`

HDOJ 3537 Daizhenyang's Coin (翻硬币游戏)

阅读更多

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove


每次可以翻动一个、二个或三个硬币。(Mock Turtles游戏)

初始编号从0开始。

N==1时,硬币为:正,先手必胜,所以sg[0]=1.

N==2时,硬币为:反正,先手必赢,先手操作后可能为:反反或正反,方案数为2,所以sg[1]=2

N==3时,硬币为:反反正,先手必赢,先手操作后可能为:反反反、反正反、正反正、正正反,方案数为4,所以sg[2]=4

位置x0 <wbr></wbr> 1 <wbr></wbr> 2 <wbr></wbr> 3 <wbr></wbr> 4 <wbr></wbr> <wbr></wbr> 5 <wbr></wbr> <wbr></wbr> <wbr></wbr> 6 <wbr></wbr> <wbr></wbr> 7 <wbr></wbr> <wbr></wbr> <wbr></wbr> 8 <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> 9 <wbr></wbr> 10 <wbr></wbr> 11 <wbr></wbr> 12 <wbr></wbr> 13 <wbr></wbr> 14...

sg[x] <wbr></wbr> 1 <wbr></wbr> 2 <wbr></wbr> 4 <wbr></wbr> 7 <wbr></wbr> 8 <wbr></wbr> 11 13 14 <wbr></wbr> 16 <wbr></wbr> 19 <wbr></wbr> 21 <wbr></wbr> 22 <wbr></wbr> 25 <wbr></wbr> 26 <wbr></wbr> 28…

看上去sg值为2x或者2x+1。我们称一个非负整数为odious,当且仅当该数的二进制形式的1出现的次数是奇数,否则称作evil。所以1247odious因为它们的二进制形式是1,10,100,111.0,3,5,6evil,因为它们的二进制形式是0,11,101,110。而上面那个表中,貌似sg值都是odious数。所以当2xodious时,sg值是2x,当2xevil时,sg值是2x+1.

这样怎么证明呢?我们会发现发现,

 <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> evil^evil=odious^odious=evil

 <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> <wbr></wbr> evil^odious=odious^evil=odious

假设刚才的假说是成立的,我们想证明下一个sg值为下一个odious数。注意到我们总能够在第x位置翻转硬币到达sg0的情况;通过翻转第x位置的硬币和两个其它硬币,我们可以移动到所有较小的evil数,因为每个非零的evil数都可以由两个odious数异或得到;但是我们不能移动到下一个odious数,因为任何两个odious数的异或都是evil数。

 <wbr></wbr>

假设在一个Mock Turtles游戏中的首正硬币位置x1,x2,…,xn是个P局面,即sg[x1]^^sg[xn]=0.那么无可置疑的是n必定是偶数,因为奇数个odious数的异或是odious数,不可能等于0。而由上面可知sg[x]2x或者2x+1sg[x]又是偶数个,那么x1^x2^^xn=0。相反,如果x1^x2^^xn=0n是偶数,那么sg[x1]^^sg[xn]=0。这个如果不太理解的话,我们可以先这么看下。2x在二进制当中相当于把x全部左移一位,然后补零,比如说2的二进制是10,那么4的二进制就是100。而2x+1在二进制当中相当于把x全部左移一位,然后补1,比如说2的二进制是105的二进制是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。

#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;
}





更多详细信息请查看java教程网 http://www.itchm.com/forum-59-1.html
分享到:
评论

相关推荐

    HDOJ题目分类 HDOJ题目分类

    【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ1002

    ACM ICPC HDOJ1002

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1001标程

    hdoj1001标程

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    HDOJ1003

    ACM ICPC HDOJ1003

    HDOJ 1008

    ACM ICPC HDOJ1008

    HDOJ离线版

    《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    hdoj1002——大整数相加

    - 使用 `scanf` 函数读取字符串,如 `scanf("%s %s", a, b);`,其中 `a` 和 `b` 分别代表两个大整数。 2. **动态规划思想:** - 虽然本题不涉及传统意义上的动态规划,但在处理大整数时,采用了一种类似于动态...

    HDOJ1000

    ACM ICPC HDOJ1000

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    ACM HDOJ 课件

    【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    HDOJ DP题目总结

    一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

Global site tag (gtag.js) - Google Analytics