2020-07-17 17:12 已编辑

关注

牛客算法竞赛入门课第二节习题

题目描述

FST是一名可怜的小朋友，他很强，但是经常fst，所以rating一直低迷。
但是重点在于，他非常适合ACM！并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本，但是FST发现，在价格能承受的范围内，笔记本的内存和速度是不可兼得的。
可是，有一些笔记本是被另外一些“完虐”的，也就是内存和速度都不高于另外某一个笔记本，现在FST想统计一下有多少笔记本被“完虐”。

输入描述:

第一行一个正整数n，
表示笔记本的数量。接下来n行，每行两个正整数Mi，Si表示这款笔记本的内存和速度。 $n≤10^5,Mi,Si≤10^9$

输出描述:

一行，一个正整数，表示被完虐的笔记本数。

输入

4
100 700
200 500
50 100
300 400

输出

1

备注:

Mi和Si都是越大越优。
数据保证Mi互不相同，Si也互不相同。

题解

排序+倒序处理
先对数对按 Mi 排序，那么对于 j > i，会有 $M_j > M_i$ 。
因此，对于i，我们只需要考虑是否存在 $j \in [i + 1, n]$ , $S_j >S_i$ 。
我们逆序遍历，维护一个后缀最大的 $S_i$ 值，即可判断 i 是否满足条件。

const int N=1e5+10;
PII a[N];
int n;

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;

    sort(a,a+n);

    int res=0;
    int mx=0;
    for(int i=n-1;i>=0;i--)
    {
        if(a[i].se <= mx) res++;
        mx=max(mx,a[i].se);
    }
    cout<<res<<endl;

    // system("pause");
}

题目描述

糖和抖m在玩个游戏，规定谁输了就要请谁吃顿大餐：抖m给糖a b c三个驻，并在a柱上放置了数量为n的圆盘，圆盘的大小从上到下依次增大，现在要做的事就是把a柱的圆盘全部移到c柱，移动的过程中保持小盘在上，大盘在下，且限定圆盘只能够移动到相邻的柱子，即a柱子上的圆盘只能够移动到b，b柱子上的圆盘只能够移动到a或者c，c同理。现在请你设计一个程序，计算所需移动的最小步数，帮助糖赢得大餐！

输入描述:

每一行输出有一个整数n(0<=n<26), 直至文件末尾。

输出描述:

对于每一组数据，输出一行，输出移动的最小步数M。

输入

1

输出

2

题解

对于n个盘子，我们可以把它分成n-1个盘子和最后一个大盘子。
设F(n)为移动所需步数。

将n-1个盘子借助B柱移动到C柱上,这一过程移动的步数极为F(n-1)
将大盘子由A柱移动到B柱上，此时需要一步
将n-1个盘子借助B柱移动到A柱上,这一过程移动的步数同样为F(n-1)
将大盘子由B柱移动到C柱上，此时需要一步
将n−1个盘子借助B柱子移动到C柱上，此时需要的步数仍为F(n-1)
综合以上分析，F(n)=3F(n-1)+2。对两边同时加上1可以凑成一个等比数列，最后求出其通项公式即为 $3^n-1$ 。

题目描述

给你一个1->n的排列和一个栈，入栈顺序给定
你要在不打乱入栈顺序的情况下，对数组进行从大到小排序
当无法完全排序时，请输出字典序最大的出栈序列

输入描述:

第一行一个数n
第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格

输出描述:

输出一行n个数表示答案，用空格隔开，结尾无空格

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

2入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈

题解

我们设f[i]表示i-n的元素的最大值。
假设当前入栈的是第i个元素，如果当前栈顶的元素比f[i+1]大，那么如果我们当前元素不出栈的话，之后如果有元素入栈，那么最后出栈的字典序一定会小于当前元素出栈的字典序。于是按照这个策略模拟即可

const int N=1e6+10;
int stk[N],top;
int a[N];
int f[N];//f[i]:i~n的最大值
int n,m;

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];

    for(int i=n-1;i>=0;i--) f[i]=max(f[i+1],a[i]);

    for(int i=0;i<n;i++)
    {
        stk[++top]=a[i];
        while(top && stk[top]>f[i+1]) cout<<stk[top--]<<' ';//因为f[n+1]=0,所以最后一定会把栈弹空
    }

    // system("pause");
}

