HDU3537

HDU3537
 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<map>
 5 #include<string>
 6 using namespace std;
 7 map<string,int>vis;
 8 bool obious(int x){
 9     int cnt = 0;
10     while(x>0){
11         if(x%2)cnt++;
12         x /= 2;
13     }
14     if(cnt%2) return true;
15     return false;
16 }
17 int string_int(string x){
18     int ans = 0;
19     for(int i = 0;i<x.size();i++){
20         ans = ans*10+x[i]-0;
21     }
22 //    cout<<"ans:"<<ans<<endl;
23     return ans;
24 }
25 int main()
26 {
27 #ifdef LOCALL
28 //    freopen("in.txt","r",stdin);
29     //freopen("out2.txt","w",stdout);
30 #endif
31     int n;
32     while(cin>>n) {
33         int ans  = 0;
34         vis.clear();
35         if(n == 0){cout<<"Yes\n";continue;}
36         for(int i = 0;i<n;i++){
37             string xx;
38             cin>>xx;
39             if(vis.count(xx))continue;
40             vis[xx] = 1;
41             int x = string_int(xx);
42 //            cout<<"x:"<<x<<"obious:"<<obious(x)<<endl;
43             if(obious(x)){
44                 ans^=2*x;
45             }
46             else ans ^= (2*x+1);
47         }
48         if(ans)cout<<"No\n";
49         else cout<<"Yes\n";
50     }
51     return 0;
52 }
HDU3537

幸好先看了Game Theory,要不然又要哭着找解题报告了……

是Mock Turtles:这类游戏每次可以翻动一个、二个或三个硬币。

本来打表SG也是可以的,可是论文里最精髓的部分在于找了这个SG表的规律。

因为这个规律不像之前那些题目那样那么明显。有兴趣的可以自己先找找规律。

规律是什么呢?

先来看sg表:

Position x 0 1 2 3 4 5 6 7 8 9 10 11 12 13
sg[x] 1 2 4 7 8 11 13 14 16 19 21 22 25 26

 

也许有些同学不清楚这些sg[x]是怎么得来的,那么我再唠叨一下:

  比方说sg[2] : 因为每次可以翻动一个、二个或三个硬币,现在第2个位置是正面(一定要翻的),0,1号位置都是反面,所以下一步可以翻到的局面有:反反反(终态,P,sg = 0),正反反(sg = sg[0] = 1),反正反(sg = sg[1] = 2),正正反。

  现在“正正反”的sg是多少呢?

  还记得我们一开始说的(额……在平等博弈那篇里),关于翻硬币的问题,我们可以化为每个正面硬币单独存在的局势的异或和,所以正正反 = 正 + 反正 = sg[0]+sg[1] = 3(这里的加是二进制加,就是异或)。

  根据sg函数的性质,我们知道最小没有出现的自然数就是4了,所以sg[2] = 4。

 

  再分析个sg[3]的:

  0 0 0 1 可以变为 0 0 0 0( sg = 0), 1 0 0 0(sg[0] = 1) ,0 1 0 0(sg[1] = 2), 0 0 1 0(sg[2] = 4) , 1 1 0 0(sg[0]^sg[1] = 3), 0 1 1 0(sg[1]^sg[2] = 6),1 0 1 0(sg[0]^sg[2] = 5).

  所以sg[3] = 7.

   以上。

 

然后,现在我们知道了SG表(嘛……之后说说怎么计算机打表的,人工打累死……)

