题解 P2148 【[SDOI2009]E&D】

~~前面的Dalao们思路感觉不是很清晰啊，打表和代码实现也有点奇怪而不是很简洁~~ 于是蒟蒻补一发题解 先安利蒟蒻仍在施工的[博弈论总结](http://www.cnblogs.com/flashhu/p/8665204.html) 首先根据题目，石子被两两分组了，于是根据SG定理，我们只要求出每一组的SG值再全部异或起来就好啦。 把每一对数看成一个ICG，首先，我们尝试构造游戏的状态转移DAG。把一堆石子拿掉，另一堆任意拆成两堆，等于说由状态$(a,b)$可以转移到$\{(c,d),c+d=a$或$c+d=b\}$ 一眼看不出来这是要干神马。。。。。。然后开始打表。其实打表的方式可以更简单。首先，观察上式，对于每一个a，所有$c+d=a$的$(c,d)$的$SG$值集合我们可以先用一个bitset存起来，这样当我们求$(a,b)$的$SG$值时我们直接将$a$和$b$对应的两个集合并起来再求$mex$就好啦。于是得到了打表代码（bitset实在是太好用啦） ``` #include<cstdio> #include<bitset> #include<iostream> using namespace std; const int N=10,M=N+1;//随便调大小 typedef bitset<M> B; B s[M]; int ans[M][M]; inline int mex(B b){//干什么就不解释了吧 int i=0; while(b[i])++i; return i; } int main(){ int i,j,k; for(i=2;i<=N;++i) for(j=1,k=i-1;k;++j,--k) s[i].set(ans[j][k]=mex(s[j]|s[k]));//枚举合并 for(i=0;i<N;++i)printf("%3d",i);puts(""); for(i=1;i<N;++i){//输出矩阵 printf("%2d:",i); for(j=1;i+j<=N;++j) printf("%3d",ans[i][j]); puts(""); } for(i=1;i<=N;++i){//输出对于每一个a，所有c+d=a的(c,d)的SG值集合 printf("%2d:SG%d ",i,mex(s[i])); cout<<s[i]<<endl; } return 0; } ``` 打出来的答案矩阵 ``` 0: 1 2 3 4 5 6 7 8 9 1: 0 1 0 2 0 1 0 3 0 2: 1 1 2 2 1 1 3 3 3: 0 2 0 2 0 3 0 4: 2 2 2 2 3 3 5: 0 1 0 3 0 6: 1 1 3 3 7: 0 3 0 8: 3 3 9: 0 ``` 怎么看也没看出什么特别的地方 但接着看看对于每一个$a$，所有$c+d=a$的$(c,d)$的SG值集合 ``` 1:SG0 00000000000 2:SG1 00000000001 3:SG0 00000000010 4:SG2 00000000011 5:SG0 00000000100 6:SG1 00000000101 7:SG0 00000000110 8:SG3 00000000111 9:SG0 00000001000 10:SG1 00000001001 ``` 诶，$S_i$等于$i-1$的二进制表示！！（我太弱了，不会证） 那对于询问的每一对数$(i,j)$，直接求$(i-1)\mid(j-1)$（按位或）的二进制的最低的0所在的二进制位，把所有的异或起来就好啦 代码应该很好懂啊，直接位运算搞一搞就行啦 ``` #include<cstdio> #define R register int const int SZ=1<<21; char ibuf[SZ],*pi=ibuf-1; inline int in(){ while(*++pi<'-'); R x=*pi&15; while(*++pi>'-')x*=10,x+=*pi&15; return x; } int main(){ fread(ibuf,1,SZ,stdin); R T=in(),n,x,cnt,ans; while(T--){ ans=0; n=in()>>1; while(n--){ cnt=0; x=(in()-1)|(in()-1); while(x&1)++cnt,x>>=1; ans^=cnt; } puts(ans?"YES":"NO"); } return 0; } ```