Codeforces Round #787 (Div. 3) 题解来了。

实况在这里

A. Food for Animals

题目描述

1

题目分析

给你猫粮，狗粮和猫和狗都能吃的粮的个数，再给你猫狗的个数，问能否使得猫狗都有一份粮食能吃。这里我操之过急，导致WA了一发，血亏。就是说你可以先判断狗粮是否够，如果不够则通用粮食减去剩余的数目，然后在判断通用粮食和猫粮是否大于等于猫的个数就行了，但是非常要注意，通用粮食的个数不能出现负数，因为这里没判断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
40
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
int a[maxn];
void solve(){
    int x,y;
    int num[5];
    cin>>num[1]>>num[2]>>num[3]>>x>>y;
    num[3]-=max(0,x-num[1]);
    if(num[3]<0)NO
    
    if(num[2]+num[3]>=y){
        puts("YES");
    }
    else{
        puts("NO");
    }
    
    
}
void init(){
    
} 
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    
    
    return 0;
}

B. Make It Increasing

题目描述

2

题目分析

给你一个数组，一次操作可以让它整除2，问最后能通过最少多少次操作让序列严格递增。因为操作只会使得数字变小，那么我们不难得到，如果要让它操作次数最小，最后一个数不能动。然后依次往前，如果前面的比后面的大那就进行一次操作，直到 a[i]<a[i-1]||a[i]==0 因为到0了整除就不会变了，因此这个条件需要加上去。

最后只需要判断第一个数和第二个数是否都为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
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
int a[maxn];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int cnt=0;
    for(int i=n-1;i>=1;i--){
        while(a[i]>=a[i+1]&&a[i]){
            a[i]/=2;
            cnt++;
        }
    }
    if(a[1]==0&&a[2]==0){
        puts("-1");    
        return ;
    }
    printf("%d\n",cnt);
    
}
void init(){
    
} 
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    return 0;
}

C. Detective Task

题目描述

3

题目分析

一开始还以为是逻辑推理题，正面思考无果之后发现一点：当一个人是小偷的时候，这个人前面全为1或者?，后面全为0或者?当遍历第 i 个人的时候，cnt(?|1)=i-1 cnt(?|0)=n-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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
char s[maxn];
void solve(){
    s[0]=0;
    scanf("%s",s+1);
    int len=strlen(s+1);
    int cnt1=0,cnt0=0;
    for(int i=1;i<=len;i++){
        if(s[i]=='?'||s[i]=='0')cnt0++;
    }
    int ans=0;
    
    for(int i=1;i<=len;i++){
        if(s[i]=='?'||s[i]=='0'){
            cnt0--;
        }
        if(s[i-1]=='?'||s[i-1]=='1'){
            cnt1++;
        }
        if(cnt0==len-i&&cnt1==i-1){
            ans++;
        }
    }
    printf("%d\n",ans);
}
void init(){
    
} 
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    
    
    return 0;
}

D. Insert a Progression

题目描述

4

题目分析

树链剖分板题，而且只要轻重链剖分完了就可以直接输出了。

标程

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
void solve(){
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int max_x=a[1],min_x=a[1],ans=0;
    for(int i=2;i<=n;i++){
        ans+=abs(a[i]-a[i-1]);
        max_x=max(max_x,a[i]);
        min_x=min(min_x,a[i]);
    }
    ans+=min((min_x-1)*2,min(abs(a[1]-1),abs(a[n]-1)));
    if(x>max_x){
        ans+=min((x-max_x)*2,min(abs(x-a[1]),abs(x-a[n])));
    }
    cout<<ans<<endl;
    
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

E. Replace With the Previous, Minimize

题目描述

5

题目分析

这题有点小意思，意思就是一次操作能把一个字符串的所有特定字符变小 1，问你 k 次操作生成的字典序最小的字符串是什么。首先有一点肯定没错，就是我无脑把前面不是 a 的字符先都变 a 了肯定不会有问题。但是有一点需要考虑，那就是先变前面，如果后面还有比这个大一点的，那就又需要很多次才能变成 a 了，所以我们的思路就是收集所有能在 k 次范围内变成 a 的字符，从左到右遍历，显而易见，k>=25则一定可以达到全 a 的状态。遇到了不能在 k 次变成 a 的字符之后，把前面取得的最大次数先用掉，如果次数有剩余，无脑给那一个字符即可。

标程

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
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
//#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");return;}
using namespace std;
char s[maxn];
int n,k;
void change(char ch){
    //putchar(ch);putchar(10);
    for(int i=0;i<n;i++){
        if(s[i]==ch)s[i]--;
    }
    //printf("%s\n",s);
}
void solve(){
    
    cin>>n>>k;
    scanf("%s",s);
    if(k>=25){
        for(int i=1;i<=n;i++){
            putchar('a');
        }
        putchar(10);
        return ;
    }
    int q=0;
    int flag=1;
    for(int i=0;i<n;i++){
        if(s[i]-'a'>k){
            int th=k-q;
            char cc=s[i];
            for(int j=0;j<th;j++){
                //printf("%d ",j);
                //putchar(cc-j);
                change(cc-j);
                //putchar(s[i]-j);putchar(10);
                
            }
            for(int j=q;j>=1;j--){
                change('a'+j);
            }
            flag=0;
            break;
            
        }
        q=max(q,s[i]-'a');
        //printf("%d\n",q);
    }
    if(flag){
        for(int i=1;i<=n;i++){
            putchar('a');
        }
        putchar(10);
        return ;
    }
    printf("%s\n",s);
    
}
void init(){
    
} 
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    init();
    while(t--)solve();
    
    
    
    return 0;
}

现在 rating 还没出来，不知道能不能蓝，不过我知道如果 A 不失误是一定有机会蓝名的，下次再接再厉吧。