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（思维）
题意
给一个n行10^6^+1列的矩阵迷宫，初始点在$(1,0)$，目标在$(n,10^6+1)$.其中行从1开始计数，列从0开始计数。
其中，每一行将被设置一个障碍，这个障碍可以被移动。其中横向移动花费v，纵向移动花费u.
你要做的是花费最少的代价，使得初始点和目标连通。
分析
其实只需要考虑三种情况：
- 所有的障碍在同一列。由于列数很大，这里要么是将其中一个障碍进行两次横向移动，要么是将其进行一次横向移动和一次纵向移动。取最小值即可。
- 存在障碍处于对角位置（如上示意图）但没有空缺。此时只需要将一个障碍移动一次即可。横纵皆可。
- 本身就有空缺，即相邻行的障碍出现横向距离大于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];
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左移。
因此我们可以简化判定：
如果u<v，不可能（v中一定有二进制的1与u中的对不上）
如果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;
int x[31], y[31];
for(int i = 0; i <= 30; ++i){
x[i] = a >> i & 1;
y[i] = b >> i & 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;
}
|
