Codeforces Round 786(Div.3)

icpccodeforces题解

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->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写的挺快的，签到手速已经在稳步提升。

本文标题:Codeforces Round 786(Div.3)

文章作者:xia0ji233

发布时间:2022-05-03, 12:00:00

最后更新:2022-12-26, 18:51:30

原始链接:http://example.com/2022/05/03/Codeforces%20Round%20786(Div.3)/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. A. Number Transformation
    1. 1.1. 题目描述
    2. 1.2. 题目分析
    3. 1.3. 标程
  2. 2. B. Dictionary
    1. 2.1. 题目描述
    2. 2.2. 题目分析
    3. 2.3. 标程
  3. 3. C. Infinite Replacement
    1. 3.1. 题目描述
    2. 3.2. 题目分析
    3. 3.3. 标程
  4. 4. D. A-B-C Sort
    1. 4.1. 题目描述
    2. 4.2. 题目分析
    3. 4.3. 标程
  5. 5. E. Breaking the Wall
    1. 5.1. 题目描述
    2. 5.2. 题目分析
    3. 5.3. 标程
  6. 6. F. Desktop Rearrangement
    1. 6.1. 题目描述
    2. 6.2. 题目分析
    3. 6.3. 标程
  7. 7. 总结
|