Codeforces Round 787(Div.3)题解

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 不失误是一定有机会蓝名的,下次再接再厉吧。

文章目录
  1. 1. A. Food for Animals
    1. 1.1. 题目描述
    2. 1.2. 题目分析
    3. 1.3. 标程
  2. 2. B. Make It Increasing
    1. 2.1. 题目描述
    2. 2.2. 题目分析
    3. 2.3. 标程
  3. 3. C. Detective Task
    1. 3.1. 题目描述
    2. 3.2. 题目分析
    3. 3.3. 标程
  4. 4. D. Insert a Progression
    1. 4.1. 题目描述
    2. 4.2. 题目分析
    3. 4.3. 标程
  5. 5. E. Replace With the Previous, Minimize
    1. 5.1. 题目描述
    2. 5.2. 题目分析
    3. 5.3. 标程
|