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

7

6

9

3

2

1

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;

}