Educational Coeforces Round 129(Div.2)题解

icpccodeforces题解

这波 div2 上大分，写波题解。

实况录屏在这

A. Game with Cards

题目描述

1

题目分析

题目的意思就是说，Alice 和 Bob 分别有 n,m 张牌，然后每次出牌不能小于等于上一次的出牌，如果到自己的回合却不能出牌则判负，问如果两人分别先手，谁会赢？这个稍微想一下就能发现我一开始出最大的一定是最优的策略，比的就是最大值谁最大，假设相等那我肯定出最大的那个我必赢，所以无脑比最大就是这题的思路，如果相等那么谁先手谁赢，所以这里就分三种情况：

  1. max1>max2：Alice必赢
  2. max1<max2：Bob必赢
  3. max1==max2：谁先手谁赢

标程

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
using namespace std;
int a[maxn];
char s[maxn];
void solve(){
    int n,x;
    cin>>n;
    int max1=0,max2=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        max1=max(max1,x);
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        max2=max(max2,x);
    }
    if(max1>max2){
        puts("Alice\nAlice");
    }
    else if(max1<max2){
        puts("Bob\nBob");
    }
    else{
        puts("Alice\nBob");
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

B. Card Trick

题目描述

2

题目分析

一个以前经常玩的魔术，就是假装洗牌，实则那张牌在哪里记得清清楚楚。给一个序列，每次操作会把前 k 个值移动到最后去。问经过若干次操作之后第一个牌的值是多少，不难发现如果进行一次操作相当于第 k+1 张牌会变成第一张牌，因为是直接移动，不改变顺序，所以不难想到改题目就是统计所有的操作次数最后对 n 取模得到的下标就是第一张牌的位置。

标程

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
using namespace std;
int a[maxn];
char s[maxn];
void solve(){
    int n,x,op,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d\n",&a[i]);
    }
    cin>>x;
    for(int i=1;i<=x;i++){
        scanf("%d",&op);
        ans+=op;
        ans%=n;
    }
    printf("%d\n",a[ans+1]);
    
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

C. Double Sort

题目描述

3

题目分析

给两个序列，每次一起交换，问最后能否交换成都不递减，且若能则输出交换次数最少的方案。我们直接定义结构体存储两个序列的值再重载小于号，让它严格按 a 递增，相等的情况按 b递增，因为交换次数最少，不难想到用选择排序可以达到交换次数最少的目的。那么我们就先排个序，然后判断 b 的值是否不递减就可以了。

标程

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
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
//int a[maxn];
char s[maxn];
struct A{
    int a,b;
    void in(){
    //    scanf("%d%d",&a,&b);
    }
    bool operator <(const A &q){
        if(a==q.a){
            return b<q.b;
        }
        return a<q.a;
    }
}a[maxn]; 
queue<pair<int,int>>ans;
void solve(){
    int n;
    cin>>n;
    queue<pair<int,int>>().swap(ans);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].a);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].b);
    }
    for(int i=1;i<n;i++){
        int idx=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[idx]){
                idx=j;
            }
        }
        if(idx!=i){
            ans.push({idx,i});
            swap(a[i],a[idx]);
        }
    }
    for(int i=2;i<=n;i++){
        if(a[i-1].b>a[i].b){
            puts("-1");
            return ;
        }
    }
    printf("%d\n",ans.size());
    while(ans.size()){
        auto x=ans.front();
        ans.pop();
        printf("%d %d\n",x.first,x.second);
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

D. Colorful Stamp

题目描述

4

题目分析

这个题，就是说对一个数进行操作，每次可以把这个数的十进制某一位作为乘数乘这个数，即为一次操作。问你最小操作次数使这个数变成十进制 n 位。

这个题的话就直接无脑广搜就好了。

标程

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
#include<bits/stdc++.h>
#define maxn 200005
#define int unsigned long long
using namespace std;
int a[maxn];
char s[maxn];
int target=0;
int ans=40;
queue<pair<int,int>>q;
map<int,int>ma;
int bfs(int now){
    q.push({now,0});
    bool used[10];
    int cnt=0;
    while(q.size()){
        cnt++;
        memset(used,0,sizeof(used));
        int num=q.front().first;
        int step=q.front().second;
        q.pop();
        int m=num;
        if(num>=target){
            //printf("%lld\n",cnt);
            return step;
        }
        while(m){
            int p=m%10;
            if(p!=0&&p!=1&&!used[p]){
                used[p]=1;
                if(ma[p*num]==1)continue;
                ma[p*num]=1;
                q.push({p*num,step+1});
            }
            m/=10;
        }
    }
    return -1;
    
}
 
void solve(){
    unsigned long long n,x;
    cin>>n>>x;
    target=1;
    for(int i=1;i<n;i++){
        target*=10;
    }
    int ans=bfs(x);
    printf("%lld\n",ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    //cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

In The End

这波应该是手速场，手速快就是上大分，继上一次罚时爆炸之后这场没有一点罚时，挺好的，刚刚掉蓝一下给加回来了。

5

6

100分！

本文标题:Educational Coeforces Round 129(Div.2)题解

文章作者:xia0ji233

发布时间:2022-05-24, 22:00:00

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

原始链接:http://example.com/2022/05/24/Educational%20Codeforces%20Round%20129(Div.2)/

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

文章目录
  1. 1. A. Game with Cards
    1. 1.1. 题目描述
    2. 1.2. 题目分析
    3. 1.3. 标程
  2. 2. B. Card Trick
    1. 2.1. 题目描述
    2. 2.2. 题目分析
    3. 2.3. 标程
  3. 3. C. Double Sort
    1. 3.1. 题目描述
    2. 3.2. 题目分析
    3. 3.3. 标程
  4. 4. D. Colorful Stamp
    1. 4.1. 题目描述
    2. 4.2. 题目分析
    3. 4.3. 标程
  5. 5. In The End
|