Codeforces Global Round 13

链接:https://codeforces.ml/contest/1491

A. K-th Largest Value

分析

直接模拟签完到,然后wa了一发(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 3;
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, q;
int cnt = 0;
cin >> n >> q;
for(int i = 0; i < n; ++i){
cin >> a[i];
if(a[i] == 1) cnt++;
}
while(q--)
{
int as, b;
cin >> as >> b;
if(as == 1){
if(a[b - 1] == 1){
a[b - 1] = 0;
cnt--;
}
else{
a[b - 1] = 1;
cnt++;
}
}
else{
if(cnt >= b){
cout << 1 << endl;
}
else cout << 0 << endl;
}
}
return 0;
}

B. Minimal Cost(思维)

img

题意

给一个n行10^6^+1列的矩阵迷宫,初始点在$(1,0)$,目标在$(n,10^6+1)$.其中行从1开始计数,列从0开始计数。

其中,每一行将被设置一个障碍,这个障碍可以被移动。其中横向移动花费v,纵向移动花费u.

你要做的是花费最少的代价,使得初始点和目标连通。

分析

其实只需要考虑三种情况:

  1. 所有的障碍在同一列。由于列数很大,这里要么是将其中一个障碍进行两次横向移动,要么是将其进行一次横向移动和一次纵向移动。取最小值即可。
  2. 存在障碍处于对角位置(如上示意图)但没有空缺。此时只需要将一个障碍移动一次即可。横纵皆可。
  3. 本身就有空缺,即相邻行的障碍出现横向距离大于1的情况。这个时候不需要移动障碍,直接就可以到达目标。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
typedef long long ll;
int a[105];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
ll n, u, v;
cin >> t;
while(t--)
{
cin >> n >> u >> v;
int flag = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
for(int i = 2; i <= n; ++i){
if(abs(a[i] - a[i - 1]) == 1) flag = 1;
else if(abs(a[i] - a[i - 1]) > 1){
flag = 2;
break;
}
}
if(flag == 1){
cout << min(u, v) << endl;
}
else if (flag == 0){
cout << min(2 * v, u + v) << endl;
}
else cout << 0 << endl;
}
return 0;
}

C.Pekora and Trampoline(贪心)

题意

现在从位置1~n放着n个蹦床,每个蹦床有弹跳力$S_i$.Pekora选择其中一个蹦床$i$开始弹跳.每弹上一个蹦床,他就会跳到$S_i+i$的位置,且此时$i$的弹跳力变为$max\{1, S_i-1\}$.每次跳到大于n的地方后,Pekora结束一轮弹跳。问至少需要几轮弹跳可以让所有蹦床的弹跳力都变为1?

分析

一步步贪心。首先,考虑选前面的还是后面的蹦床起跳。如果选后面的,那么就算后面的都变为1了,前面的也还要补;反之选前面的起跳,前面的变为1了,后面的可能需要补,也可能就直接踩到1了。因此,我们用最贪心的策略,选择永远从蹦床1起跳。

然后,由于蹦床弹跳力变为1后,我们再跳它就对它的弹跳力不影响了。因此我们可以把从1开始优化到从第一个弹跳力不为0的蹦床开始。

接着,我们要考虑弹跳的情况。我们可以这样在线更新:

如果某点$i$此时弹跳力为$x$,大于1,那么从它开始还要跳$x-1$次,这几次的下一个蹦床将覆盖$[i+2,max\{n,i+x\}]$,那么就要求答案加上$x-1$.

反之,如果某点$i$在经历前面的弹跳后,不需要继续跳了,那么我们可以让它的下一个蹦床继承下来这多余的几次弹跳,看看这几次弹跳是否能对接下来的蹦床起作用。

实现上,我们可以维护一个数组表示从前面出发到这里弹跳了几次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 5;
typedef long long ll;
ll a[maxn];
ll cnt[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--)
{
memset(cnt, 0, sizeof(cnt));
int n;
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
//贪心:从1起跳
ll ans = 0;
for(int i = 1; i <= n; ++i){
if(a[i] - 1 > cnt[i]) ans += a[i] - 1 - cnt[i];
else if(a[i] - 1 < cnt[i]) cnt[i + 1] += cnt[i] - a[i] + 1;
for(int j = i + 2; j <= min(a[i] + i, ll(n)); ++j){
cnt[j]++;
}
}
cout << ans << endl;
}
return 0;
}

D. Zookeeper and The Infinite Zoo(位运算)

分析

考虑条件$u\&v=v$,也就是说,二进制表示下,$v$中的所有出现1的位置都必须在$u$中也为1.

此时,考虑$u+v$,由于只发生1+1,0+0,故1的个数不会增多,而且不会有1左移。

因此我们可以简化判定:

  1. 如果u<v,不可能(v中一定有二进制的1与u中的对不上)

  2. 如果u>=v,就必须保证:

    (1)对二者二进制表示的所有位,从最低位开始的前$i$位,一定有$u$的1个数>$v$的1个数,其中$1≤i≤$最大位数.

    (2)u最低位的1一定不能比v的最低位的1还低。

例1:对于1,4,二进制表示分别为001,100,从前1位到前3位,1的二进制中1的个数分别为1,1,1.而对于4,这个数据是0,0,1.满足2.(1).且v=1的最低位1是第一位,u=4的最低位1是第三位,3>1,符合2.(2).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 3;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int q;
cin >> q;
while(q--)
{
int a, b;
cin >> a >> b;
//维护1个数的前缀和
int x[31], y[31];
//----------------------------------
for(int i = 0; i <= 30; ++i){
x[i] = a >> i & 1;
y[i] = b >> i & 1;
}
//------------------------------------
//此段是看他人题解中发现的一种计算二进制1个数的方法,比我求二进制串再一个个数快多了呀!
for(int i = 1; i <= 30; ++i){
x[i] += x[i - 1];
y[i] += y[i - 1];
}
if(b == 2 * a){
cout << "YES" << endl;
continue;
}
if(a == b){
cout << "YES" << endl;
continue;
}
if(a > b){
cout << "NO" << endl;
continue;
}
bool flag = 1;
for(int i = 0; i <= 30; ++i){
if(x[i] < y[i]){
flag = 0;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}