CF293A

tanghairong · 2022-10-03 20:51:51 · 题解

显然取到更多 1 的一定更大。

考虑在什么情况下能判定谁的 1 更多。

设第一行的第 i 个数为 a_i ，第二行的为 b_i ，小A拿到的 1 的个数为 sum1 ，小B的为 sum2 。

Step 1 第一轮取

优先考虑 a_i=b_i=1 的，统计个数 num ，若为偶数，可直接抵消，若为奇数， sum1 加一

Question ：为什么优先 a_i=b_i=1 ？

Answer ：因为这样不仅给自己的 sum 加了一个，还使别人少了一个，相当于取一次赚两个，当然优先。

Step 2 第二轮取

接下来分析 a_i=1 或 b_i=1 的情况（两个只有 1 个是 1），设 p ，若是小A取，则 p=1 ，若是小B取，则 p=2 ，可分 4 种情况。

Question：为什么第 2 种情况和第 3 种情况对自己的 sum 没有贡献但也可以与第 1 种情况和第 4 种情况同级处理呢？

Answer：因为如果我取了这个之后，别人就不能取，而这个位置别人是 1 ，所以相当于使别人少了一个 1 的可能（也就相当于是有利于自己了）。

Step 3 代码

另外如果还有问题的话就看我的代码吧，个人觉得注释还比较详尽。

code ：

#include<iostream>
using namespace std;
bool a[2000005],b[2000005],bj[2000005];
//注意数组要开两倍，因为有2*n个数据！！！
int main(){
    int n,num=0,sum1=0,sum2=0;
    cin>>n;
    n*=2;
    //在这里先乘，后面直接用n就可以了
    for(int i=1;i<=n;i++){char c;cin>>c;a[i]=c-'0';}
    for(int i=1;i<=n;i++){char c;cin>>c;b[i]=c-'0';}
    //注意输入没有空格，所以要用char转换一下
    for(int i=1;i<=n;i++){
        if(a[i]==1&&b[i]==1){num++;bj[i]=1;}
        //这里一定要标记已取，要不然会在下面重复取
    }
    if(num%2==1)sum1++;
    int p=num%2+1;
    //若num为奇数，则p=2，即小B先取；若num为偶数，则p=1，即小A先取
    for(int i=1;i<=n;i++){
        if(bj[i]==1)continue;
        if(p==1&&a[i]==1){sum1++;bj[i]=1;p=2;}
        if(p==1&&b[i]==1){bj[i]=1;p=2;}
        if(p==2&&a[i]==1){bj[i]=1;p=1;}
        if(p==2&&b[i]==1){sum2++;bj[i]=1;p=1;}
        //四种情况，一一讨论
    }
    if(sum1>sum2)cout<<"First";
    if(sum1<sum2)cout<<"Second";
    if(sum1==sum2)cout<<"Draw";
    //最后判断，输出结果
    return 0;
}