第一次训练赛-C-阿甘的珠宝

C - 阿甘的珠宝

FZU - 1534

阿甘向来好运连连，他在好心人的带领下发现了基督山伯爵的宝藏。珠宝~~满眼都是珠宝！！！但是守护的神灵对阿甘提出了苛刻的要求，“你要珠宝，必须赢了我再说。”

阿甘要和守护神灵玩这样一个游戏，规则如下：

阿甘眼前有n堆珠宝，n≤10000;
每堆珠宝有mi个，0≤mi≤2^31-1;
每人每轮可以拿走一堆珠宝中2^i个，比如1，2，4，8…..（不能不拿）;
阿甘先拿。
由守护申领决定取到最后一个赢or输。

守护神拥有千年的生命，无比智慧，阿甘是否能赢呢？

Input

多组数据输入。每组数据包括：

一个整数n，接下来n行每行一个整数，表示mi。

第n+1行有一个数0或者1，表示取到最后一个赢或者输。

Output

阿甘能赢则输出一行yes，否则输出no。

Sample Input

Sample Output

yes

这题很是伤人，我开始随便猜猜写写忽然就ac了

然后我仔细一想，有bug，改完之后反而wa了

我寻思着我已经研究半天了估计能看懂百度大佬的算法了，于是去搜，得到了百度第一页唯二的两个代码，仔细研究之后，发现都有bug。

在这里我把现有的几个代码（我的两个版本和百度上的两个代码）和发现的bug都列出来供哪位路过的大神参考。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    int n,m,status;
    int num[3];
    while (~scanf("%d",&n)) {
        fill(num,num+3,0);
        while (n--) {
            scanf("%d",&m);
            num[m%3]++;
        }
        scanf("%d",&status);
        if (num[2]%2)
            printf("yes\n");
        else
            printf(num[1]%2==status?"no\n":"yes\n");
    }
    return 0;
}

这是我的代码1

这个亮出来略惭愧，但反正是ac了，最显眼的bug在于2 2 2 1，意思：两堆石子，每堆两个，简写为（2，2），最后取完输

输出：yes，正确答案：no

ag（阿甘）god（神）

（1）ag：（2，2）→（2，0）；god：（2，0）→（1，0）；阿甘输

（2）ag：（2，2）→（2，1）；god：（2，1）→（0，1）；阿甘输

因此阿甘必败

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    int n,m,status;
    int num[3];
    while (~scanf("%d",&n)) {
        fill(num,num+3,0);
        while (n--) {
            scanf("%d",&m);
            num[m%3]++;
        }
        scanf("%d",&status);
        if (num[2] == 0)
            printf(num[1]%2==status?"no\n":"yes\n");
        else
            printf(num[2]%2||num[2]%2 ? "yes\n" : "no\n");
    }
    return 0;
}

这是我感觉不对之后改的代码，但是wa了，具体推导在最后说，我目前坚持这个算法。

其他代码的bug这里都ok

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int p[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)){
        int cnt = 0;
        for(int i = 0;i < n;i++){
            scanf("%d",p+i);
            if(p[i] > 1)cnt++;
            p[i] %= 3;
        }
        int q,ans = 0;
        scanf("%d",&q);
        for(int i = 0;i < n;i++)
                ans ^= p[i];
        if(q){
            if ((!cnt&&!ans) || (cnt&&ans))
                printf("yes\n");
            else
                printf("no\n");
        }
        else{
            if(ans)
                printf("yes\n");
            else
                printf("no\n");
        }
    }
    return 0;
}

百度代码1

一个较明显的bug是1 9 1输出no，正确答案yes

ag：9→1；神输了，阿甘赢了

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#define Inf 0x7fffffff // 0x 是数字0,而不是字母o
#define N 10001
using namespace std;
typedef long long LL;
int main(){
    int n,unalone,ans,flag,temp,zero;
    while(cin>>n)
    {
        unalone=0,ans=0,zero=0;
        for(int i=0;i<n;i++)
         {
             cin>>temp;
             if(temp>1) unalone++;
             if(temp==0) zero++;
             ans^=(temp%3);
         }
        cin>>flag;
        if(flag ==0)
        {
            if(ans) puts("yes");
            else puts("no");
        }
        else
        {
            if(zero == n) {puts("yes");continue;}
            if((ans==0 && unalone>=2) || (ans && unalone==0))
                puts("no");
            else puts("yes");
        }
    }
    return 0;
}

百度代码2

一个较明显的bug：1 4 1输出yes正确答案no

（1）ag：4→3；god：3→1；阿甘输

（2）ag：4→2；god：2→1；阿甘输

（3）ag：4→0；直接输了

最后说一下我这题的方法思路，首先展示下石子堆数量<2的情况（图的推导略）：

（xy轴：两堆石子的数量；紫色：无意义；

红色：只能保证拿走最后的石子；绿色：只能保证不拿走最后的石子；

黑色：拿不拿走最后石子都能做到；白色：都不能做到）