codeforces 1382 B C D

B
题意：给n堆石头，有两个人，从前往后拿石头，每次拿的时候只能拿排在前面的堆得石头，可以拿任意的值，但不可以不拿，谁最先拿完最后的那堆石头，谁赢。

思路： 刚开始以为只要确定出1个的堆数就行，但是，并非如此，实际上谁能赢之和在最前面的1的个数有关系，和排在后面的1的个数没有关系。因为只要有一个人能第一次开始拿不是1个的堆的石头，那么，他就能决定第二个人该怎样拿，即使后面还有1出现。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
   int q;
   scanf("%d",&q);
   int n;
   while(q--)
   {
       scanf("%d",&n);
       int x;
       int jud=1;
       int flag=0;
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&x);
           if(x==1) continue;
           else if(flag==0)
           {
              if((i&1))
              {
                  jud=1;
                  flag=1;
              }
              else
              {
                  jud=2;
                  flag=1;
              }
           }
       }
       if(flag==0)
       {
           if(n&1)printf("First\n");
           else printf("Second\n");
       }
       else
       {
           if(jud==1) printf("First\n");
           else printf("Second\n");
       }
   }
   return 0;
}

c1
给两串等长的二进制串，定义一次操作为取第一个串的前i个字符，按位取反，然后翻转。问能否在3*n次操作以内使得第一个串转化为第二个串。并给出具体的操作过程。

思路：可以从前向后一位一位的修改，仔细观察就能发现每次修改也就是和第一位上的数和第i位上的数有关系，而且由于是一位一位修改的，要使当前操作不会影响之前的修改结果。找到这样的操作，每次只是修改了一位的操作，那么，就解决了。当然，也可以从后向前修改，后面的修改的不会被影响，但是需要对前面的串不断的进行翻转操作以进行下一步的判断，否则则会出现错误，而从前向后的则不用，速度较快。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
   int q;
   scanf("%d",&q);
   int n;
   while(q--)
   {
       scanf("%d",&n);
       int x;
       int jud=1;
       int flag=0;
       for(int i=1;i<=n;i++)
       {
           scanf("%d",&x);
           if(x==1) continue;
           else if(flag==0)
           {
              if((i&1))
              {
                  jud=1;
                  flag=1;
              }
              else
              {
                  jud=2;
                  flag=1;
              }
           }
       }
       if(flag==0)
       {
           if(n&1)printf("First\n");
           else printf("Second\n");
       }
       else
       {
           if(jud==1) printf("First\n");
           else printf("Second\n");
       }
   }
   return 0;
}

c2

把上一题的限制改为了在2*n以内，那么111000, 001001, 则有111000->000000, 001001->000000;
把后面的操作过程倒过来和前面的接上就行。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
char s[100005];
char ss[100005];
vector<int>p1;
vector<int>p2;
int main()
{
    int t;
    scanf("%d",&t);
    int n;
    while(t--)
    {
        p1.clear();
        p2.clear();
        scanf("%d",&n);
        scanf("%s",s+1);
        scanf("%s",ss+1);
        int res=0;
        for(int i=1;i<=n-1;i++)
        {
            if(s[i]!=s[i+1])
            {
                res++;
                p1.push_back(i);
            }
        }
        if(s[n]=='1')
        {
            res++;
            p1.push_back(n);
        }
        for(int i=1;i<=n-1;i++)
        {
            if(ss[i]!=ss[i+1])
            {
                res++;
                p2.push_back(i);
            }
        }
        if(ss[n]=='1')
        {
            res++;
            p2.push_back(n);
        }
        printf("%d ",res);
        for(int i=0;i<p1.size();i++)
        {
            printf("%d ",p1[i]);
        }
        for(int i=p2.size()-1;i>=0;i--)
        {
            printf("%d ",p2[i]);
        }
        printf("\n");
    }
    return 0;
}

D
题意：给出一串长度为2*n的一串数，问是否能把它拆成两串长度为n的数，使得这两串长度为n的数在定义的规则下能够组成原来的那串数。规则是这样的，
a1,a2,a3,…,
b1,b2,b3…,
a1<b1 那么组合时a1 +(a剩下的数与b组合）。

思路：
假如这串数为6 1 3 7 4 5 8 2，
那么这串数能拆成6 1 3,7 4 5,8 2，这三段数，那么接下来的事情就是看这三段数中的几段能否组成一个为n长度的数。如果能组成的话，仔细观察会发现实际上只要能凑出长度为n的串来，就一定有办法构造出另一个串使之按规则正确的构造出2*n的串，也就是说这要能凑出长度为n的一个串，那么就一定能找出这样的两个串来，和其他因素没有关系。
接下来的问题就是判断用现有的串能否凑出长度为n的串来。那么设vis[i]表示长度为i的串能凑出，结合dp,判断vis[n]的值就能判断长度为n的串能否凑出。

网上大神的代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int t, n, p[2 * N], a[N];
bool vis[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n;
        int mx = 0;
        vector<int> ind;
        for(int i = 1; i <= 2 * n; i++)
        {
            cin >> p[i];
            if(p[i] > mx)
            {
                mx = p[i];
                ind.push_back(i);
            }
        }
        ind.push_back(2 * n + 1);
        vector<int> lens;
        for(int i = 1; i < (int) ind.size(); i++)
        {
            lens.push_back(ind[i] - ind[i - 1]);
        }
        sort(lens.begin(), lens.end());
        fill(vis, vis + n + 1, false);
        vis[0] = true;
        int m = lens.size();
        for(int k = 0; k < m; k++)
        {
            int r = k;
            while(r < m && lens[r] == lens[k]) r++;
            fill(a, a + n + 1, 0);
            for(int i = lens[k]; i <= n; i++)
            {
                if(!vis[i] && vis[i - lens[k]] && a[i - lens[k]] < r - k)
                {
                    a[i] = a[i - lens[k]] + 1;
                    vis[i] = true;
                }
            }
            k = r - 1;
        }
        cout << (vis[n] ? "YES" : "NO") << '\n';
    }
    return 0;
}

本文地址：https://blog.csdn.net/weixin_45608039/article/details/107525700