Bluesky

Codeforces#658(Div.2)

2020/7/21 22:35 Codeforces Round #658 (Div. 2)

1382A - Common Subsequence

题目大意：有两串字符串，寻找他们的最小公共子串，找到子串输出 “ YES ” 换行输出子串长度，以及对应子串，若没有公共子串则输出 “ NO “.

解题思路：最短公共子串一定是两字符串相等的一个数，直接循环找到相同的字符即可。

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
#include <bits/stdc++.h>

int a[1009],b[1009];

int main()
{
    int t;
    std::cin>>t;
    while(t--){
        int n,m;
        std::cin>>n>>m;
        for(int i=0;i<n;i++){
            std::cin>>a[i];
        }
        for(int i=0;i<m;i++){
            std::cin>>b[i];
        }
        std::sort(a,a+n);
        std::sort(b,b+m);
        int flag=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i]==b[j]) {
                    std::cout<<"YES"<<"\n";
                    std::cout<<1<<" "<<a[i]<<"\n";
                    flag=1;
                    break;

                }
            }
            if(flag) break;
        }
        if(!flag) std::cout<<"NO"<<"\n";
    }
    return 0;
}

1382B - Sequential Nim

题目大意：有n堆石子 小明和小红轮流在当前不为空的第一堆石子里取任意多个石子，谁先不能取石子就输掉游戏，小明和小红都很聪明，他们做的每次决定都是最佳决定
例如告诉你，有3堆，每堆是2 5 4 这时候是小明赢
有6堆石子 分别是1 2 3 4 5 6是小红赢
小明赢输出 “ First “,小红赢输出 “ Second ”。

解题思路：这个是看谁先掌握主动权，只要看最前面1的个数，因为当一堆只有一个是的时候轮到你，你就必须取他，而大于一时，有主动权的人可以控制下一堆是谁开始取，散落在序列中的1不用考虑因为有主动权的人会安排。若前面连续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
#include <bits/stdc++.h>

int main(){
    int t;
    std::cin>>t;
    while(t--){
        int a[100009];
        int n,flag=1;
        std::cin>>n;
        for(int i=0;i<n;i++){
            std::cin>>a[i];
            if(a[i]!=1) flag=0;
        }
        if(flag){
            if(n%2==0) std::cout<<"Second"<<"\n";
            else std::cout<<"First"<<"\n";
        }else{
             int cnt=0;
             for(int i=0;i<n;i++){
                 if(a[i]==1) cnt++;
                 if(a[i]!=1) break;
             }
            if(cnt%2==0) std::cout<<"First"<<"\n";
            else std::cout<<"Second"<<"\n";
         }

    }
    return 0;
}

1382C1 - Prefix Flip (Easy Version)

题目大意：有两个长度为n的01串 a ，b.现在对a串可以选择a串的前缀k个数进行01反转然后再将前缀前后反转。
例：001011选择前缀长度3，该串将进行下列变化001011——110011——011011.得到011011.
问：如何在3n次内将a串变换为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
#include <bits/stdc++.h>
int a[1009],b[1009];
int main(){
    int t;
    std::cin>>t;
    while(t--){
        int n;
        std::cin>>n;
        for(int i=0;i<n;i++){
            char k;
            std::cin>>k;
            a[i]=k-'0';
        }
        for(int i=0;i<n;i++){
            char k;
            std::cin>>k;
            b[i]=k-'0';
        }
        int sum=0;
        int ans[3009];
        for(int i=n-1;i>=0;i--){
            if(a[0]==b[i]){
                a[0]=1-a[0];
                ans[sum++]=1;
                for(int j=0;j<=i;j++){
                    a[j]=1-a[j];
                }
                std::reverse(a,a+i+1);
                ans[sum++]=i+1;
            }else{
                for(int j=0;j<=i;j++){
                    a[j]=1-a[j];
                }
                std::reverse(a,a+i+1);
                ans[sum++]=i+1;
            }
        }
        std::cout<<sum;
        for(int i=0;i<sum;i++){
            std::cout<<" "<<ans[i];
        }
        std::cout<<"\n";
    }
    return 0;
}

1382C2 - Prefix Flip (Hard Version)

题目大意：和上一题大致相同，字符串长度变大了，条件限制只能用2n次以内将其反转完成，用上一题的解法会TLE毋庸置疑，
下面思考了一种新的解法。

解题思路：我们可以在n次之内将a串变成全为0或全为1的串，也可以在n次内将b串变为全为0或全为1的串。他会变成什么串取决于他的最后一个数，最后他变成的串会是最后一个数的相反数。那么它通过如何的变换才能变成全为0或1的串呢，即当两个相邻的数不一样时，就将下标记录下来，因为我的下标是从0开始的所以我记录i+1恰好代表了前面有几个数字。a串全部反转为0或1之后看看b如果按照同样规律反转最后是0串还是1串，若不同则将a串整体反转一次，接下来将记录下的b的反转下标倒序输出，即可通过反转后的a串获得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
#include <bits/stdc++.h>

int main(){
    int t;
    std::cin>>t;
    while(t--){
        int n;
        std::cin>>n;
        std::string a,b;
        std::cin>>a>>b;
        int t1[100009],t2[100009];
        int sum1=0,sum2=0;
        for(int i=0;i<n-1;i++){
            if(a[i]!=a[i+1]) t1[sum1++]=i+1;
            if(b[i]!=b[i+1]) t2[sum2++]=i+1;
        }
        int temp=0;
        if(a[n-1]!=b[n-1]) temp=1;
        std::cout<<sum1+sum2+temp;
        for(int i=0;i<sum1;i++){
            std::cout<<" "<<t1[i];
        }
        if(temp) std::cout<<" "<<n;
        for(int i=sum2-1;i>=0;i--){
            std::cout<<" "<<t2[i];
        }
        std::cout<<"\n";
    }
    return 0;
}