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

实时录频在这里

A. Number Transformation

题目描述

1

题目分析

就是说让你找到两个数 $a,b$,使得 $x\times a^b=y$ 这里可以使得 $b=1$ 然后就判断一下 $y\ mod\ x=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
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");}
using namespace std;

void solve(){
int x,y;
cin>>x>>y;
if(y%x==0){
printf("1 %d\n",y/x);
}
else{
puts("0 0");
}
}
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. Dictionary

题目描述

2

题目分析

就是说输出一个字符串的字典序,字符串只有2个字符,然后两个字符应该不能一样,这样的话直接用公式就好了,如果能一样,这个公式应该是 $(a[0]-‘a’)\times 26+a[1]-‘a’$ 的,这里既然不能一样那就都减一就好了,但是要注意,如果 $a[1]$ 不超过 $a[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
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");}
using namespace std;

void solve(){
int x,y;
char s[5];
scanf("%s",s);
printf("%d\n",(s[0]-'a')*25+(s[1]-'a')-(s[1]>s[0])+1);


}
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. Infinite Replacement

题目描述

3

题目分析

就是说一个字符串 $s$ 只包含 $a$,$a$ 可以用另一个字符串 $t$ 替代,问有多少种替换的结果,替换可以有无限次。

首先不难发现,如果 $t$ ==”$a$” 那么我替换是没有效果的,答案为 $1$。

其次如果 $t$ 不包含 “$a$”,那么对于 $s$ 的每个位置的 “$a$”,有替换和不替换两种选择,答案就是$2^{strlen(s)}$。

只剩下包含”$a$”的长度不为 $1$ 的字符串,可以发现允许进行无限次替换,直接 $-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
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define maxn 200005
#define maxx 40005
#define int long long
#define OK {puts("YES");}
#define NO {puts("NO");}
using namespace std;
char s[maxn],t[maxn];
void solve(){
int x,y;
scanf("%s",s);
scanf("%s",t);
int len=strlen(t);
if(len==1 && t[0]=='a'){
puts("1");
return;
}
int flag=0;
for(int i=0;i<len;i++){
if(t[i]=='a'){
flag=1;
break;
}
}
if(flag){
puts("-1");
}
else{
printf("%lld\n",1ll<<strlen(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;
}

D. A-B-C Sort

题目描述

4

题目分析

过程是这样的:

a->b
选择最后一个元素放在b数组的中间
b->c
选择中间元素放在c数组的后面

相当于这样:
按一定顺序将元素压入两个栈中,然后分别弹出观察是否能递增。
如果序列长度为偶数,则1,2元素均小于3,4元素,3,4元素均小于5,6元素……
如果为奇数,则1元素需要最小,2,3需要小于,4,5……
模拟一下就ok

标程

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
#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;
int cnt=0,x,y;
if(n%2==1){
scanf("%d",&x);
a[++cnt]=x;
}
for(int i=cnt;i<n;i+=2){
scanf("%d %d",&x,&y);
if(x>y){
a[++cnt]=y;
a[++cnt]=x;
}
else{
a[++cnt]=x;
a[++cnt]=y;
}
}
for(int i=1;i<n;i++){
if(a[i+1]<a[i])NO
}
OK
}
void init(){

}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
init();
while(t--)solve();



return 0;
}

E. Breaking the Wall

题目描述

5

题目分析

这题被杀疯了,结束的时候 $3000AC$ 到现在就剩下 $200$ 多个了,主要是数据锅了。

只需要考虑三种情况,相邻的墙,隔一个的墙和最小两个墙,给你的测试数据很充足,但是实际测试点不行,也不知道这个新写的能不能过。

标程

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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 ans=1e9;
for(int i=1;i<n;i++){//¢ù
int res=0;
int first=a[i],second=a[i+1];
if(first>second)swap(first,second);

res+=second-first;
second-=2*res;
first-=res;
if(first<0){
res=max(a[i]+1,a[i+1]+1)/2;
//printf("%d\n",res);
ans=min(ans,res);
continue;
}
int times=first/3;
res+=times*2;
first-=times*3;
second-=times*3;

//printf("%d %d\n",first,second);
//printf("%d\n",times);
while(first>0||second>0){
if(first<=0){
res+=second/2+second%2;
break;
}
else if(second<=0){
res+=first/2+first%2;
break;
}
else{
if(first>second){
first-=2;
second-=1;
res++;
}
else{
second-=2;
first-=1;
res++;
}
}

}
ans=min(ans,res);

//printf("%d\n",ans);
}
//printf("%d\n",ans);
for(int i=1;i<n-1;i++){//¢ú
int first=min(a[i],a[i+2]);
int second=max(a[i],a[i+2]);

ans=min(ans,first+(second-first)/2+(second-first)%2);
//printf("%d\n",ans);
}
//printf("%d\n",ans);
sort(a+1,a+1+n);
ans=min(ans,(a[1]/2+a[1]%2+a[2]/2+a[2]%2));
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;
}

F. Desktop Rearrangement

题目描述

6

题目分析

就是给你一个桌面,每次询问的时候添加或减少图标,询问需要几次排列好图标。这个直接暴力模拟就可以了,首先计算出有多少个图标,然后把它拍成一列,图标下标在这个值数量之外的数目就是答案了。每次增加或减少最多对答案产生 $1$ 的影响,所以也不难。就是这个x,y,比赛的时候总是搞反,最后发现这个x是行号,y是列号。

标程

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
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define maxn 2000005
#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,m,q;
cin>>n>>m>>q;
int cnt=0;
string s;
for(int i=0;i<n;i++){
cin>>s;
for(int j=0;j<m;j++){
if(s[j]=='*'){
a[j*n+i+1]=1;
cnt++;
}
}
}
int ans=0;
for(int i=1;i<=n*m;i++){
if(i<=cnt&&a[i]==0){
ans++;
}
}
// for(int i=1;i<=n*m;i++){
// putchar('0'+a[i]);
// }putchar(10);
//printf("%d\n",ans);;
while(q--){
int y,x;
scanf("%d %d",&y,&x);

int pos=(x-1)*n+y;
if(a[pos]==0){
//printf("pos %d appear\n",pos);

cnt++;
int flag=0;
if(a[cnt]==1){
flag--;
}
if(pos>cnt){
flag++;
}
a[pos]=1;
ans+=flag;

}
else{
//printf("pos %d disappear\n",pos);


int flag=0;
if(a[cnt]==1){
flag++;
}
cnt--;
if(pos>cnt){
flag--;
}
a[pos]=0;
ans+=flag;

}
// for(int i=1;i<=n*m;i++){
// putchar('0'+a[i]);
// }putchar(10);
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;
}

总结

赛中做出五道,赛后被叉一道还行吧,反正ABCD写的挺快的,签到手速已经在稳步提升。