hdu 3537 翻硬币每次能翻1个或2个或3个

N 枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开始对硬币按1 到N 编号。

第一，游戏者根据某些约束翻硬币，但他所翻动的硬币中，最右边那个硬币的必须是从正面翻到反面。

第二，谁不能翻谁输。

有这样的结论：局面的SG 值为局面中每个正面朝上的棋子单一存在时的SG 值的异或和。即一个有k个硬币朝上，朝上硬币位置分布在的翻硬币游戏中，SG值是等于k个独立的开始时只有一个硬币朝上的翻硬币游戏的SG值异或和。比如THHTTH这个游戏中，2号、3号、6号位是朝上的，它等价于TH、TTH、TTTTTH三个游戏和，即sg[THHTTH]=sg[TH]^sg[TTH]^sg[TTTTTH].我们的重点就可以放在单个硬币朝上时的SG值的求法。

这一题是每次可以翻动一个、二个或三个硬币。

初始编号从0开始。如果先手胜则输出NO
sg[i] 表示第i个位置上为正其余位置为反面

只有一枚硬币时正，先手必胜，则它的后继状态的sg值为0 所以sg[0]=1.
有2枚硬币时反正翻2个后继状态为sg[0] 翻1个后继状态为所以sg[1] = 2
....

Sample Input
0
1 //n
0 //正面朝上硬币的位置
4
0 1 2 3

Sample Output
Yes
No
Yes

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <string>

 # include <cmath>

 # include <queue>

 # include <list>

 # define LL long long

 using namespace std ;

 int a[];

 int SG(int x)

 {

     int tmp = x;

     int cnt = ;

     while(tmp)

     {

         if(tmp&)cnt++;

         tmp>>=;

     }

     if(cnt&)return *x;

     else return *x + ;

 }

 int main()

 {

     int n;

     while(scanf("%d",&n)==)

     {

         for(int i = ;i < n;i++)

             scanf("%d",&a[i]);

         sort(a,a+n);

         n = unique(a,a+n)-a;

         int sum = ;

         for(int i = ;i < n;i++)

             sum ^= SG(a[i]);

         if(sum)printf("No\n");

         else printf("Yes\n");

     }

     return ;

 }

打表找规律
发现 1 2 4 7 8.... 这些的sg值为本身的两倍这些数字的二进制只含有奇数个1 剩余的sg值为本身的2倍+1 （比如0 3 5 6 9这些）

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <string>

 # include <cmath>

 # include <queue>

 # include <list>

 # define LL long long

 using namespace std ;

 int sg[];

 bool vis[];

 int mex(int n) //求N的SG值

 {

     if(sg[n] != -)return sg[n];

     memset(vis,false,sizeof(vis));

     vis[] =  ; //只有1枚硬币，后继必败

     int i , j  ;

     for (i =  ; i < n ; i++)

         vis[mex(i)] =  ;

     for (i =  ; i < n ; i++)

         for (j =  ; j < i ; j++)

             vis[mex(i)^mex(j)] =  ;

     for(i = ;;i++)

         if(vis[i] == false)

         {

             sg[n] = i;

             break;

         }

     return sg[n];

 }

 int main()

 {

     memset(sg,-,sizeof(sg));

     sg[] =  ;

     for(int i = ;i <= ;i++)

         sg[i] = mex(i);

     cout<<sg[]<<" ";

        for(int i=;i<=;i++)

        {

           cout<<sg[i]<<" ";

           if(i%==)

             cout<<endl;

        }

     return ;

 }

巴特西

hdu 3537 翻硬币每次能翻1个或2个或3个

最新文章

热门文章

巴特西

hdu 3537 翻硬币 每次能翻1个 或2个 或3个

最新文章

热门文章

hdu 3537 翻硬币每次能翻1个或2个或3个