Codeforces Round #786 (Div. 3)题解来了
实时录频在这里
题目描述
/1.png)
题目分析
就是说让你找到两个数 $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.png)
题目分析
就是说输出一个字符串的字典序，字符串只有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.png)
题目分析
就是说一个字符串 $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.png)
题目分析
过程是这样的：
a->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 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.png)
题目分析
这题被杀疯了，结束的时候 $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 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;
ans=min(ans,res);
continue;
}
int times=first/3;
res+=times*2;
first-=times*3;
second-=times*3;
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);
}
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);
}
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(){
int t=1;
init();
while(t--)solve();
return 0;
}
|
F. Desktop Rearrangement
题目描述
/6.png)
题目分析
就是给你一个桌面，每次询问的时候添加或减少图标，询问需要几次排列好图标。这个直接暴力模拟就可以了，首先计算出有多少个图标，然后把它拍成一列，图标下标在这个值数量之外的数目就是答案了。每次增加或减少最多对答案产生 $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 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++;
}
}
while(q--){
int y,x;
scanf("%d %d",&y,&x);
int pos=(x-1)*n+y;
if(a[pos]==0){
cnt++;
int flag=0;
if(a[cnt]==1){
flag--;
}
if(pos>cnt){
flag++;
}
a[pos]=1;
ans+=flag;
}
else{
int flag=0;
if(a[cnt]==1){
flag++;
}
cnt--;
if(pos>cnt){
flag--;
}
a[pos]=0;
ans+=flag;
}
printf("%d\n",ans);
}
}
void init(){
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
init();
while(t--)solve();
return 0;
}
|
总结
赛中做出五道，赛后被叉一道还行吧，反正ABCD写的挺快的，签到手速已经在稳步提升。
