SG函数

 1 //BZOJ 1874 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<iostream> 6 #include<algorithm> 7 #define rep(i,n) for(int i=0;i<n;++i) 8 #define F(i,j,n) for(int i=j;i<=n;++i) 9 #define D(i,j,n) for(int i=j;i>=n;--i)10 using namespace std;11 const int N=1010;12 #define debug13 int n,m,a[11],b[11],SG[N];14 bool mark[N];15 void calsg(){16     F(i,1,1000){17         memset(mark,0,sizeof mark);18         F(j,1,m) if (i-b[j]>=0) 19             mark[SG[i-b[j]]]=1;//利用SG函数原本的定义20         //i的后继状态即为 i-b[j]21         //SG[i-b[j]]为后继状态到不了的状态22         //所以那个状态i也到不了 23         F(j,0,10) if (!mark[j]) {SG[i]=j; break;}24     }25 }26 27 int main(){28     #ifndef ONLINE_JUDGE29     freopen("file.in","r",stdin);30     #endif31     scanf("%d",&n);32     F(i,1,n) scanf("%d",&a[i]);33     scanf("%d",&m);34     F(i,1,m) scanf("%d",&b[i]);35     calsg();36     37     int temp=0;38     F(i,1,n) temp^=SG[a[i]];39     40     if (temp){41         printf("YES\n");42         F(i,1,n)43             F(j,1,m)44                 if(SG[a[i]-b[j]]==(temp^SG[a[i]])){45                     printf("%d %d\n",i,b[j]);46                     return 0;47                 }48         }49     else printf("NO\n");50     return 0;51 }