BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 957 Solved: 394
[Submit][Status][Discuss]
Description
小H和小Z正在玩一个取石子游戏。取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，
每次取石子的个数有限制，谁不能取石子时就会输掉游戏。小H先进行操作，他想问你他是否有必胜策略，如果有
，第一步如何取石子。
Input
输入文件的第一行为石子的堆数N
接下来N行，每行一个数Ai，表示每堆石子的个数接下来一行为每次取石子个数的种类数M
接下来M行，每行一个数Bi，表示每次可以取的石子个数，
输入保证这M个数按照递增顺序排列。
N≤10 Ai≤1000
对于全部数据，M≤10，Bi≤10
Output
输出文件第一行为“YES”或者“NO”，表示小H是否有必胜策略。
若结果为“YES”,则第二行包含两个数，第一个数表示从哪堆石子取，第二个数表示取多少个石子，
若有多种答案，取第一个数最小的答案，
若仍有多种答案，取第二个数最小的答案。
Sample Input
4

2
Sample Output
YES

1 1

Hint

样例中共有四堆石子，石子个数分别为7、6、9、3，每人每次可以从任何一堆石子中取出1个或者2个石子，小H有

必胜策略，事实上只要从第一堆石子中取一个石子即可。

解题思路

简单的SG函数。首先暴力求出所有的SG函数值，异或即可。结果本蒟蒻因为最后输出方案时，
位运算没有加括号调了半天。。

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 15;
const int MAXN = 1005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,f[N],a[N],ans;
int sg[MAXN],MAX=-1;
bool vis[MAXN];

inline void get_SG(){
    for(register int i=1;i<=MAX;i++){
        memset(vis,false,sizeof(vis));
        for(register int j=1;f[j]<=i;j++)
            vis[sg[i-f[j]]]=1;
        for(register int j=0;j<=N;j++)
            if(!vis[j]) {
                sg[i]=j;
                break;
            }
    }
}

int main(){
    memset(f,0x3f,sizeof(f));
    n=rd();
    for(register int i=1;i<=n;i++) a[i]=rd(),MAX=max(a[i],MAX);
    m=rd();
    for(register int i=1;i<=m;i++) f[i]=rd();
    get_SG();
//  for(register int i=1;i<=n;i++) cout<<a[i]<<" "<<sg[a[i]]<<endl;
    for(register int i=1;i<=n;i++) ans^=sg[a[i]];
    if(!ans) puts("NO");
    else {
        puts("YES");
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=m;j++)
                if(a[i]>=f[j] && (sg[a[i]-f[j]]^ans^sg[a[i]])==0){
                    printf("%d %d",i,f[j]);
                    return 0;
                }
    }
    return 0;
}