Educational Codeforces Round 100 (Rated for Div. 2)

A. Dungeon

题意：三只小怪兽，分别有a，b，c点血量。普攻一次只能攻击一只怪兽，并且扣1点血。但是第7,14,21,……，7k 次，有普攻强化，会对三只怪兽同时扣除1点血。求是否能够保证，最后一次强化普攻，可以同时把三只怪打死。

思路：首先每打到一次强化普攻，就总共造成了 6+3 也就是9滴血。所以a+b+c 要是9的倍数。其次，血量最低的怪兽，要至少能够抗住强化普攻的扣血，也就是min(a,b,c) >= (a+b+c)/9 。

AC代码：

#include <bits/stdc++.h>
//#define int long long
const int N = 4e5+10;
const int mod = 1e9+7;
using namespace std;
int n,m,s,d;
int res = 0;
 
signed main(){
    int t = 1;
    cin>>t;
    while(t--){
        int a,b,c;
        cin>>a>>b>>c;
        if((a+b+c)%9 == 0 && min(c,min(a,b)) >= (a+b+c)/9){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
 
    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

B. Find The Array

题意：给定一个n个元素的数组a[n],S是 数组的和。求另一个数组b，使得b的所有相邻元素，都存在倍数关系，如 1，2，4，4，2，4。且所有的abs(a[i]-b[i])*2 <= S。

思路：先让b[0] = a[0]，然后对于b[i]，每次取a[i]/b[i-1]*b[i-1]，这样就可以保证，b[i]和b[i-1]始终保持倍数关系，并且尽可能的接近a[i]。写的时候没有想到怎么证明，盲交了一发。过了。别人大多数不是这么写的，并且有证明。这写法，下次再证。有可能是数据水了。

AC代码：

#include <bits/stdc++.h>
//#define int long long
const int N = 4e5+10;
const int mod = 1e9+7;
using namespace std;
int n,m,s,d;
int res = 0;
int a[N];
 
signed main(){
    int t = 1;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 0 ; i < n ; i ++) cin>>a[i];
        int sum = 0;
        for(int i = 0 ; i < n ; i ++) sum += a[i];
        int pre = a[0];
        cout<<pre<<" ";
        for(int i = 1 ; i < n ; i ++){
            int now = (a[i]/pre)*pre;
            now = now==0 ? 1 : now;
            cout<<now<<" ";
            pre = now;
        }
        cout<<endl;
    }
 
    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

C. Busy Robot

题意：一个忙碌的机器人，一根数轴，机器人在这个数轴上反复横跳。初始在0位置，机器人每次只能执行一条命令，当这条命令结束后，才能开始执行别的命令。命令按时间顺序给出，t，x，即命令机器人t时刻开始出发到x点取。再[t_i - t_i+1]时间段内，如果机器人经过了x点，那么就认为，命令i被执行了。（实际上可能正在执行别的命令，但是就是就是按这样的条件计数）

思路：就是一个小模拟。但是略有些麻烦。首先考虑，如果t_i时刻没有在执行别的命令，这时候执行命令i,并且在t_i+1时刻之前到达了目的地，那么这条命令就算作正确执行了。 另一种情况就是，正在执行别的命令呢，但是在[t_i - t_i+1]时间段内，凑巧，经过了x点，那么也算作正确执行了。就模拟判断就好了。

AC代码：

#include <bits/stdc++.h>
#define int long long
const int N = 4e5+10;
const int mod = 1e9+7;
using namespace std;
int n,m,s,d;
int res = 0;
struct node{
    int t,x;
    node(){}
    node(int tt,int xx){t=tt,x=xx;}
}a[N];
 
signed main(){
    int t = 1;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 0 ; i < n ; i ++){
            int ti;
            int x;
            cin>>ti>>x;
            a[i] = node(ti,x);
        }
        a[n].x = a[n-1].x;
        a[n].t = 1e17;
        int now = 0;            // current position
        int res = 0;            // the ans
        int busy = 0;           // flag
        int command = 0;        // last command
        int time = 0;           // past time
        int need = 0;           // time needed for walk
        for(int i = 0 ; i <= n ; i ++){
            if(!busy){
                time = 0;
                busy = 1;
                command = i;
                need = abs(a[i].x-now);
            }else{
                time += a[i].t-a[i-1].t;        // past time
                if(time >= need){
                    if(i-command == 1){
                        res++;
                        //cout<<a[i].t<<" -111-  "<<a[i].x<<endl;
                        //cout<<"pre : "<<a[command].t<<" "<<a[command].x<<endl;
                    }
                    now = a[command].x;
                    time = 0;
                    command = i;
                    need = abs(a[i].x-now);
                }else{
                    if(a[i].x < now && a[command].x < now){
                        if(abs(a[i].x - now) >= time && abs(a[i].x - now) <= time+a[i+1].t-a[i].t && abs(a[i].x - now) <= need){
                            res++;
                            //cout<<a[i].t<<" -222- "<<a[i].x<<endl;
                            //cout<<"pre c: "<<a[command].t<<" "<<a[command].x<<" now"<<now<<endl;
                        }
                    }else if(a[i].x > now && a[command].x > now){
                        if(abs(a[i].x - now) >= time && abs(a[i].x - now) <= time+a[i+1].t-a[i].t && abs(a[i].x - now) <= need){
                            res++;
                            //cout<<a[i].t<<" -222- "<<a[i].x<<endl;
                            //cout<<"pre c: "<<a[command].t<<" "<<a[command].x<<" now"<<now<<endl;
                        }
                    }
                }
            }
        }
        cout<<res<<endl;
    }
 
    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

D. Pairs

题意：给定n个数在[1,2n]范围内。同时你有2n个数，就是1-2n，然后又是两种元组(x，y)，要么取他们的 min 要么取他们的max。把这2n个数分成n个元组。 对前x个取min，后n-x个取max，然后得到最初给定的数组。求 有多少个x 满足条件。

思路：首先2n个数，总共出现了n个数，剩下n个数没出现，那么把出现和没出现的分别放在两个数组里面。接着二分枚举x。待证。。

AC代码：

#include <bits/stdc++.h>
#define int long long
#define pb push_back
const int N = 4e5+10;
const int mod = 1e9+7;
using namespace std;
int n,m,s,d;
int res = 0;
int a[N];
int mark[N];
vector<int> v1;
vector<int> v2;
 
 
int check(int mid){
    for(int i = 0 ; i < mid ; i ++){
        if(v1[i] > v2[n-mid+i])
            return 1;
    }
    for(int i = 0 ; i < n - mid ; i ++){
        if(v1[i+mid] < v2[i])
            return 2;
    }
    return 0;
}
 
 
 
signed main(){
    int t = 1;
    cin>>t;
    while(t--){
        cin>>n;
        v1.clear();
        v2.clear();
        for(int i = 1 ; i <= 2*n ; i ++){
            mark[i] = 0;
        }
        for(int i = 0 ; i < n ; i ++){
            cin>>a[i];
            mark[a[i]] = 1;
        }
        for(int i = 1 ; i <= 2*n ; i ++){
            if(mark[i])
                v1.pb(i);
            else
                v2.pb(i);
        }
        int l = 0,r = n;
        int L = n,R = n;
        while(l <= r){
            int mid = (l+r)>>1;
            if(check(mid) != 2){
                L = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        l = 0,r = n;
        while(l <= r){
            int mid = (l+r)>>1;
            if(check(mid) != 1){
                R = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        cout<<(R-L+1)<<endl;
    }
    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