题目描述

小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。）
例如:ooOOoooO经过一段时间以后会变成oO。

输入描述:

数据有多组，处理到文件结束。
每组输入包含一行仅有'O'与'o'组成的字符串。

输出描述:

每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

输入

ooOOoooO

输出

oO

说明

自左到右进行合并

备注:

对于100%的数据，
字符串的长度不超过100。

题解

直接拿栈模拟即可

const int N=110;
char s[N];
stack<char> stk;
int n;

int main()
{
    while(cin>>s)
    {
        n=strlen(s);
        for(int i=0;i<n;i++)
        {
            if(stk.size() && stk.top() == s[i])
            {
                if(stk.top() == 'o')//同为小气泡
                {
                    stk.pop();
                    if(stk.size() && stk.top() == 'O') stk.pop();
                    else stk.push('O');
                }
                else stk.pop();//同为大气泡
            }
            else stk.push(s[i]);
        }

        vector<char> res;
        while(stk.size())
        {
            res.push_back(stk.top());
            stk.pop();
        }
        reverse(res.begin(),res.end());

        for(auto t:res) cout<<t;
        cout<<endl;
    }
    // system("pause");
}

题目描述

小C最近学会了java小程序的开发，他很开心，于是想做一个简单的记事本程序练练手。

他希望他的记事本包含以下功能：

1、append(str)，向记事本插入字符串 str（英文字符）

2、delete(k)，删除记事本最后k个字符（保证不为空串）

3、print(k)，输出记事本第k个字符（保证不为空串）

4、undo()，撤销最近的1（或者）操作，使记事本回到1（或者2）操作之前的状态

可怜的小C琢磨了半天还是做不来，聪明的你能解决小C的问题吗？

输入描述:

多组输入

第一行输入一个整数q，代表操作总数

以下q行每行描述了一个操作，每行以一个整数t开始（1 <= t <= 4）。

t表示上述问题陈述中定义的操作类型。 如果操作需要参数，则后跟空格分隔的参数。

题目保证所有操作均合法

1 <= q <= 10^6 
1 <= k <= |记事本内容长度| 
每个测试数据中str的总长度 <= 10^6

请使用 ios::sync_with_stdio(false); 对读写进行加速

输出描述:

所有操作类型3必须输出第k个字符，每行以换行符结束。

示例1

输入

复制

输出

复制

b
c
a

说明

**样例解释**

假设记事本用字符串S表示

1、插入ab，S="ab"

2、输出第2个字符，是b

3、删除最后2个字符，S=""

4、插入cd, S="cd"

5、输出第1个字符，是c

6、撤销，此时S=""

7、撤销，此时S="ab"

8、输出第1个字符，是a

题解

直接用存储字符串类型的栈模拟即可。

int n;

int main()
{
    while(cin>>n)
    {
        string s;
        stack<string> stk;
        stk.push(s);//初始空字符串不要忘记入栈
        for(int i=0;i<n;i++)
        {
            int t;
            cin>>t;
            if(t == 1)
            {
                string str;
                cin>>str;
                s.append(str);
                stk.push(s);
            }
            else if(t == 2)
            {
                int k;
                cin>>k;
                int len=s.size();
                s.erase(len-k,len);
                stk.push(s);
            }
            else if(t == 3)
            {
                int k;
                cin>>k;
                cout<<s[k-1]<<endl;
            }
            else
            {
                stk.pop();
                s=stk.top();
            }
        }
    }
    // system("pause");
}

题目描述

HA实验有一套非常严密的安全保障体系，在HA实验基地的大门，有一个指纹锁。

该指纹锁的加密算***把一个指纹转化为一个不超过1e7的数字，两个指纹数值之差越小，就说明两个指纹越相似，当两个指纹的数值差≤k时，这两个指纹的持有者会被系统判定为同一个人。
现在有3种操作，共m个，
操作1：add x，表示为指纹锁录入一个指纹，该指纹对应的数字为x，如果系统内有一个与x相差≤k的指纹，则系统会忽略这次添加操作
操作2：del x，表示删除指纹锁中的指纹x，若指纹锁中多个与x相差≤k的指纹，则全部删除，若指纹锁中没有指纹x，则可以忽略该操作，
操作3：query x，表示有一个持有指纹x的人试图打开指纹锁，你需要设计一个判断程序，返回该人是否可以打开指纹锁（只要x与存入的任何一个指纹相差≤k即可打开锁）。
初始状态，指纹锁中没有任何指纹。