然后最精彩的部分来了:

  我们先定义2个代名词:

        1.  odious:二进制表示中1的个数为奇数

        2.  evil: 二进制表示中1的个数为偶数

  结论是:

    if(2x) == odious,sg(x) = 2x;

    if(2x) == evil,sg(x) = 2x+1.

  而且sg值是odious数字的连续升序(额,不知道怎么准确描述,自创词汇,就是说sg[x]和sg[x-1]之间没有其他的odious数了)。

     额……证明基于一个事实(为什么是事实,反证一下就清楚了):(这个事实重要啊!这是证明的核心!

                                                      evil^evil=odious^odious=evil

                                                      evil^odious=odious^evil=odious

  + 数学归纳法。

  证明:

  目标:证明sg值是odious数字的连续升序。

  具体实现(不严谨版):

    1、假设在位置x左边的所有位置的sg值满足这个性质

    2、目标转变:企图证明,x位置的sg值就是下一个obious数。

        首先,根据规则,x这个位置的硬币肯定要翻过来。

      然后如果我们只翻这一位,0;——也就是说0这个数被排除,不会是sg[x](事实由于0是evil数,所以没什么关系)。

      如果翻2位,也就是说变成了翻x左边的一位(因为x一定要被翻成反面)——把左边一位的反面翻成正面,就成了sg[x-i]{x=>i>0},而由1知,这个数sg[x-i]一定是一个odious数(而且是出现过的,就是说不会是下一位)。然后i是从1到x,所以,之前所有的odious数都会出现过。

        如果翻3为,同理,变成了2个odious数,而odious^odious=evil,所以不会影响下一个odious数的出现。

    综上得证。(PS:有些同学可能会问,为什么“之前所有的odious数都会出现”,现在出现的就一定是下一个odious数,下2个,下3个不行么?答案是不行的,为什么呢?不要忘了我们关于SG函数的定义,SG函数定义的时候就说了“最小没有出现的(自然)数”,如果是现在的sg[x]是“下2个”,而且又满足上面2的推理,那就说明“下一个”还没有出现,那sg[x]应该是“下1个”的值才对,这和假设的“sg[x]是“下2个””矛盾。所以一定是“下一个”……)

    

MT与NIM:

  我看论文的时候发现其实这个Mock Turtles很像Multi-SG(就是可以选择把1堆分成2堆的那个)。

  MT可以允许每次翻1、2、3个。

  只翻1个,就到终态,就是nim里的,取一堆,全部取完了。

  只翻2个,就是nim里的取一堆,但是没取完。

  只翻3个,就是nim里的,选一堆,不取石子,而是把这堆分成2个小堆。——当然,这两个小堆怎么分,就不是按照平时的整数拆成2个整数相加那么直接了。

 

最后说说怎么打表吧,打个小点的表,那就按照我上面说的与NIM的类比进行DFS打表吧……(就说说……给个方向……

 

番外:

  窝: 可是证明好像还是没有说为什么

    “if(2x) == odious,sg(x) = 2x;

    if(2x) == evil,sg(x) = 2x+1.”

    是正确的吧!

  Big窝:嘛…… Think!骚年!

  窝:   可是那个证明只说明了SG函数的值是odious数的……额……连续……升序啊……

  Big窝:为什么要考虑2x?除了找到规律之外,当我们知道结论之后,能知道为什么吗?

  窝: 恩……我想是因为odious数的定义吧!奇数个1。……一个自然数写成2进制,其中1的个数不是奇数,就是偶数,我想所以才会是和2x有关的规律吧。

  Big窝: 然后?

  窝: 然后?!然后就求2x是不是odious数!如果不是,+1肯定是的!

  Big窝:……这样就证明了?

  窝:(点头)

  Big窝:嘛……你说“2x是不是odious数!如果不是,+1肯定是的!”……我觉得你说的最大的漏洞在于,我们关于‘SG函数的值是odious数的连续升序“本来就是

   “if(2x) == odious,sg(x) = 2x;

    if(2x) == evil,sg(x) = 2x+1.”

  这个结论推导出来的,现在你用这个结论去证明它的前提,你觉得正确性如何?

  窝: ……

  Big窝:不过你说的想法,可以作为以后思考后猜想的方向,嘛……也不是完全没有用的……

  窝:……

  

HDU3537

上一篇:解Bug之路-串包Bug


下一篇:一般处理程序处理图片(动态给图片加上水印、保存缩略图)