Codeforces Round #658 (Div. 2) 题解 A~D

相比上一场的自闭场这场着实舒服啊…

A - Common Subsequence

题意：求a和b的最短公共子序列
思路：找出相同的一个数字就行。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int a[MAX_N];
int b[MAX_N];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int n,m;
        int i,j;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
   
            scanf("%d",&a[i]);
        }
        for(i=1;i<=m;i++)
        {
   
            scanf("%d",&b[i]);
        }
        int ans=0;
        for(i=1;i<=n;i++)
        {
   
            for(j=1;j<=m;j++)
            {
   
                if(a[i]==b[j])
                {
   
                    ans=a[i];
                    break;
                }
                if(ans)
                    break;
            }
        }
        if(ans)
        {
   
            cout<<"YES"<<endl;
            cout<<1<<' '<<ans<<endl;
        }
        else
            cout<<"NO"<<endl;
    }
}

B. Sequential Nim

题意：有几堆石头，现在有两个人比赛，每个人可以轮流在第一个非空的堆里拿走任意个石头，最后没石头拿的人输，已知两人都会采取最佳策略，要求输出谁会赢。
思路：一堆石头可以分为两种情况，即只有1块石头，和有1块以上，如果只有1块石头，那么轮到的人是没有选择权的，必须全部拿完，但是如果有1块以上，那么这个人可以选择拿完这堆，让对方拿下一堆，或者拿到只剩1个，让对方拿最后一个，自己拿下一堆，所以有绝对的决定权，因此可以得出结论：谁先轮到不是1的堆谁就赢，全为1的情况考虑奇偶。

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<iomanip>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<cstdlib>
    #include<string>
    #include<vector>
    #include<list>
    #include<map>
    #include<set>
    #define fi first
    #define se second
    #define pb push_back
    #define me(a,b) memset(a,b,sizeof(a))
    #define INIT() std::ios::sync_with_stdio(false)
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int>P;
    const int MAX_N=200000+5;
    const int MAX_M=100000+5;
    const int INF=0x7fffffff;
    const int inf=1000000000;
    const double EPS=1e-6;
    const ull base=123;
    const ll mod=998244353;
    const double pi=4*atan(1.0);
    int a[MAX_N];
    int main()
    {
   
        int t;
        cin>>t;
        while(t--)
        {
   
            int n;
            scanf("%d",&n);
            int i;
            for(i=1;i<=n;i++)
                scanf("%d",&a[i]);
            int flag=0;
            for(i=1;i<=n;i++)
            {
   
                if(a[i]!=1)
                {
   
                    if(i%2)
                    {
   
                        flag=1;
                    }
                    else
                        flag=2;
                    break;
                }
            }
            if(!flag)
            {
   
                if(n%2)
                {
   
                    cout<<"First"<<endl;
                }
                else
                    cout<<"Second"<<endl;
            }
            else
            {
   
                if(flag==1)
                    cout<<"First"<<endl;
                else
                    cout<<"Second"<<endl;
            }
        }
    }

C1 - Prefix Flip (Easy Version)

题意：给定a,b两个01序列，要求通过数次操作使a等于b。操作为使a的指定长度前缀，01互换，并且倒置。
思路：c1和c2题是一样的，就是数据范围c2卡的更严格，所以按理说c2的ac代码可以直接用来交c1，但本菜鸡不敢跳过c1做c2，怕血本无归，但做完发现其实c1到c2的做法思路是连贯的。由于长的前缀操作会影响到短的，所以我们考虑从后往前看。从后往前遍历，如果a[i]不等于b[i]，那么为了让他们相同必然要进行i长度的操作，但是如果a[1]==b[i]，翻转过来以后依然是不一样的，所以我们可以先进行一次1长度的操作，再进行i长度操作，遍历下来操作数不超过2*n完全符合题目要求的不超过3n，因为本题n不超过1000，可以O(n^2)暴力翻转。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
char a[MAX_N];
char b[MAX_N];
char temp[MAX_N];
vector<int>ans;
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        ans.clear();
        int n;
        scanf("%d",&n);
        scanf("%s",a);
        scanf("%s",b);
        int i,j;
        for(i=n-1;i>=0;i--)
        {
   
            if(a[i]!=b[i])
            {
   
                if(a[0]!=b[i])
                {
   
                    ans.pb(i+1);
                    for(j=0;j<=i;j++)
                    {
   
                        if(a[j]=='0')
                            temp[j]='1';
                        else
                            temp[j]='0';
                    }
                    int pos=0;
                    for(j=i;j>=0;j--)
                    {
   
                        a[j]=temp[pos++];
                    }
                }
                else
                {
   
                    ans.pb(1);
                    if(a[0]=='0')
                        a[0]='1';
                    else
                        a[0]='0';
                    i++;
                    continue;
                }
            }
        }
        cout<<ans.size();
        for(auto i:ans)
        {
   
            cout<<' '<<i;
        }
        cout<<endl;
    }
}

