Educational Codeforces Round 100 (Rated for Div. 2) A~D题解

A. Dungeon

• 题意
  三个怪物血量分别为$a,b,c$，每回合你可以选择一个怪物造成$1$点伤害，特殊的当回合数是$7$的倍数的时候能对所有怪物造成$1$点伤害。问能否在特殊的回合杀死所有怪物。

• 解题思路
  我们注意到，$7$轮回合下来我们可以造成$9$的伤害，所有$a+b+c$必须是$9$的倍数，同时我们还必须保证在特殊回合杀死怪物，即怪物不能在最后一个特殊回合之前死去，我们特判一下最小的血量是否满足即可。

• AC代码

/**
  *@filename:A
  *@author: pursuit
  *@created: 2021-08-17 09:19
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,a,b,c;
void solve(){
    int sum = a + b + c;
    if(sum % 9 == 0 && min(a,min(b,c)) >= sum / 9){
        puts("YES");
    }
    else{
        puts("NO");
    }
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%d%d", &a, &b, &c);
        solve();
    }
    return 0;
}
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

B. Find The Array

• 题意
  给你一个序列$a$，要求你构造一个美丽序列$b$，其中美丽序列满足：
  1. $\forall i\in [1,n],1\le b_i\le 10^9$；
  2. $b$中相邻的两数能否整除。
  3. 与$a$作差的绝对值之和$\le suma$
• 解题思路
  我们知道$1$是任何数的除数，那么如果我们相邻间隔构造$1,a_i\dots$这种是不是可以满足呢$?$，对前两个条件我们肯定是满足的，而第三条我们得到的约为$a$的奇数位置之和，这个可能不满足，那么我们再构造偶数位置之和是不是可以呢？很明显是的，因为这两部分加起来则为$sum$。至此题解。
• AC代码

/**
  *@filename:B
  *@author: pursuit
  *@created: 2021-08-17 09:32
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 50 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n,a[N],b[N];
ll sum;
void solve(){
    ll sum1 = 0;
    for(int i = 1; i <= n; ++ i){
        if(i & 1){
            b[i] = 1;
        }
        else{
            b[i] = a[i];
        }
        sum1 += 1LL * (a[i] - b[i]);
    }
    if(sum1 * 2 <= sum){
        for(int i = 1; i <= n; ++ i){
            printf("%d ", b[i]);
        }
    }
    else{
        for(int i = 1; i <= n; ++ i){
            printf("%d ", (i & 1) ? a[i] : 1);
        }
    }
    puts("");
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        sum = 0;
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
            sum += a[i];
        }
        solve();
    }
    return 0;
}
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
54

C. Busy Robot

• 题意
  给你一堆机器指令，判断有几条机器指令有效，其中当时间处于$[t_i,t_{i+1}]$，机器人位置达到了$x[i]$，则认为机器指令有效。

• 解题思路
  一道模拟题，首先我们需要清楚当前的机器人授予了哪条指令，将要到达哪个位置，然后我们再判断在第$i$条指令的时候是否有可能到达。

• AC代码

/**
  *@filename:C
  *@author: pursuit
  *@created: 2021-08-17 10:06
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int T,n;
ll x[N],t[N];
void solve(){
    t[n + 1] = 1e15;
    int cnt = 0;
    ll cur = 0,target = 0;
    for(int i = 1; i <= n; ++ i){
        if(cur == target){
            target = x[i];
        }
        ll d = t[i + 1] - t[i],sum = abs(cur - target);
        //说明目标点在当前位置的左端。而当前的任务也在当前位置左端。我们即可判断这期间能不能到达x[i]
        if(target >= cur && cur <= x[i] && min(cur + d,target) >= x[i]){
            cnt ++;
        }
        else if(target <= cur && cur >= x[i] && max(cur - d,target) <= x[i]){
            cnt ++;
        }
        if(target >= cur){
            cur += min(d,sum);
        }
        else{
            cur -= min(d,sum);
        }
    }
    printf("%d\n", cnt);
}
int main(){	
    scanf("%d", &T);
    while(T -- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i){
            scanf("%lld%lld", &t[i], &x[i]);
        }
        solve();
    }
    return 0;
}
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
54

D. Pairs

• 题意
  给出一个序列$b$，长度为n。现在支持有两种操作：

  1. 对于一组pair(x,y)选择pair中小的数留下
  2. 对于一组pair(x,y)选择pair中大的数留下

  现在有1~2n的数，数值分别为1-2n，现在可以将这2n个数进行任意的分组，对其中的x组执行1操作，n-x组执行2操作。输出有多少个x可以使得，执行完操作以后，得到给出的数组$b$。

• 解题思路
  首先我们可以将这未占用的$n$个数，那么试想，如果要进行$x$个操作$1$，那么肯定是利用未占用的后$x$个数去和$b$中的前$x$个数进行。同理操作$2$则反过来。那么我们假设只通过操作$1$，能获得的最小$x$是多少，同理我们考虑只通过操作$2$，能获得的最大$x$是多少，那么这即是$x$的可选区间，因为这是符合答案单调的。具体看$AC$代码。

• AC代码

/**
  *@filename:D
  *@author: pursuit
  *@created: 2021-08-17 12:34
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 4e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n,a[N],b[N],vis[N];
int check(int x){
    //分前b个x组。取最小的。
    for(int i = 1; i <= x; ++ i){
        if(a[i] > b[n - x + i])return 1;//说明x太大了。
    }
    //取最大的。
    for(int i = x + 1; i <= n; ++ i){
        if(a[i] < b[i - x])return 2;//说明x太小了。
    }
    return 0;//说明符合。
}
void solve(){
    int cnt = 0;
    for(int i = 1; i <= 2 * n; ++ i){
        //统计未使用的值。
        if(!vis[i]){
            b[++cnt] = i;
        }
    }
    //二分上边界和下边界。
    int l = 0,r = n,lBound = 0;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid) != 2){
            //说明符合。
            lBound = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;//说明x太小了。
        }
    }
    l = 0,r = n;
    int ans =0;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid) != 1){
            //说明符合。
            ans = max(ans,mid - lBound + 1);
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    printf("%d\n", ans);
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        memset(vis,false,sizeof(vis));
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
            vis[a[i]] = true;
        }
        solve();
    }
    return 0;
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77