POJ 3553 Light Switching Game 博弈论 nim积 sg函数-白红宇

POJ 3553 Light Switching Game 博弈论 nim积 sg函数

阅读量：5067 次

发布时间：2019-06-12

本文共 1197 字，大约阅读时间需要 3 分钟。

变成三维的nim积。。前面hdu那个算二维nim积的题的函数都不用改，多nim积一次就过了。。。longlong似乎不必要但是还是加上了

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
            7 #include
            
              8 using namespace std; 9 long long n;10 long long sg[21][21]={};11 long long f(long long,long long);12 long long g(long long x,long long y){13 if(sg[x][y]!=-1)return sg[x][y];14 if(!x)return sg[x][y]=1<
             
              >=1;y>>=1;k<<=1;24 }25 k=1;x=x1;y=y1;26 while(x||y){27 t=1<
              
               >=1;y>>=1;k<<=1;32 }return sg[x1][y1]=ans;33 }34 long long f(long long x,long long y){35 if(!x||!y)return 0;36 if(x==1)return y;37 if(y==1)return x;38 long long ans=0;39 for(long long i=x,a=0;i;i>>=1,a++){40 if(!(i&1))continue;41 for(long long j=y,b=0;j;j>>=1,b++){42 if(!(j&1))continue;43 ans^=g(a,b);44 }45 }return ans;46 }47 int main(){48 memset(sg,-1,sizeof(sg));49 while(~scanf("%lld",&n)){50 long long ans=0,x,y,z;51 for(long long i=1;i<=n;i++){52 scanf("%lld%lld%lld",&x,&y,&z);53 ans^=f(z,f(x,y));54 }55 if(ans)printf("No\n");56 else printf("Yes\n");57 }58 return 0;59 }