输入描述:

第一行有2个正整数m，k。
接下来m行，每行描述一种操作：add x，del x或query x。

输出描述:

对于每个query操作，输出一行，包含一个单词“Yes”或“No”，表示该人是否可以打开指纹锁。

示例1

输入

复制

4 3
add 1
add 10
query 5
query 4

输出

复制

No
Yes

示例2

输入

复制

4 3
add 1
query 4
del 1
query 4

输出

复制

Yes
No

示例3

输入

复制

6 3
add 10
query 10
add 5 
query 5
del 7        //系统将指纹10和指纹5全部删除
query 8

输出

复制

Yes
Yes
No

备注:

对于100%的测试数据：
1 ≤ k,m ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

题解

需要重载set的()运算，重载的含义为：在 abs(a - b) <= k 存在的情况下不插入b，否则按插入b后升序排序。
set中判断元素是否相等：
if(!(A<B || B<A))，当A<B和B<A都为假时，它们相等。

int n,k;
struct cmp
{
    bool operator()(int a,int b) const
    {
        if(abs(a-b) <= k) return false;
        return a<b;
    }
};
set<int,cmp> s;

int main()
{
    ios;
    cin>>n>>k;

    for(int i=0;i<n;i++)
    {
        string op;
        int x;
        cin>>op>>x;
        if(op == "add") s.insert(x);
        else if(op == "del") s.erase(x);
        else
        {
            if(s.find(x) != s.end()) puts("Yes");
            else puts("No");
        }
    }
    // system("pause");
}

题目描述

CSL正在学习《计算机办公自动化》文件的建立与删除。

CSL发现，当他新建一个word文档时，会得到一个名为"新建 Microsoft Office Word 文档.doc"的文件，再新建一个，则名为"新建 Microsoft Office Word 文档(2).doc"，再新建，便是"新建 Microsoft Office Word 文档(3).doc"。不断新建，编号不断递增。倘若他已经新建了三个文档，然后删除了"新建 Microsoft Office Word 文档(2).doc"，再新建一个就又会得到一个"新建 Microsoft Office Word 文档(2).doc"。

严格来说，Windows在每次新建文档时，都会选取一个与已有文件编号不重复的最小正整数作为新文档的编号。

现在，请你编程模拟以上过程，支持以下两种操作：

New：新建一个word文档，反馈新建的文档的编号；

Delete id：删除一个编号为id的word文档，反馈删除是否成功。

初始时一个文件都没有，"新建 Microsoft Office Word 文档.doc"的编号算作1。

输入描述:

第一行一个正整数n表示操作次数，接下来n行，每行表示一个操作。若该行为"New"，则表示新建，为:Delete id"则表示要删除编号为id的文档，其中id为一个正整数。操作按输入顺序依次进行。操作次数不超过100000，删除编号的数值不超过100000。

输出描述:

对于输入的每一个操作，输出其反馈结果。对于新建操作，输出新建的文档的编号；对于删除操作，反馈删除是否成功：如果删除的文件存在，则删除成功，输出"Successful"，否则输出"Failed"。

示例1

输入

复制

12
New
New
New
Delete 2
New
Delete 4
Delete 3
Delete 1
New
New
New
Delete 4

输出

复制

1
2
3
Successful
2
Failed
Successful
Successful
1
3
4
Successful

题解

简单来说：在不删除文档的情况下，你就是从1->n一条龙创建下去。
但如果你删除了前面的文件，而且是多个的话，就从最小的那个，把这些文件命名中的空缺填充完整。
用set维护当前已创建的文档，用优先队列维护已删除的文档
在新建的时候，我们先查优先队列里面有没有元素（表示前面有没有填满），填满了就往后创建，没满就从队列里面取呗。
那在删除的时候，就判断这个能不能删，能删就删了放优先队列里面呗。

const int N=1e5+10;
set<int> s;
priority_queue<int,vector<int>,greater<int> > heap;
int n;