C2 - Prefix Flip (Hard Version)

题意：同上。
思路：较c1的差别是，操作数改为不能超过2n以及n的范围扩大到1e5，操作数我们上一题本来就是2*n，所以方法不用换，现在要考虑如何降低复杂度，容易看出主要消耗复杂度的地方在于倒置操作的处理，所以我们可以先提前放置一个数组，是整个a的n长度操作后的数组。我们这里把一个序列标记为 1 2 3 4 5，那么倒置就是5 4 3 2 1，此时我们倒置前4个，就是2 3 4 5 1，倒置前三个是4 3 2 5 1，所以可以发现每次倒置就是从一个数组跳到另一个数组，并且起点变为上一次操作的末尾数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
char a1[MAX_N];
char a2[MAX_N];
char b[MAX_N];
char temp[MAX_N];
vector<int>ans;
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        ans.clear();
        int n;
        scanf("%d",&n);
        scanf("%s",a1);
        scanf("%s",b);
        int pos=0;
        int i,j;
        for(i=n-1;i>=0;i--)
        {
   
            if(a1[pos++]=='0')
                a2[i]='1';
            else
                a2[i]='0';
        }
        int pos1=0;
        int pos2=0;
        int flag=1;
        for(i=n-1;i>=0;i--)
        {
   
            if(flag==1)
            {
   
                if(a1[pos1+i]!=b[i])
                {
   
                    //pos1=pos2;
                    if(a1[pos1]==b[i])
                    {
   
                        ans.pb(1);
                    }
                    ans.pb(i+1);
                    flag=2;
                    //pos2=pos1;
                    pos2=n-(pos1+i)-1;
                }
 
            }
            else
            {
   
                if(a2[pos2+i]!=b[i])
                {
   
                    //pos2=pos1;
                    if(a2[pos2]==b[i])
                    {
   
                        ans.pb(1);
                    }
                    ans.pb(i+1);
                    flag=1;
                    //pos1=pos2;
                    pos1=n-(pos2+i)-1;
                }
 
            }
        }
        cout<<ans.size();
        for(auto i:ans)
        {
   
            cout<<' '<<i;
        }
        cout<<endl;
    }
}

D - Unmerge

题意：有两个序列，每次将这两个序列开头小的那个元素拿出，放入新序列末尾，最终形成新序列，现在给定该序列，问是否存在原来的两个序列，可以形成这个序列。
思路：通过观察可以看出，当这个序列某一段是递减的，那么这一段必然来自同一序列，那么就可以把这一段看成以连通块，题意就转变为，将多个连通块平均分到两队，用01背包实现。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int a[MAX_N];
vector<int>v;
int dp[MAX_N];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        v.clear();
        int n;
        scanf("%d",&n);
        int i,j;
        n*=2;
        for(i=1;i<=n;i++)
        {
   
            scanf("%d",&a[i]);
        }
        for(i=1;i<=n;i++)
        {
   
            j=i;
            while(a[j]<=a[i]&&j<=n)
                j++;
            v.pb(j-i);
            i=j-1;
        }
        me(dp,0);
        dp[0]=1;
        for(auto i:v)
        {
   
            for(j=n;j>=i;j--)
            {
   
                if(dp[j-i])
                {
   
                    dp[j]=1;
                }
            }
        }
        if(dp[n/2])
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}