Educational Codeforces Round 68(Rated for Div.2)

发表于 | 更新于: | 分类于 | | 阅读数

日常掉分

A.Remove a Progression

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    int n,x;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&x);
        printf("%d\n",2*x);
    }
}

B.Yet Another Crosses Problem

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int maxn=5e4+10;
vector<char>mp[maxn];
char s[maxn];
int an[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        getchar();
        for(int i=0; i<n; i++){
            mp[i].clear();
            scanf("%s",&s);
            for(int j=0; j<m; j++){
                mp[i].push_back(s[j]);
            }
        }
        for(int j=0; j<m; j++){
            int jj=0;
            for(int i=0; i<n; i++){
                if(mp[i][j] == '*') jj++;
            }
            an[j]=jj;
        }
        int ans=0x3f3f3f3f;
        for(int i=0; i<n; i++){
            int q=0;
            for(int j=0; j<m; j++){
                if(mp[i][j]=='*') q++;
            }
            int pp=0,pos=-1;
            for(int j=0; j<m; j++){
                if(pp<an[j]){
                    pos=j;
                    pp=an[j];
                }
                else if(pp==an[j]){
                    if(mp[i][j]=='.') pos=j;
                }
            }
            if(pos==-1){
                ans=min(ans,m+n-1-q);
            }
            else{
                if(mp[i][pos]=='*') ans=min(ans,m+n-1-q-pp+1);
                else ans=min(ans,m+n-1-pp-q);
            }
        }
        printf("%d\n",ans);
    }
}

C.From S To T

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=110;
char s[maxn],t[maxn],p[maxn];
int vis[300];
int vi[300];
int v[300];
int main(){
    int tt;
    scanf("%d",&tt);
    while(tt--){
        memset(vis,0,sizeof vis);
        memset(vi,0,sizeof vi);
        memset(v,0,sizeof v);
        scanf("%s %s %s",s,t,p);
        for(int i=0; i<strlen(s); i++){
            vis[s[i]]++;
        }
        for(int i=0; i<strlen(t); i++){
            vi[t[i]]++;
        }
        for(int i=0; i<strlen(p); i++){
            v[p[i]]++;
        }
        bool flag=true;
        int j=0;
        for(int i=0; i<strlen(s); i++){
            if(j==strlen(t)){
                flag=false;
                break;
            }
            for(; j<strlen(t); j++){
                if(t[j] == s[i]){
                    //printf("%c\n",t[j]);
                    break;
                }
                else continue;
            }
            if(t[j]!=s[i]){
                flag=false;
                break;
            }
            else j++;
        }
        for(int i='a'; i<='z'; i++){
            if(vis[i]==vi[i]) continue;
            if(vis[i]<vi[i] && vis[i]+v[i]>=vi[i]){
                v[i]--;
            }
            else{
                flag=false;
                break;
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
}

D.1-2-K Game

题意：给你一堆石子数量为n，你一次只能拿走1或2或k，最后一个没有石子拿的人输（描述与题目说法不一样，本质是一样的）

思路：博弈题。

分情况讨论，首先0是必败态，1，2是必胜态，然后3是必败态…一直到$k$是必胜态。
如果$n<k$，那么我只能拿1或2，根据巴什博弈，当$n \equiv 0(mod \ 3)$必败，否则必胜。

接下来讨论$n \geq k$的情况：

那如果$k \not\equiv 0(mod \ 3)$的话，那么$k$一定是必胜态，$k-1$和$k+1$必有一个必胜态，假设$k\equiv 1(mod \ 3)$，那么$k-1$就是必败态，$k+1$就是必胜态，然后一直下去和前面巴什博弈规律一样，$k\equiv 2(mod \ 3)$也是如此。

那么如果$k\equiv 0(mod \ 3)$的话，$k-1$必胜态，$k$必胜态，$k+1$必败，$k+2$，$k+3$必胜 ……$k+k-1$ 和 $k+k$是必胜态 $2 * k+1$必胜(因为可以拿$k$使得变成必败态)，所以规律就出来了，当$n \equiv k (mod \ (k+1))$就是必胜态，否则就判断n%(k+1)%3​的值，如果等于0，就是必败态，否则就是必胜态。

不会sg函数，只能手推

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=110;
int main(){
    int tt;
    //freopen("in.txt","r",stdin);
    scanf("%d",&tt);
    int cnt=1;
    while(tt--){
        int n,k;
        scanf("%d %d",&n,&k);
        if(n == 0){
            //printf("%d %d %d ",cnt++,n,k);
            puts("Bob");
            continue;
        }
        if(k == n || n<=2){
            //printf("%d %d %d ",cnt++,n,k);
            puts("Alice");
            continue;
        }
        if(n<k||k%3!=0){
            //printf("%d %d %d ",cnt++,n,k);
            if(n%3!=0) puts("Alice");
            else puts("Bob");
            continue;
        }
        else{
            //printf("%d %d %d ",cnt++,n,k);
            int tmp=n%(k+1);
            if(tmp == k) puts("Alice");
            else{
                if(tmp%3==0) puts("Bob");
                else puts("Alice");
            }
        }
    }
}
thanks!