int main()
{
    cin>>n;

    int cnt=1;
    for(int i=0;i<n;i++)
    {
        string op;
        cin>>op;
        if(op == "New")
            if(heap.empty())
            {
                cout<<cnt<<endl;
                s.insert(cnt);
                cnt++;
            }
            else
            {
                cout<<heap.top()<<endl;
                s.insert(heap.top());
                heap.pop();
            }
        else
        {
            int x;
            cin>>x;
            if(s.find(x) != s.end()) puts("Successful"),s.erase(x),heap.push(x);
            else puts("Failed");
        }
    }
    // system("pause");
}

题目描述

给出长度为n的序列a，其中第i个元素为

，定义区间(l,r)的价值为

$v_{l,r} = max(a_i - a_j | l \leqslant i,j\leqslant r)$

请你计算出 $\sum_{l = 1}^n \sum_{r = l + 1}^n v_{l,r}$

输入描述:

第一行输入数据组数T
对于每组数据，第一行为一个整数n，表示序列长度
接下来一行有n个数，表示序列内的元素

输出描述:

对于每组数据，输出一个整数表示答案

示例1

输入

复制

3
3
4 2 3
5
1 8 4 3 9
20
2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17

输出

复制

5
57
2712

说明

对于一组测试数据的解释：
区间[1, 2]的贡献为：4 - 2 = 2
区间[1, 3]的贡献为：4 - 2 = 2
区间[2, 3]的贡献为：3 - 2 = 1
2 + 1 + 2 = 5.

备注:


不保证数据随机生成！

题解

图片说明

用l[i]控制a[i]左端点最远可以到哪里，r[i]控制a[i]右端点最远可以到哪里，说明当前a[i]是区间[l[i],r[i]]中的最大值，最小值只需讲所有a[i]取反进行相同的步骤即可。

以a[i]为区间最值的区间个数有 $(R_i-i+1)*(i-L_i+1)-1$ 。
举个例子：1 2 3 4 5，求必须包含3的区间个数，左边有3种选择：1 2；2；不选；右边也有三种选择：4 5；4；不选；但是题目中要求区间长度至少为2，所以两边都不选的情况不能计算在内。
当往左扩展或者向右扩展其中一个一定不能有等于号，因为如果数据中有两个或多个值相同时，如果你都写成了大于等于，那么算出的区间就是以该值为最大值的严格意义上的那段区间，比如：
6 5 5 4 8
如果你都写成了大于等于，那么数据中两个5对应的左右端点就都是：
2 4
这样没毛病，[2,4]上确实5是最大值，但是当你算子区间最值之和时就会重复，以第一个5为最值的子区间有：[2,2]、[2,3]、[2,4]，而算第二个5时：[2,3]、[3,4]、[2,4]、[3,3]，很明显[2,3]、[2,4]这俩区间重复了，我们应该把它们减去，如何减去呢？其实只要把大于等于改成大于就行了，这样5的右端点就拓展到第一个大于等于5的前一个位置，也就是第一个5区间变成了[2,2]，就完成了去重。

题目描述

兔子最近喜欢上了逆序对。
一个逆序对(i,j) 需要满足 i < j 且 a_i > a_j
兔子觉得只是求一个序列的逆序对个数太没有意思了。
于是兔子想到了一个更有趣的问题！
兔子可以把区间[L,R] 反转，例如序列{1,2,3,4} 反转区间[1,3] 后是{3,2,1,4}。
兔子有m次反转操作，现在兔子想知道每次反转后逆序对个数是奇数还是偶数，兔子喜欢偶数，而讨厌奇数。
请注意，每一次反转操作都会对原序列进行改变。例如序列{1,2,3,4} 第一次操作区间[1,2] 后变成{2,1,3,4} 第二次反转区间[3,4] 后变成 {2,1,4,3}

输入描述:

第一行一个整数 n，表示序列的大小。
第二行 n 个整数a_i 表示序列的各个元素。
第三行一个整数m，表示操作个数。
接下来 m 行，每行两个整数 l，r，表示反转的区间。

输出描述:

输出共m行每行一个字符串，表示反转后序列逆序对个数的奇偶性，如果是逆序对个数奇数，输出"dislike"(不含引号)，如果是偶数，输出"like"。

示例1

输入

复制

输出

复制

