Codeforces Round #658 (Div. 2)（BCD）

题目链接：https://codeforces.com/contest/1382

B. Sequential Nim（博弈）

C. Prefix Flip （思维题）

D. Unmerge（背包DP）

B. Sequential Nim

题目大意：给你n堆石子，每堆$a_i$个，你必须按顺序从左到右取，每次取至少一个，最多$a_i$个，问先手胜利还是后手。$nleq 10^5 a_ileq 10^9$

Example

input

7
3
2 5 4
8
1 1 1 1 1 1 1 1
6
1 2 3 4 5 6
6
1 1 2 1 2 2
1
1000000000
5
1 2 2 1 1
3
1 1 1

output

First
Second
Second
First
First
Second
First

emmm，我们先不考虑1的情况，那么先手在最后一堆石子前必然拿走$a_i-1$个石子，然后先手永远是先手，所以先手必胜。

那么如果有一个1呢？我们考虑1出现的位置，有两种情况，1在最前面，这个时候，先手被迫拿走1，那么先手和后手的顺序就会被逆转，先手必败。如果1不在最前面，那么先手一定可以使得在1的前面拿走$a_i$个石子，使得后手被迫拿走1，那么先手还是先手，依然是必胜。

那么接下来似乎就不需要考虑了，通过对1个1的观察我们就可以得出结论了，我们只需要考虑前缀1的个数就行了。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e5+10;

int a[mac];

int main(int argc, char const *argv[])
{
    int t;
    scanf ("%d",&t);
    while (t--){
        int n;
        scanf ("%d",&n);
        for (int i=1; i<=n; i++)
            scanf ("%d",&a[i]);
        int f=1,s=0,cnt=0;
        for (int i=1; i<=n; i++){
            if (a[i]==1) cnt++;
            else break;
        }
        if (cnt&1){
            if (cnt==n) printf("First
");
            else printf("Second
");
        }
        else{
            if (cnt==n) printf("Second
");
            else printf("First
");
        }
    }
    return 0;
}

View Code

C. Prefix Flip

题目大意：给你2个长度为$n$的01串，你需要将第一个01串通过变换变成第二个01串。你可以进行的变换为，选择一个前缀长度，然后将其元素翻转，然后再翻转其位置。比如说001001，选择长度为3的前缀，那么会得到011001。问你s1可以通过几步得到s2，并输出每次选择的前缀长度。$|S|leq 10^5$，步数必须在$2n$以内

Example

input

output

3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

此题最为麻烦的就是要考虑位置的翻转，这样翻转之后整个过程就变得非常不可控。所以我们想如何将这个位置翻转从考虑的因素中剔除掉。我们能想到，对于几个相同的元素进行翻转，他们的位置翻转是没有意义的。那么我们就可以考虑直接将串s1全部变成相同的元素，然后再将s1变为s2。这个过程所需要的步数一定是在$2n$以内的。

我们从前往后跑，然后相邻的两个元素不一样，那么我们就将前面的元素全部翻转，那么就可以得到了该位置下前缀的所有元素都一样了。那么最多执行n-1次。

接下来从后往前跑，如果s1和s2的该位置不一样，我们直接将该位置的前缀翻转就可以了。最多执行n次。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e5+10;
const int inf=1e9+10;

char a[mac],b[mac];

int main(int argc, char const *argv[])
{
    int t;
    scanf ("%d",&t);
    while (t--){
        int n;
        scanf ("%d",&n);
        scanf ("%s",a+1);
        scanf ("%s",b+1);
        vector<int>ans;
        for (int i=2; i<=n; i++){
            if (a[i]!=a[i-1]) ans.push_back(i-1);
        }
        char last=a[n];
        for (int i=n; i>=1; i--){
            if (b[i]!=last){
                ans.push_back(i);
                last=last=='0'?'1':'0';
            }
        }
        printf("%d ",ans.size());
        for (int i=0; i<ans.size(); i++)
            printf("%d ",ans[i]);
        printf("
");

    }
    return 0;
}

View Code

D. Unmerge

题目大意：有两个长度为n的集合，进行merge操作，每次取两个集合最前面的最小值，那么可以得到一个新的长度为2n的集合，现在给你这个长度为2n的集合，问你是否存在着2个长度为n的集合通过merge操作得到它。$n<leq 2000$

Example

input

6
2
2 3 1 4
2
3 1 2 4
4
3 2 6 1 5 7 8 4
3
1 2 3 4 5 6
4
6 1 3 7 4 5 8 2
6
4 3 2 5 1 11 9 12 8 6 10 7

output

YES
NO
YES
YES
NO
NO

emmm，我们将这个序列进行分段，找到一个数后面第一个比他大的元素进行分段，比如2 3 1 4可以分为2| 3 1| 4。然后跑对每段的长度跑01背包就可以了，最后判断一下背包的价值是否为n。

至于为什么这样分的。。。我们可以观察，对于两个集合（我们可以看做是一个栈），每次出来的都是栈顶最小的元素，那么如果先出来了个17，那么后面出来的元素，如果比17来得小，那么一定是和17同栈的，因为，如果不是同栈的话出来的就是将17踢掉的那个元素，它肯定会大于17的，所以我们可以这样来分段。

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=4e3+10;

int len[mac],a[mac],dp[mac];

int main(int argc, char const *argv[])
{
    int t;
    scanf ("%d",&t);
    while (t--){
        int n;
        scanf ("%d",&n);
        for (int i=1; i<=2*n; i++)
            scanf ("%d",&a[i]);
        int cnt=1,mx=a[1],num=1;
        len[cnt]=1;
        for (int i=2; i<=2*n; i++){
            if (a[i]>mx) len[cnt++]=num,num=1,mx=a[i];
            else num++;
        }
        for (int i=0; i<=2*n; i++) dp[i]=0;
        for (int i=1; i<cnt; i++)
            for (int j=n; j>=len[i]; j--)
                dp[j]=max(dp[j],dp[j-len[i]]+len[i]);
        if (dp[n]==n) printf("YES
");
        else printf("NO
");
    }
    return 0;
}

View Code

路漫漫兮