Codeforces Round #658 (Div. 2)题解ABC(1&2)D

发布于 2020-07-22  0 次阅读


A. Common Subsequence

思路:

数据不是很大,直接vis标记一下在a中出现过的数,然后在b中遇到相同的数记录一下就可以

AC Code:

#include<stdio.h>
int t, n, m, temp, flag;
int a;
int main(){
    scanf("%d", &t);
    while(t--){
        int vis[1009]={0};
        flag=0;
        scanf("%d %d", &n, &m);
        for(int i=0; i<n; i++)  {scanf("%d", &a); vis[a]=1;}
        for(int i=0; i<m; i++){
            scanf("%d", &temp);
            if(vis[temp])
                flag=temp;
        }
        if(flag)    printf("YES\n1 %d\n", flag);
        else    printf("NO\n");
    }
    return 0;
}

B. Sequential Nim

思路:

因为拿石头是从左到右挨个拿,0直接跳过,对于1只需要知道奇偶即可,当遇到第一个>1的位置时,当前人可以选择全拿或者拿到剩一个,这一步就可以让另一个人进入自己的节奏并且获得胜利

AC Code:

#include<stdio.h>
int t, n, m;
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        int idx=-1;
        for(int i=1; i<=n; i++){
            scanf("%d", &m);
            if(m>1 && idx==-1) idx=i;
        }
        if(idx==-1){
            if(n&1)  printf("First\n");
            else    printf("Second\n");
        }
        else{
            if(idx&1)   printf("First\n");
            else     printf("Second\n");
        }        
    }
    return 0;
}

C1. Prefix Flip (Easy Version)

C2. Prefix Flip (Hard Version)

思路:

在Hard中,需要在2n次内将a变成b,所以每个位置的操作次数最多为2,所以可以先将a变成单一字符(0或者1),然后再从后往前处理,如果从前往后的话你调好的位置会被反转,最后再将单一字符的a变成b。

AC Code:

#include<cstdio>
#include<iostream>
using namespace std;
int t, n, c[200009], k;
string a, b;
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        k=0;
        cin>>n;
        cin>>a>>b;
        for(int i=1; i<n; i++){
            if(a[i]!=a[i-1])
                c[k++]=i;
        }
        char temp=a[n-1];
        for(int i=n-1; i>=0; i--){
            if(temp!=b[i]){
                c[k++]=i+1;
                temp=b[i];
            }
        }
        cout<<k<<" ";
        for(int i=0; i<k; i++){
            cout<<c[i]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

D. Unmerge

思路:

首先处理序列p,题目给的是一个合成p的a,b数组,其中一个为空时,为另一个,都非空时选出最左边最小的那个。
所以在处理p的时候考虑目前出现的最大值即可,因为目前最大值是前面的分隔。
例如对于:3 2 6 1 5 7 8 4,可以分成3,2,和6,1,5和7,和8,4四段
对于已经分成小段的序列p,我们只需要考虑能否将这些小段中的部分提出合成一个长度为n的序列(另外一部分自动成n),可以采取状压dp或者01背包的方式解决,价值和重量为每小段的长度,总空间为n,最大价值即为最长的序列,判断该值是否是n即可(即为背包装满,即为序列长为n)。

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x3f3f3f3f
int t, n, a, mx;
int z[4009], k;
// #define TDS_ACM_LOCAL
void solve(){
    cin>>n;
    mx=0, k=0;
    for(int i=0; i<2*n; i++){               //对p分段,只需要记录每个段的起始位置
        cin>>a;
        if(a>mx){
            z[k++]=i;
            mx=a;
        }
    }
    int v[4009]={}, w[4009]={}, dp[4009]={};
    for(int i=1; i<k; i++)                     //价值和重量为每小段的长度(即两个起始位置的差
        v[i-1]=w[i-1]=z[i]-z[i-1];
    for(int i=0; i<k; i++)
        for(int j=n; j>=w[i]; j--)             
            dp[j]=max(dp[j], dp[j-w[i]]+v[i]);
    if(dp[n]==n)    cout<<"YES"<<endl;          //如果背包装满了,即为可以合成长度为n的序列
    else    cout<<"NO"<<endl;
    return ;
}

int main(){
    ios::sync_with_stdio(false);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    cin>>t;
    while(t--)  solve();
    return 0;
}

平平无奇的大学在读本科生