dislike
like
like
dislike

说明

注意：以下的(i,j)指的是位置 i 和位置 j
a={2,1,3,4} 的逆序对是 (1,2) 共1个，1是奇数，所以是dislike
a={2,1,4,3} 的逆序对是 (1,2) (3,4)共2个,2是偶数，所以是like
a={3,4,1,2} 的逆序对是 (1,3) (1,4) (2,3) (2,4)共4个,4是偶数，所以是like
a={3,1,4,2} 的逆序对是 (1,2) (1,4) (3,4) 共3个,3是奇数，所以是dislike

备注:

对于20%的数据
1 ≤ n ≤ 100 
1 ≤ m ≤ 10 
对于40%的数据
1 ≤ n ≤ 2000 
1 ≤ m ≤ 50 
对于60%的数据
1 ≤ n ≤ 2000 
1 ≤ m ≤ 10⁴
对于100%的数据
1 ≤ n ≤ 10⁵ 
1 ≤ m ≤ 2*10⁶
对于所有数据 l ≤ r且 a_i 是n的一个排列，即a_i互不相同且a_i ≤ n
由于读入数据较大，建议使用快速读入。

题解

首先考虑翻转操作，翻转一个区间[l,r]对于区间外的数逆序对数量是不变的。那么只需要考虑区间内的即可。

区间内的逆序对+顺序对=总对数

翻转之后顺序对变成逆序对，逆序对变成顺序对。
总对数等于 $C_n^2=\frac{(r-l+1)(r-l)}{2}$
那么区间总对数-区间逆序对个数=区间顺序对个数

那么可以得到一个等式：
原来的总逆序对个数-区间内原来逆序对个数+区间内总对数-区间内原来逆序对个数=反转之后总逆序对个数。

化简一下即： $sum-\frac{(r-l+1)(r-l)}{2}-2x$

由于2*x不对奇偶性造成影响，所以不需要计算。

const int N=1e5+10;
int a[N];
int b[N];
int n,m;
LL ans;

void merge(int l,int r)
{
    if(l >= r) return;
    int mid=l+r>>1;
    merge(l,mid);
    merge(mid+1,r);

    int i=l,j=mid+1;
    for(int k=l;k<=r;k++)
        if(j>r || (i<=mid && a[i]<=a[j])) b[k]=a[i++];
        else
        {
            b[k]=a[j++];
            ans+=mid-i+1;
        }

    for(int k=l;k<=r;k++) a[k]=b[k];
}

int main()
{
    ios;
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    merge(1,n);

    cin>>m;

    while(m--)
    {
        int l,r;
        cin>>l>>r;
        int p=(r-l+1ll)*(r-l)/2;
        ans-=p;
        int res=ans%2;
        if(res & 1) puts("dislike");
        else puts("like");
    }
    // system("pause");
}

题意

我们有长度为n的数组array1:[a1,a2,a3,a4,a5,a6,.....,an]
以及长度为m的数组array2:[b1,b2,b3,b4,b5,b6,.....bm]
问array2中有几个元素等于array1中一个或两个元素相加。注意是一个或两个。

题解

将数组array1看成一串二进制串，将 $a_i$ 对应的位数置1，如array1:[1,3,5],则s1=101010(从低位到高位),对array2采用类似处理得到s2。

遍历array1，每次将array1左移 $a_i$ 位，其中为1的二进制位即表示array1：[a1,a2,a3,a4,a5,a6,.....,an]和 $a_i$ 相加得到的结果
与array2做与运算即可得到能凑出的array2的个数
将array2已凑出的数的对应位置0，防止重复统计，本步可采用异或运算。
最后剩下的s2中为1的位即为不能凑出的数，用m减去最后s2中1的个数即为能凑出的数的个数

由于array1可以是1个数凑出，加上左移0位的情况即可

const int N=2e5+10;
bitset<N> s1,s2;
int a[N];
int n,m;

int main()
{
    ios;
    while(cin>>n)
    {
        s1.reset();
        s2.reset();

        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            s1[a[i]]=1;
        }

        cin>>m;

        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            s2[x]=1;
        }

        for(int i=0;i<=n;i++)
            s2^=s2&(s1<<a[i]);

        cout<<m-s2.count()<<endl;
    }

    // system("pause");
}