频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDOJ 3537 Daizhenyang's Coin (翻硬币游戏)
2012-08-12 09:53:00           
收藏   我要投稿

每次可以翻动一个、二个或三个硬币。(Mock Turtles游戏)
初始编号从0开始。
当N==1时,硬币为:正,先手必胜,所以sg[0]=1.
当N==2时,硬币为:反正,先手必赢,先手操作后可能为:反反或正反,方案数为2,所以sg[1]=2。
当N==3时,硬币为:反反正,先手必赢,先手操作后可能为:反反反、反正反、正反正、正正反,方案数为4,所以sg[2]=4。
位置x:0  1  2  3  4   5    6   7    8     9  10  11  12  13  14...
sg[x]:  1  2  4  7  8  11 13 14  16  19  21  22  25  26  28…
看上去sg值为2x或者2x+1。我们称一个非负整数为odious,当且仅当该数的二进制形式的1出现的次数是奇数,否则称作evil。所以1,2,4,7是odious因为它们的二进制形式是1,10,100,111.而0,3,5,6是evil,因为它们的二进制形式是0,11,101,110。而上面那个表中,貌似sg值都是odious数。所以当2x为odious时,sg值是2x,当2x是evil时,sg值是2x+1.
这样怎么证明呢?我们会发现发现,
                                                      evil^evil=odious^odious=evil
                                                      evil^odious=odious^evil=odious
假设刚才的假说是成立的,我们想证明下一个sg值为下一个odious数。注意到我们总能够在第x位置翻转硬币到达sg为0的情况;通过翻转第x位置的硬币和两个其它硬币,我们可以移动到所有较小的evil数,因为每个非零的evil数都可以由两个odious数异或得到;但是我们不能移动到下一个odious数,因为任何两个odious数的异或都是evil数。
 
假设在一个Mock Turtles游戏中的首正硬币位置x1,x2,…,xn是个P局面,即sg[x1]^…^sg[xn]=0.那么无可置疑的是n必定是偶数,因为奇数个odious数的异或是odious数,不可能等于0。而由上面可知sg[x]是2x或者2x+1,sg[x]又是偶数个,那么x1^x2^…^xn=0。相反,如果x1^x2^…^xn=0且n是偶数,那么sg[x1]^…^sg[xn]=0。这个如果不太理解的话,我们可以先这么看下。2x在二进制当中相当于把x全部左移一位,然后补零,比如说2的二进制是10,那么4的二进制就是100。而2x+1在二进制当中相当于把x全部左移一位,然后补1,比如说2的二进制是10,5的二进制是101。现在看下sg[x1]^…^sg[xn]=0,因为sg[x]是2x或者2x+1,所以式子中的2x+1必须是偶数个(因为2x的最后一位都是0,2x+1的最后一位都是1,要最后异或为0,2x+1必须出现偶数次)。实际上的情况可能是这样的:

MT游戏当中的P局面是拥有偶数堆石子的Nim游戏的P局面。

虽然看不太懂,但是有上面的结论就够了,找到每个位置的SG值,然后异或
被戴神的女友坑了,还要排序判重,ORZ。
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<ctime> 
#include<cstring> 
#include<cmath> 
#include<algorithm> 
#include<cstdlib> 
#include<vector> 
#define C    240 
#define TIME 10 
#define inf 1<<25 
#define LL long long 
using namespace std; 
int main(){ 
    int n,a[100]; 
    while(scanf("%d",&n)!=EOF){ 
        int ret=0,k; 
        if(n==0){ 
            puts("Yes"); 
            continue; 
        } 
        for(int i=0;i<n;i++) 
            scanf("%d",&a[i]); 
        sort(a,a+n); 
        int len=1; 
        for(int i=1;i<n;i++) 
            if(a[i]!=a[len-1]) 
                a[len++]=a[i]; 
        for(int i=0;i<len;i++){ 
            int k=a[i]; 
            int cnt=0,t=2*k; 
            while(k){ 
                if(k&1) 
                   cnt++; 
                k>>=1; 
            } 
            if(cnt%2==0) 
                ret^=t+1; 
            else 
                ret^=t; 
        } 
        puts(ret?"No":"Yes"); 
    } 
    return 0; 

 作者:ACM_cxlove

点击复制链接 与好友分享!回本站首页
相关TAG标签 硬币
上一篇:C++内存溢出场景1
下一篇:线段树和单调队列优化DP---POJ2373解题报告
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站