精华内容
下载资源
问答
  • 博弈 SG

    2018-04-09 19:10:28
    1.ACM博弈题,不会的时候觉得难于上青天,会的时候觉得没有比博弈更水的题了; 博弈题看到的第一眼觉得是难题,代码敲完顿觉水题。你可能花半个小时去找规律,然后仅花2分钟敲代码。 2.博弈是单人游...

    转自:https://blog.csdn.net/tomorrowtodie/article/details/52145645

    一、心得体会

    1.ACM博弈题,不会的时候觉得难于上青天,会的时候觉得没有比博弈更水的题了;

    博弈题看到的第一眼觉得是难题,代码敲完顿觉水题。你可能花半个小时去找规律,然后仅花2分钟敲代码。

    2.博弈是单人游戏,也可以说是自己跟自己玩,因为“双方都做出最优决策”这一点限制了,最后的结果不取决

    于你是谁,不取决于你的智商,只取决于你面对的局面

    3.局面,这是博弈里面最最最重要的东西!!!(所谓SG也是指这一局面的SG),博弈是一种不公平的游戏

    因为游戏开始的时候已经结束了,影响你胜负的就是你所面对的局面,因为双方采取最优策略

    故而局面必然会以双方当前对自己最优的路径走下去,所以结局已经确定了

    4.当你面对一个局面的时候如何做出最优的决策呢?你一定是走到了最后一步才确定了胜负,所以当前的局面

    往往需要从最终的局面逆推而来(也就是从一个已知胜负的局面一步步推导其他的局面,有了这样的思想,SG

    也就不那么难理解了)

    5.关于SG:

    入门了博弈的人都知道,博弈里面常常用到一个重要的概念 – SG。但是SG是什么?你去百度的话会有非常专业的解答,

    但是那些所谓的专业绝对让人看的头疼。这里说说我所理解的博弈里面的SG(仅限博弈)

    挑程里是这样解释SG值的:

              除 任意一步所能转移到的子局面的SG值以外最小非负整数

    仔细体会一下这句话,你会发现,这里对SG值的定义是递归定义的!

    当前局面的SG是什么呢?请先去找当前局面的子局面的SG值。

    显然,递归是有一个边界的,SG是一种递归,那么它也是有边界的,

    不难发现,它的边界是没有子局面的局面(也就无法再转移的局面)

    什么样的局面没有子局面呢,也就是胜负已定的局面。在第4点说到,

    当前局面的最优策略是从胜负已定的最终局面逆推来的,这里的SG其实也是

    说了这些,那么SG到底是什么呢?

    联想当年学习递归的一个例子:

    f(n)  =   1         , n = 1

                f(n-1) +1  ,n > 1

    这样一个函数是我们学习递归时的经典例子,你说这里的F到底是什么?其实它不过是一个函数而已。

    SG也是一样,它只是一个函数而已,函数这个词翻译成英语再翻译成中文,就成了“功能、作用”

    那么SG的作用是什么呢?

    举一个最简单的例子:

    有一堆石头数量为n,两个人轮流从石堆拿{a1,a2,a3,……,ak}个石头,先取完所有石头者胜。

    根据前面说的,首先找胜负已定的局面,当n=0的时候,石头被拿完了,败态

    那么sg[0] = 0表示面对0个石头的局面者败,然后根据sg的定义,我们可以求出其他局面的sg值

    (为了使每种局面确保有可以转移的子局面,我们假设{a1,a2,a3……,ak}里面一定有1,例如假设没有1的话

    ,假设为{5,6,7}那么局面4没有可以转移的子局面,这样会出现平局的情况,我们后面再说平局)

    这样可以求出所有局面的sg值,然后sg的作用出来了~

    我们发现,若sg[x] = 0,那么x是败态,这其中很神奇,鶸也说不清楚,只说一下胜态败态的转移

    (其实光理解的话可能还是不知道什么是SG,但是看了后面的题目就能理解了并知道怎么用SG找到游戏的胜态败态了)

    6.胜态与败态:

    之前说了,博弈里面,游戏开始的时候已经结束了,影响你胜负的就是你所面对的局面。

    也就是说,这个局面觉得了你的胜负,我们称能让你走向胜利的局面称为胜态,也是必胜态,专业术语也叫P态(积极的英语单词怎么写?)

    称让你走向失败的状态称为败态,也是必败态,专业也叫N态(消极的英语单词鶸也不会拼。。。)

    有一个很显然的规律:

    只要当前状态可以转移到的状态中有一个是败态,那么当前状态就是胜态。

    如果当前状态可以转移到的所有状态都是胜态,那么当前状态就是败态。

    这两句话互为逆否命题,一眼就看出是对的就不解释了。

    可以胜态败态的角度去理解下SG。

    7.Nim游戏:

    关于这个Nim游戏,百度的话又是一大堆乱七八糟看不下去的东西,

    它的最原始的版本大概是说有N堆石头,{a1,a2,a3……,an}表示每堆的数量,两个人轮流选一个石堆拿若干石头(不能不拿),

    如果轮到某个人时所有的石子堆都已经被拿空了,则判负。

    这个游戏有个非常完美的结论:

    令   s  =  a1^a2^a3….^an(^符号表示异或运算)

    若 s = 0,则此局面为败态,否则为胜态

    对于上面的式子,我们不难发现,当你从一个石堆拿走一些石头(即改变一个ai),一定会发生胜态和败态的转变

    胜态一定会转移成败态,败态也一定有策略转移成胜态

    当这个结论与SG结合,神奇的事发生

    我们发现sg异或和为0的状态也是败态,否则胜态。

    另外,很多游戏都可以转变为Nim的形式,例如POJ 1704(挑程上有讲解)

    8.关于平局:

    我们发现,一个必胜态的获得,必然是因为它可以转移到一个败态,那么是不是说相比于平局我们更倾向于败态呢?

    如果有更多的败态,理论上可以转移出更多的胜态,但是孩子别太天真了啊~

    博弈将“对敌人的仁慈就是对自己的残忍”这句话发挥的淋漓尽致,当你选择败态的时候,对方却不会傻傻按照你的想法给你转移胜态的

    该你输的时候你还是得输,所以,在博弈里的决策,一定要是对自己最有利对对手最不利的策略才是最优策略,、

    也就是说,如果实在不能赢,你一定宁可平局,也不要选择败态。例如今年HDU 多校题5754 里面马的情况

    9.当初关于博弈看了很多但是都只是似懂非懂,只有做多了题才有更多的·体会

    二、博弈做题技巧

    做了个专题:点击打开博弈专题

    题目其实好多都是做过的原题,不过以前都是自己找规律的,这次就是用SG打表找规律,通过这些题目也算是知道怎么使用SG找规律了

    其中的题目大多都是打表找规律,不过也有一些有趣的题目

    PS:题目选自kuangbin 的博弈分类:点击打开链接(难度的话,后面的题都蛮简单,前面的题稍难)

    1.打表找规律题:

    输入n,从1开始,每次乘以2~9的数,谁最先达到n谁胜
    直接上代码,其中solve()函数是打表的过程,找完规律之后直接解决不需要solve,不过为了记录自己的思路,打表的代码也保留了

    1. #include<iostream>  
    2. #include<cstdio>  
    3. #include<cstring>  
    4. #include<set>  
    5. #define mem(a,x) memset(a,x,sizeof(a))  
    6. using namespace std;  
    7. typedef long long ll;  
    8. / 
    9.     败态:  
    10.     10 - 18  
    11.     163 - 324 
    12.     2917 - 5832 
    13.     综上: 
    14.     败态: 
    15.     (9*18^i,18*18^i] 
    16.     i从0开始  
    17. /  
    18. const int N = 100000;   
    19. int sg[N+4];  
    20. void solve()  
    21. {  
    22.     sg[1] = 0;   
    23.     for (int i = 2;i <= N;++i)  
    24.     {  
    25.         set<int>s;  
    26.         for (int j = 2;j <= 9;++j)  
    27.         {  
    28.             int to = i/j;  
    29.             if (i%j)to++;  
    30.             s.insert(sg[to]);   
    31.         }  
    32.         int g = 0;  
    33.         while (s.count(g)) ++g;  
    34.         sg[i] = g;  
    35.     }  
    36.     for (int i = 2000;i <= 9000;++i)   
    37.     {  
    38.         cout<<i<<” ”<<sg[i]<<endl;  
    39.     }   
    40. }  
    41. ll l[10],r[10];  
    42. void init()  
    43. {  
    44.     l[0] = 9,r[0] = 18;  
    45.     for (int i = 1;i <= 9;++i)  
    46.     {  
    47.         l[i] = 18LL*l[i-1];  
    48.         r[i] = 18LL*r[i-1];  
    49.     }  
    50. }   
    51. bool loser(ll x)  
    52. {  
    53.     for (int i = 0;i <= 9;++i)  
    54.     {  
    55.         if (x>l[i]&&x<=r[i]) return 1;  
    56.     }  
    57.     return 0;  
    58. }  
    59. int main()  
    60. {  
    61. //  solve();  
    62.     ll n;init();  
    63.     while (~scanf(“%I64d”,&n))  
    64.     {  
    65.         if (loser(n)) puts(“Ollie wins.”);  
    66.         else puts(“Stan wins.”);  
    67.     }  
    68.     return 0;  
    69. }  
    #include<iostream>

    #include<cstdio> #include<cstring> #include<set> #define mem(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; /* 败态: 10 - 18 163 - 324 2917 - 5832 综上: 败态: (9*18^i,18*18^i] i从0开始 */ const int N = 100000; int sg[N+4]; void solve() { sg[1] = 0; for (int i = 2;i <= N;++i) { set<int>s; for (int j = 2;j <= 9;++j) { int to = i/j; if (i%j)to++; s.insert(sg[to]); } int g = 0; while (s.count(g)) ++g; sg[i] = g; } for (int i = 2000;i <= 9000;++i) { cout<<i<<" "<<sg[i]<<endl; } } ll l[10],r[10]; void init() { l[0] = 9,r[0] = 18; for (int i = 1;i <= 9;++i) { l[i] = 18LL*l[i-1]; r[i] = 18LL*r[i-1]; } } bool loser(ll x) { for (int i = 0;i <= 9;++i) { if (x>l[i]&&x<=r[i]) return 1; } return 0; } int main() { // solve(); ll n;init(); while (~scanf("%I64d",&n)) { if (loser(n)) puts("Ollie wins."); else puts("Stan wins."); } return 0; }

    S - A Multiplication Game

    S题和W题一样的,不说了

    R - 悼念512汶川大地震遇难同胞——选拔志愿者

    和S、W的意思也差不多,不过操作从乘法变成了加法,由于数据小,于是也没有找规律,直接打完所有表把规律存在表里就好

    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. const int N = 10010;  
    25. bool sg[N+4];  
    26. int n,m;  
    27. void turn(int n)//以败态转移  
    28. {  
    29.     for (int i = 1;i <= m;++i)  
    30.     {  
    31.         sg[n+i] = 1;//胜态   
    32.     }  
    33. }   
    34. void solve()  
    35. {  
    36.     mem(sg,0);  
    37.     sg[0] = 0;  
    38.     for (int i = 0;i <= n;++i)  
    39.     {  
    40.         if (sg[i] == 0)//败态  
    41.         {  
    42.             turn(i);  
    43.         }   
    44.     }  
    45. }  
    46. int main()  
    47. {  
    48.     int T;cin>>T;  
    49.     while (T–)  
    50.     {  
    51.         cin>>n>>m;  
    52.         solve();  
    53.         if (sg[n]) puts(“Grass”);  
    54.         else puts(“Rabbit”);  
    55.     }  
    56.     return 0;  
    57. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; const int N = 10010; bool sg[N+4]; int n,m; void turn(int n)//以败态转移 { for (int i = 1;i <= m;++i) { sg[n+i] = 1;//胜态 } } void solve() { mem(sg,0); sg[0] = 0; for (int i = 0;i <= n;++i) { if (sg[i] == 0)//败态 { turn(i); } } } int main() { int T;cin>>T; while (T--) { cin>>n>>m; solve(); if (sg[n]) puts("Grass"); else puts("Rabbit"); } return 0; }
    同样从终态逆推,不过逆推的过程有点麻烦,导致看起来都像模拟了。。。
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. bool isleap(int y)  
    25. {  
    26.     if (y%400==0||(y%4==0&&y%100!=0)) return 1;  
    27.     else return 0;  
    28. }  
    29. struct Date  
    30. {  
    31.     int y,m,d;  
    32.     Date()  
    33.     {  
    34.         y = 2001,m = 11,d = 4;  
    35.     }   
    36.     Date(int y,int m,int d):y(y),m(m),d(d){}   
    37.     bool operator == (const Date &a) const  
    38.     {  
    39.         return y==a.y&&m==a.m&&d==a.d;  
    40.     }  
    41.     bool operator < (const Date &a) const  
    42.     {  
    43.         if (y==a.y)  
    44.         {  
    45.             if (m == a.m) return d<a.d;  
    46.             return m<a.m;  
    47.         }  
    48.         return y<a.y;  
    49.     }  
    50.     Date sub()  
    51.     {  
    52.         d–;  
    53.         if (d == 0)  
    54.         {  
    55.             –m;  
    56.             if (m == 0)  
    57.             {  
    58.                 m = 12;  
    59.                 d = 31;  
    60.                 y–;  
    61.             }  
    62.             else if (m==2)  
    63.             {  
    64.                 if (isleap(y)) d = 29;  
    65.                 else d = 28;  
    66.             }  
    67.             else if (m==1||m==3||m==5||m==7||m==8||m==10||m==12) d = 31;  
    68.             else d = 30;  
    69.         }  
    70.         return *this;  
    71.     }  
    72. } ;  
    73. map<Date,int>sg;  
    74. bool ok(Date x)  
    75. {  
    76.     int m = x.m;  
    77.     int d = x.d;  
    78.     if (m == 2)   
    79.     {  
    80.         if (isleap(x.y)) return d<=29;  
    81.         else return d<=28;   
    82.     }  
    83.     else if (m==1||m==3||m==5||m==7||m==8||m==10||m==12) return d<=31;  
    84.     else return d <= 30;  
    85. }  
    86. void output(Date d)  
    87. {  
    88.     cout<<d.y<<” ”<<d.m<<“ ”<<d.d<<endl;  
    89. }  
    90. void turn(Date n)  
    91. {  
    92.     Date s = n;  
    93.     sg[s.sub()] = 1;  
    94.     Date t = n;  
    95.     t.m–;  
    96.     if (ok(t)) sg[t] = 1;  
    97. }  
    98. void moni()  
    99. {  
    100.     Date d;sg.clear();  
    101.     sg[d] = 0;//败  
    102. //  output(d);  
    103.     Date s(1900,1,1);  
    104.     for (Date i;;i.sub())   
    105.     {  
    106. //      cout<<i.y<<” ”<<i.m<<” ”<<i.d<<endl;   
    107.         if (sg[i] == 0) turn(i);  
    108.         if (i == s) break;  
    109.     }  
    110. }  
    111. int main()  
    112. {  
    113.     moni();  
    114.     int T;cin>>T;  
    115.     while (T–)  
    116.     {  
    117.         Date n;  
    118.         Sint2(n.y,n.m);Sint(n.d);  
    119.         if (sg[n]) puts(“YES”);  
    120.         else puts(“NO”);  
    121.     }  
    122.     return 0;  
    123. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; bool isleap(int y) { if (y%400==0||(y%4==0&&y%100!=0)) return 1; else return 0; } struct Date { int y,m,d; Date() { y = 2001,m = 11,d = 4; } Date(int y,int m,int d):y(y),m(m),d(d){} bool operator == (const Date &a) const { return y==a.y&&m==a.m&&d==a.d; } bool operator < (const Date &a) const { if (y==a.y) { if (m == a.m) return d<a.d; return m<a.m; } return y<a.y; } Date sub() { d--; if (d == 0) { --m; if (m == 0) { m = 12; d = 31; y--; } else if (m==2) { if (isleap(y)) d = 29; else d = 28; } else if (m==1||m==3||m==5||m==7||m==8||m==10||m==12) d = 31; else d = 30; } return *this; } } ; map<Date,int>sg; bool ok(Date x) { int m = x.m; int d = x.d; if (m == 2) { if (isleap(x.y)) return d<=29; else return d<=28; } else if (m==1||m==3||m==5||m==7||m==8||m==10||m==12) return d<=31; else return d <= 30; } void output(Date d) { cout<<d.y<<" "<<d.m<<" "<<d.d<<endl; } void turn(Date n) { Date s = n; sg[s.sub()] = 1; Date t = n; t.m--; if (ok(t)) sg[t] = 1; } void moni() { Date d;sg.clear(); sg[d] = 0;//败 // output(d); Date s(1900,1,1); for (Date i;;i.sub()) { // cout<<i.y<<" "<<i.m<<" "<<i.d<<endl; if (sg[i] == 0) turn(i); if (i == s) break; } } int main() { moni(); int T;cin>>T; while (T--) { Date n; Sint2(n.y,n.m);Sint(n.d); if (sg[n]) puts("YES"); else puts("NO"); } return 0; }

    V - Digital Deletions

    题意是对于一个数字形式的字符串,可以把每一位的数字变小(包括0,不为负),可以删去一个0以及0右边的所有数一起删除,两人轮流操作

    谁移除最后一个数胜

    同样逆推局面推出胜态败态

    逆推的时候操作变成将数字变大,或者在后面补0及其他数字,因为长度不超过6,所以还是很简单的

    1. #include<iostream>  
    2. #include<cstdio>  
    3. #include<cstring>  
    4. #include<string>  
    5. #include<set>  
    6. #include<sstream>  
    7. #include<map>  
    8. #define mem(a,x) memset(a,x,sizeof(a))  
    9. using namespace std;  
    10. typedef long long ll;  
    11. const int N = 1000000;  
    12. bool sg[N+4];  
    13. int dig[10];  
    14. int getdig(int x)  
    15. {  
    16.     int len = 0;  
    17.     while (x)  
    18.     {   
    19.         dig[++len] = x%10;  
    20.         x /= 10;  
    21.     }  
    22.     return len;  
    23. }  
    24. int turntonum(int bit[],int n)  
    25. {  
    26.     int num = 0;  
    27.     for (int i = 1,j = 1;i <= n;++i,j*=10)  
    28.     {  
    29.         num += bit[i]*j;  
    30.     }  
    31.     return num;  
    32. }  
    33. void solve(int n,int i)  
    34. {  
    35.     if (i == 1)  
    36.     {  
    37.         n*=10;  
    38.         for (int j = 0;j <= 9;++j)   
    39.         {  
    40. //          cout<<n+j<<endl;  
    41.             sg[n+j] = 1;  
    42.         }  
    43.     }  
    44.     else if (i == 2)  
    45.     {  
    46.         n*=100;  
    47.         for (int j = 0;j <= 99;++j)   
    48.         {  
    49. //          cout<<n+j<<endl;  
    50.             sg[n+j] = 1;  
    51.         }  
    52.           
    53.     }  
    54.     else if (i == 3)  
    55.     {  
    56.         n*=1000;  
    57.         for (int j = 0;j <= 999;++j)  
    58.         {  
    59. //          cout<<n+j<<endl;  
    60.             sg[n+j] = 1;  
    61.         }  
    62.            
    63.     }  
    64.     else if (i == 4)  
    65.     {  
    66.         n*=10000;  
    67.         for (int j = 0;j <= 9999;++j)   
    68.         {  
    69. //          cout<<n+j<<endl;  
    70.             sg[n+j] = 1;  
    71.         }  
    72.           
    73.     }  
    74. }  
    75. void turn(int n)//n是必败态,所有n可以转移到的状态都是必胜态   
    76. {  
    77.     int len = getdig(n);  
    78.     for (int i = 1;i <= len;++i) //数字变大   
    79.     {  
    80.         for (int j = dig[i]+1;j <= 9;++j)  
    81.         {  
    82.             int d[10];  
    83.             memcpy(d,dig,sizeof(d));  
    84.             d[i] = j;  
    85.             int x = turntonum(d,len);  
    86. //          cout<<x<<endl;  
    87.             sg[x] = 1;  
    88.         }  
    89.     }  
    90.     //加0加数  
    91.     if (len < 6)   
    92.     {  
    93.         n *= 10;//后面加个0  
    94.         sg[n] = 1;  
    95.         int d = 5-len;  
    96.         for (int i = 1;i <= d;++i)  
    97.         {  
    98.             solve(n,i);  
    99.         }  
    100.     }  
    101. }   
    102. void fool()  
    103. {  
    104.     sg[0] = 1;  
    105. //  turn(1);  
    106.     for (int i = 1;i < N;++i)  
    107.     {  
    108.         if (sg[i] == 0) turn(i);  
    109.     }  
    110. }  
    111. int main()  
    112. {  
    113.     fool();  
    114.     string s;  
    115.     while (cin>>s)  
    116.     {  
    117.         if (s[0] == ‘0’) puts(“Yes”);  
    118.         else   
    119.         {  
    120.             stringstream ss(s);  
    121.             int n;  
    122.             ss>>n;  
    123.             if (sg[n]) puts(“Yes”);  
    124.             else puts(“No”);  
    125.         }  
    126.     }  
    127.     return 0;  
    128. }  
    #include<iostream>
    
    
    
    
    
    #include<cstdio> #include<cstring> #include<string> #include<set> #include<sstream> #include<map> #define mem(a,x) memset(a,x,sizeof(a)) using namespace std; typedef long long ll; const int N = 1000000; bool sg[N+4]; int dig[10]; int getdig(int x) { int len = 0; while (x) { dig[++len] = x%10; x /= 10; } return len; } int turntonum(int bit[],int n) { int num = 0; for (int i = 1,j = 1;i <= n;++i,j*=10) { num += bit[i]*j; } return num; } void solve(int n,int i) { if (i == 1) { n*=10; for (int j = 0;j <= 9;++j) { // cout<<n+j<<endl; sg[n+j] = 1; } } else if (i == 2) { n*=100; for (int j = 0;j <= 99;++j) { // cout<<n+j<<endl; sg[n+j] = 1; } } else if (i == 3) { n*=1000; for (int j = 0;j <= 999;++j) { // cout<<n+j<<endl; sg[n+j] = 1; } } else if (i == 4) { n*=10000; for (int j = 0;j <= 9999;++j) { // cout<<n+j<<endl; sg[n+j] = 1; } } } void turn(int n)//n是必败态,所有n可以转移到的状态都是必胜态 { int len = getdig(n); for (int i = 1;i <= len;++i) //数字变大 { for (int j = dig[i]+1;j <= 9;++j) { int d[10]; memcpy(d,dig,sizeof(d)); d[i] = j; int x = turntonum(d,len); // cout<<x<<endl; sg[x] = 1; } } //加0加数 if (len < 6) { n *= 10;//后面加个0 sg[n] = 1; int d = 5-len; for (int i = 1;i <= d;++i) { solve(n,i); } } } void fool() { sg[0] = 1; // turn(1); for (int i = 1;i < N;++i) { if (sg[i] == 0) turn(i); } } int main() { fool(); string s; while (cin>>s) { if (s[0] == '0') puts("Yes"); else { stringstream ss(s); int n; ss>>n; if (sg[n]) puts("Yes"); else puts("No"); } } return 0; }

    M - Play a game

    大胆猜测,小心求证,自己随便玩几种局面就会发现奇败偶胜(代码略)

    1. int n;  
    2. while (cin>>n)  
    3. {  
    4.     if (!n) break;  
    5.     if (n&1) puts(“ailyanlu”);  
    6.     else puts(“8600”);  
    7. }  
        int n;
        while (cin>>n)
        {
            if (!n) break;
            if (n&1) puts("ailyanlu");
            else puts("8600");
        }

    L - Good Luck in CET-4 Everybody!

    依旧简单打表找规律,自己手动找规律也可以,不过为了练习下SG的运用,还是用SG打表(也比手动找规律更快更准)

    具体用SG打表找规律的方法代码中见:

    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. const int N = 1000;  
    25. int sg[N+7];  
    26. void fool()  
    27. {  
    28.     sg[0] = 0;  
    29.     for (int i = 1;i <= N;++i)  
    30.     {  
    31.         set<int>s;  
    32.         s.insert(sg[i-1]);  
    33.         for (int j = 1;j <= 10;++j)  
    34.         {  
    35.             int to = i - (1<<j);  
    36.             if (to < 0) continue;  
    37.             s.insert(sg[to]);  
    38.         }  
    39.         int g = 0;  
    40.         while (s.count(g)) ++g;  
    41.         sg[i] = g;  
    42.     }  
    43.     for (int i = 1;i <= 70;++i)  
    44.     {  
    45.         if (sg[i] == 0) cout<<i<<endl;   
    46. //      cout<<i<<”: ”<<sg[i]<<endl;  
    47.     }  
    48. }  
    49. int main()  
    50. {  
    51. //    fool();  
    52.     int n;  
    53.     while (cin>>n)  
    54.     {  
    55.         if (n%3==0)//败  
    56.         {  
    57.             puts(”Cici”);  
    58.         }   
    59.         else puts(“Kiki”);  
    60.     }  
    61.     return 0;  
    62. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; const int N = 1000; int sg[N+7]; void fool() { sg[0] = 0; for (int i = 1;i <= N;++i) { set<int>s; s.insert(sg[i-1]); for (int j = 1;j <= 10;++j) { int to = i - (1<<j); if (to < 0) continue; s.insert(sg[to]); } int g = 0; while (s.count(g)) ++g; sg[i] = g; } for (int i = 1;i <= 70;++i) { if (sg[i] == 0) cout<<i<<endl; // cout<<i<<": "<<sg[i]<<endl; } } int main() { // fool(); int n; while (cin>>n) { if (n%3==0)//败 { puts("Cici"); } else puts("Kiki"); } return 0; }
    K - kiki’s game
    打表找规律,发现当n和m都是奇数的时候必败,打表代码注释了没删除以供参考
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. const int N = 100;  
    25. int sg[N+4][N+4];  
    26. bool ok(int x,int y)  
    27. {  
    28.     return x>=1&&y>=1;  
    29. }  
    30. void fool()  
    31. {  
    32.     sg[1][1] = 0;  
    33.     for (int i = 1;i <= 70;++i)  
    34.     {  
    35.         for (int j = 1;j <= 70;++j)  
    36.         {  
    37.             if (i == 1&&j == 1) continue;  
    38.             set<int>s;  
    39.             if (ok(i-1,j))  
    40.             {  
    41.                 s.insert(sg[i-1][j]);  
    42.             }  
    43.             if (ok(i,j-1))  
    44.             {  
    45.                 s.insert(sg[i][j-1]);  
    46.             }  
    47.             if (ok(i-1,j-1))  
    48.             {  
    49.                 s.insert(sg[i-1][j-1]);  
    50.             }  
    51.             int g = 0;  
    52.             while(s.count(g)) ++g;  
    53.             sg[i][j] = g;  
    54.         }  
    55.     }  
    56.     for (int i = 1;i <= 20;++i)  
    57.     {  
    58.         for (int j = 1;j <= 20;++j)  
    59.         {  
    60.             if (sg[i][j] == 0)//败态  
    61.             {  
    62.                 cout<<”(“<<i<<“,”<<j<<“)”<< endl;  
    63.             }   
    64.         }  
    65.     }  
    66. }   
    67. int main()  
    68. {  
    69. //    fool();  
    70.     int n,m;  
    71.     while (cin>>n>>m)  
    72.     {  
    73.         if (n==0&&m==0) break;  
    74.         if ((n&1)&&(m&1)) puts(“What a pity!”);  
    75.         else puts(“Wonderful!”);  
    76.     }  
    77.     return 0;  
    78. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; const int N = 100; int sg[N+4][N+4]; bool ok(int x,int y) { return x>=1&&y>=1; } void fool() { sg[1][1] = 0; for (int i = 1;i <= 70;++i) { for (int j = 1;j <= 70;++j) { if (i == 1&&j == 1) continue; set<int>s; if (ok(i-1,j)) { s.insert(sg[i-1][j]); } if (ok(i,j-1)) { s.insert(sg[i][j-1]); } if (ok(i-1,j-1)) { s.insert(sg[i-1][j-1]); } int g = 0; while(s.count(g)) ++g; sg[i][j] = g; } } for (int i = 1;i <= 20;++i) { for (int j = 1;j <= 20;++j) { if (sg[i][j] == 0)//败态 { cout<<"("<<i<<","<<j<<")"<< endl; } } } } int main() { // fool(); int n,m; while (cin>>n>>m) { if (n==0&&m==0) break; if ((n&1)&&(m&1)) puts("What a pity!"); else puts("Wonderful!"); } return 0; }

    J - 取石子游戏

    斐波那契博弈哦,必败态是斐波那契数

    1. #include<iostream>  
    2. #include<cstdio>  
    3. using namespace std;  
    4. typedef long long ll;  
    5. bool check(ll x)  
    6. {  
    7.     ll f1 = 1,f2 = 1;  
    8.     ll f = 2;  
    9.     while (f <= x)  
    10.     {  
    11.         f = f1 + f2;  
    12.         if (f == x) return 1;  
    13.         f1 = f2;  
    14.         f2 = f;  
    15.     }  
    16.     return 0;  
    17. }  
    18. int main()  
    19. {  
    20.     ll n;  
    21.     while (cin>>n)  
    22.     {  
    23.         if (!n) break;  
    24.         if (check(n)) puts(“Second win”);  
    25.         else puts(“First win”);  
    26.     }  
    27.     return 0;  
    28. }   
    #include<iostream>
    
    
    
    
    
    #include<cstdio> using namespace std; typedef long long ll; bool check(ll x) { ll f1 = 1,f2 = 1; ll f = 2; while (f <= x) { f = f1 + f2; if (f == x) return 1; f1 = f2; f2 = f; } return 0; } int main() { ll n; while (cin>>n) { if (!n) break; if (check(n)) puts("Second win"); else puts("First win"); } return 0; }
    I - 邂逅明下

    三个变量,找规律的时候不是那么容易,然后说到博弈还有一个特点就是,大胆猜测~

    最后发现1~p必败,p+1~p+q必胜

    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. const int N = 100000;  
    25. int sg[N+4];  
    26. int n,p,q;  
    27. void turn(int n)  
    28. {  
    29.     for (int i = p;i <= q;++i)  
    30.     {  
    31.         sg[i+n] = 1;  
    32.     }  
    33. }  
    34. void fool()  
    35. {  
    36.     mem(sg,0);  
    37.     sg[0] = 1;  
    38.     for (int i = 1;i <= n;++i)  
    39.     {  
    40.         if (sg[i] == 0) turn(i);  
    41.     }  
    42.     for (int i = 1;i <= n;++i)  
    43.     {  
    44.         if (sg[i] == 0) cout<<“{“<<i<<“}”<<endl;  
    45.     }  
    46. }  
    47. void solve()  
    48. {  
    49.     for (int i = 1;i <= 10;++i)  
    50.     {  
    51.         for (int j = i;j <= 10;++j)  
    52.         {  
    53.             p = i,q = j;  
    54.             n = 80;  
    55.             cout<<p<<”,”<<q<<“:”<<endl;  
    56.             fool();  
    57.             cout<<”———————————-“<<endl;  
    58.         }  
    59.     }  
    60. }  
    61. int main()  
    62. {  
    63. //  solve();  
    64.     while (Sint(n) == 1)  
    65.     {  
    66.         Sint2(p,q);//fool();  
    67. //      if (sg[n]) puts(“WIN”);  
    68. //      else puts(“LOST”);  
    69.         –n;  
    70.         n%=(p+q);  
    71.         if (n < p) puts(“LOST”);  
    72.         else puts(“WIN”);  
    73.     }  
    74.     return 0;  
    75. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; const int N = 100000; int sg[N+4]; int n,p,q; void turn(int n) { for (int i = p;i <= q;++i) { sg[i+n] = 1; } } void fool() { mem(sg,0); sg[0] = 1; for (int i = 1;i <= n;++i) { if (sg[i] == 0) turn(i); } for (int i = 1;i <= n;++i) { if (sg[i] == 0) cout<<"{"<<i<<"}"<<endl; } } void solve() { for (int i = 1;i <= 10;++i) { for (int j = i;j <= 10;++j) { p = i,q = j; n = 80; cout<<p<<","<<q<<":"<<endl; fool(); cout<<"----------------------------------"<<endl; } } } int main() { // solve(); while (Sint(n) == 1) { Sint2(p,q);//fool(); // if (sg[n]) puts("WIN"); // else puts("LOST"); --n; n%=(p+q); if (n < p) puts("LOST"); else puts("WIN"); } return 0; }

    E - Fliping game

    找规律,发现当右下角是1的时候必胜

    插一句,这个游戏公平吗?是公平的,因为右下角是1的概率是1/2,而其他的石头怎么样不需要考虑^_^

    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24.   
    25. int main()  
    26. {  
    27.     int T;Sint(T);  
    28.     while(T–)  
    29.     {  
    30.         int n,m;  
    31.         Sint2(n,m);  
    32.         int s ;  
    33.         for (int i = 0;i < n;++i)  
    34.         {  
    35.             for (int j = 0;j < m;++j)  
    36.             {  
    37.                 Sint(s);  
    38.             }  
    39.         }   
    40.         if (s) puts(“Alice”);  
    41.         else puts(“Bob”);  
    42.     }   
    43.     return 0;  
    44. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; int main() { int T;Sint(T); while(T--) { int n,m; Sint2(n,m); int s ; for (int i = 0;i < n;++i) { for (int j = 0;j < m;++j) { Sint(s); } } if (s) puts("Alice"); else puts("Bob"); } return 0; }

    2.Nim 游戏变形:


    Nim游戏的简单变形,特判全部是1的情况:如果全部是1,奇败偶胜,否则就按Nim游戏的异或和为0的是败态
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. //const int N = 100;  
    25. //int a[N];  
    26. int main()  
    27. {  
    28.     int n;  
    29.     int T;cin>>T;  
    30.     while (T–)  
    31.     {  
    32.         int s = 0;cin>>n;  
    33.         bool  allone = 1;  
    34.         for (int i = 1,x;i <= n;++i)  
    35.         {  
    36.             Sint(x);  
    37.             s ^= x;  
    38.             if (x > 1) allone = 0;  
    39.         }  
    40.         if (allone)//奇败偶胜   
    41.         {  
    42.             if (n&1) puts(“Brother”);  
    43.             else puts(“John”);  
    44.         }  
    45.         else   
    46.         {  
    47.             if (s) puts(“John”);  
    48.             else puts(“Brother”);  
    49.         }  
    50.           
    51.     }  
    52.     return 0;  
    53. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; //const int N = 100; //int a[N]; int main() { int n; int T;cin>>T; while (T--) { int s = 0;cin>>n; bool allone = 1; for (int i = 1,x;i <= n;++i) { Sint(x); s ^= x; if (x > 1) allone = 0; } if (allone)//奇败偶胜 { if (n&1) puts("Brother"); else puts("John"); } else { if (s) puts("John"); else puts("Brother"); } } return 0; }
    T - Be the Winner
    和上面一题一样的规律,完全不一样的游戏却有完全一样的规律
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24.   
    25. int main()  
    26. {  
    27.     int n;  
    28.     while (cin>>n)  
    29.     {  
    30.         int s = 0;bool allone = 1;  
    31.         for (int i = 1,x;i <= n;++i)  
    32.         {  
    33.             Sint(x);  
    34.             s^=x;  
    35.             if (x > 1) allone = 0;  
    36.         }   
    37.         if (allone)//奇败偶胜  
    38.         {  
    39.             if (n&1) puts(“No”);  
    40.             else puts(“Yes”);  
    41.         }   
    42.         else   
    43.         {  
    44.             if (s) puts(“Yes”);  
    45.             else puts(“No”);  
    46.         }  
    47.     }      
    48.     return 0;  
    49. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; int main() { int n; while (cin>>n) { int s = 0;bool allone = 1; for (int i = 1,x;i <= n;++i) { Sint(x); s^=x; if (x > 1) allone = 0; } if (allone)//奇败偶胜 { if (n&1) puts("No"); else puts("Yes"); } else { if (s) puts("Yes"); else puts("No"); } } return 0; } H - Nim or not Nim?
    和今年多校里面的一道博弈题基本一样,规律基本都是一样的,这里是可以把石头分两堆,今年多校的那题( HDU 5795)分三堆一样的原理
    直接打表找规律,打表的过程注释以供参考
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. //const int N = 1000;  
    25. //int sg[N+6];  
    26. //int SG(int st)  
    27. //{  
    28. //  if (sg[st]!=-1) return sg[st];  
    29. //  set<int>s;  
    30. //  s.insert(SG(0));  
    31. //  for (int i = 1;i < st;++i)  
    32. //  {  
    33. //      s.insert(SG(st-i));//拿   
    34. //      s.insert(SG(i)^SG(st-i) );//分   
    35. //  }  
    36. //  int g = 0;  
    37. //  while (s.count(g)) ++g;  
    38. //  sg[st] = g;  
    39. //  return sg[st];  
    40. //}  
    41. //void solve()  
    42. //{  
    43. //  mem(sg,-1);  
    44. //  sg[0] = 0;  
    45. //  for (int i = 1;i <= 50;++i)  
    46. //  {  
    47. //      cout<<i<<” :”<<SG(i)<<endl;  
    48. //  }  
    49. //}  
    50. int SG(int st)  
    51. {  
    52.     if (st == 0) return 0;  
    53.     if (st%4==0) return st-1;  
    54.     if (st%4==3) return st+1;  
    55.     return st;   
    56. }  
    57. int main()  
    58. {  
    59. //    solve();  
    60.     int T;cin>>T;  
    61.     while (T–)  
    62.     {  
    63.         int n;  
    64.         Sint(n);  
    65.         int s = 0;  
    66.         for (int i = 1,x;i <= n;++i)  
    67.         {  
    68.             Sint(x);  
    69.             s ^= SG(x);  
    70.         }  
    71.         if (s) puts(“Alice”);  
    72.         else puts(“Bob”);  
    73.     }  
    74.     return 0;  
    75. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; //const int N = 1000; //int sg[N+6]; //int SG(int st) //{ // if (sg[st]!=-1) return sg[st]; // set<int>s; // s.insert(SG(0)); // for (int i = 1;i < st;++i) // { // s.insert(SG(st-i));//拿 // s.insert(SG(i)^SG(st-i) );//分 // } // int g = 0; // while (s.count(g)) ++g; // sg[st] = g; // return sg[st]; //} //void solve() //{ // mem(sg,-1); // sg[0] = 0; // for (int i = 1;i <= 50;++i) // { // cout<<i<<" :"<<SG(i)<<endl; // } //} int SG(int st) { if (st == 0) return 0; if (st%4==0) return st-1; if (st%4==3) return st+1; return st; } int main() { // solve(); int T;cin>>T; while (T--) { int n; Sint(n); int s = 0; for (int i = 1,x;i <= n;++i) { Sint(x); s ^= SG(x); } if (s) puts("Alice"); else puts("Bob"); } return 0; }PS:另附HDU 5795代码对比:(表打出来了规律就很简单了)
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. //const int N = 1000;  
    25. //int sg[N+5];  
    26. //int SG(int st)  
    27. //{  
    28. //  if (sg[st]!=-1) return sg[st];  
    29. //  set<int>s;  
    30. //  s.insert(SG(0));  
    31. //  for (int i = 1;i < st;++i)  
    32. //  {  
    33. //      s.insert(SG(st-i));//拿  
    34. //      for (int j = 1;j+i < st;++j)   
    35. //      {  
    36. //          s.insert(SG(i)^SG(j)^SG(st-i-j));//分  
    37. //      }  
    38. //  }  
    39. //  int g = 0;  
    40. //  while (s.count(g)) ++g;  
    41. //  sg[st] = g;  
    42. //  return sg[st];  
    43. //}  
    44. //void solve()  
    45. //{  
    46. //  mem(sg,-1);  
    47. //  sg[0] = 0;  
    48. //  for (int i = 1;i <= 50;++i)  
    49. //  {  
    50. //      cout<<i<<”: ”<<SG(i)<<endl;  
    51. //  }  
    52. //}  
    53. int SG(int st)  
    54. {  
    55.     if (st == 0) return 0;  
    56.     if (st%8 == 0) return st-1;  
    57.     if (st%8 == 7) return st+1;  
    58.     return st;  
    59. }  
    60. int main()  
    61. {  
    62. //    solve();  
    63.     int T;cin>>T;  
    64.     while (T–)  
    65.     {  
    66.         int n;  
    67.         Sint(n);  
    68.         int s = 0;  
    69.         for (int i = 1,x;i <= n;++i)  
    70.         {  
    71.             Sint(x);  
    72.             s^=SG(x);  
    73.         }  
    74.         if (s) puts(“First player wins.”);  
    75.         else puts(“Second player wins.”);  
    76.     }  
    77.     return 0;  
    78. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; //const int N = 1000; //int sg[N+5]; //int SG(int st) //{ // if (sg[st]!=-1) return sg[st]; // set<int>s; // s.insert(SG(0)); // for (int i = 1;i < st;++i) // { // s.insert(SG(st-i));//拿 // for (int j = 1;j+i < st;++j) // { // s.insert(SG(i)^SG(j)^SG(st-i-j));//分 // } // } // int g = 0; // while (s.count(g)) ++g; // sg[st] = g; // return sg[st]; //} //void solve() //{ // mem(sg,-1); // sg[0] = 0; // for (int i = 1;i <= 50;++i) // { // cout<<i<<": "<<SG(i)<<endl; // } //} int SG(int st) { if (st == 0) return 0; if (st%8 == 0) return st-1; if (st%8 == 7) return st+1; return st; } int main() { // solve(); int T;cin>>T; while (T--) { int n; Sint(n); int s = 0; for (int i = 1,x;i <= n;++i) { Sint(x); s^=SG(x); } if (s) puts("First player wins."); else puts("Second player wins."); } return 0; }

    F - Daizhenyang’s Coin

    我以为算是找规律的题,不过找的不是十进制数的规律,而是二进制数的规律,本来博弈就和二进制有着密不可分的关系

    所以找规律的时候也要记得考虑一下二进制(这一点不仅是博弈,记得很多其他地方也用到找二进制数的规律)

    不过有文章专门讲解了这一类型的游戏的策略:博弈-翻硬币游戏

    这里的规律是如果x的二进制里面1个数为奇数,sg[x]就是2x,否则是2x+1

    关于unique去重函数:点击打开链接

    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. int getone(int x)//返回二进制1的个数  
    25. {  
    26.     int t = 0;  
    27.     while (x)  
    28.     {  
    29.         if (x&1) ++t;  
    30.         x>>=1;  
    31.     }  
    32.     return t;  
    33. }   
    34. int SG(int x)  
    35. {  
    36.     if (getone(x)&1) return 2*x;  
    37.     else return 2*x+1;  
    38. }  
    39. ll a[111];  
    40. int main()  
    41. {  
    42.     int n;  
    43.     while (cin>>n)  
    44.     {  
    45.         ll s = 0;  
    46.         for (int i = 0;i < n;++i)  
    47.         {  
    48.             Sll(a[i]);  
    49.         }  
    50.         sort(a,a+n);  
    51.         n = unique(a,a+n)-a;  
    52.         for (int i = 0;i < n;++i)  
    53.         {  
    54.             s ^= SG(a[i]);   
    55.         }  
    56.         if (!s) puts(“Yes”);  
    57.         else puts(“No”);  
    58.     }  
    59.     return 0;  
    60. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; int getone(int x)//返回二进制1的个数 { int t = 0; while (x) { if (x&1) ++t; x>>=1; } return t; } int SG(int x) { if (getone(x)&1) return 2*x; else return 2*x+1; } ll a[111]; int main() { int n; while (cin>>n) { ll s = 0; for (int i = 0;i < n;++i) { Sll(a[i]); } sort(a,a+n); n = unique(a,a+n)-a; for (int i = 0;i < n;++i) { s ^= SG(a[i]); } if (!s) puts("Yes"); else puts("No"); } return 0; }

    3.状态转移:

    一般博弈都是问当前的局面是胜态还是败态,这个问如果是胜态,第一步有几种走法
    真正理解博弈的会明白,博弈双方对局面做出的转移
    当某人面对胜态的时候,他会将胜态转移成败态,
    而面对败态的人不管怎么操作,只能将局面由败态转为胜态(不包含平局)
    这是因为,如果异或和为0(败态)不管怎么操作都将使异或和变为非0(胜态)
    而异或和不为0(胜态),一定有策略将异或和变为0(败态)
    所以这题就是找,如果面对的是异或和不为0的胜态,有多少种方案将其变成异或和为0的败态
    关于异或,有个很有用的性质:a^a^b = b  (即相同的数异或为0),具体操作看代码
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. /* 
    25.     将非0态(胜态)转化为0态(负态)有多少种方案  
    26. */   
    27. const int N = 100;  
    28. int a[N+4];   
    29. int s;  
    30. bool ok(int x)  
    31. {  
    32.     int ns = s^x;//把x变成更小的数,使状态变为0   
    33.     if (ns < x) return 1;  
    34.     else return 0;  
    35. }  
    36. int main()  
    37. {  
    38.     int n;  
    39.     while (cin>>n)  
    40.     {  
    41.         if (!n) break;  
    42.         s = 0;  
    43.         for (int i = 1;i <= n;++i)  
    44.         {  
    45.             Sint(a[i]);  
    46.             s ^= a[i];  
    47.         }  
    48.         if (s == 0) puts(“0”);  
    49.         else   
    50.         {  
    51.             int sun = 0;  
    52.             for (int i = 1;i <= n;++i)  
    53.             {  
    54.                 if (ok(a[i])) ++sun;  
    55.             }  
    56.             Pintc(sun,’\n’);  
    57.         }  
    58.     }   
    59.     return 0;  
    60. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; /* 将非0态(胜态)转化为0态(负态)有多少种方案 */ const int N = 100; int a[N+4]; int s; bool ok(int x) { int ns = s^x;//把x变成更小的数,使状态变为0 if (ns < x) return 1; else return 0; } int main() { int n; while (cin>>n) { if (!n) break; s = 0; for (int i = 1;i <= n;++i) { Sint(a[i]); s ^= a[i]; } if (s == 0) puts("0"); else { int sun = 0; for (int i = 1;i <= n;++i) { if (ok(a[i])) ++sun; } Pintc(sun,'\n'); } } return 0; }
    一样的水题打表,不过问的是第一次的选择有哪些,那么枚举第一次的选择,判断子局面是不是败态即可
    (也就是只能将败态留给对手)
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. const int  N= 2111;  
    25. int sg[N];  
    26. int n,m;  
    27. void turn(int n)  
    28. {  
    29.     for (int i = 1;i <= m;++i)  
    30.     {  
    31.         sg[n+i] = 1;  
    32.     }  
    33. }  
    34. void fool()  
    35. {  
    36.     mem(sg,0);  
    37.     sg[0] = 0;  
    38.     for (int i = 0;i <= n;++i)  
    39.     {  
    40.         if (sg[i] == 0) turn (i);  
    41.     }   
    42. }  
    43. bool ok(int x)//将此局面给 对手,对手能否赢   
    44. {  
    45.     mem(sg,0);  
    46.     sg[x] = 0;  
    47.     for (int i = x;i <= n;++i)  
    48.     {  
    49.         if (sg[i] == 0) turn(i);  
    50.     }  
    51.     if (sg[n] == 0)//对手不能赢  
    52.     return 1;  
    53.     else return 0;   
    54. }  
    55. int main()  
    56. {  
    57.     while (cin>>n>>m)//n 是成本,m是可以加的数   
    58.     {  
    59.         fool();  
    60.         if (sg[n] == 0) puts(“none”);  
    61.         else   
    62.         {  
    63.             bool first = 1;  
    64.             for (int i = 1;i <= m;++i)  
    65.             {  
    66.                 if (ok(i))   
    67.             {  
    68.                 if (first)  
    69.                 {  
    70.                     printf(”%d”,i);  
    71.                     first = 0;  
    72.                 }  
    73.                 else printf(“ %d”,i);  
    74.             }         
    75.         }  
    76.         puts(”“);  
    77.     }  
    78.     }  
    79.     return 0;  
    80. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    
    #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; const int N= 2111; int sg[N]; int n,m; void turn(int n) { for (int i = 1;i <= m;++i) { sg[n+i] = 1; } } void fool() { mem(sg,0); sg[0] = 0; for (int i = 0;i <= n;++i) { if (sg[i] == 0) turn (i); } } bool ok(int x)//将此局面给 对手,对手能否赢 { mem(sg,0); sg[x] = 0; for (int i = x;i <= n;++i) { if (sg[i] == 0) turn(i); } if (sg[n] == 0)//对手不能赢 return 1; else return 0; } int main() { while (cin>>n>>m)//n 是成本,m是可以加的数 { fool(); if (sg[n] == 0) puts("none"); else { bool first = 1; for (int i = 1;i <= m;++i) { if (ok(i)) { if (first) { printf("%d",i); first = 0; } else printf(" %d",i); } } puts(""); } } return 0; }


    4.思维王道

    这题的选择稍多,假设a<b,可以选择对b减去k*a,只要k*a<=b
    这里涉及到一个自由度的概念,有些局面是固定的,比如(4,7),它只能按(4,7)-(4,3)-(1,3)的情况走下去
    像这样的局面就是没有自由度,操作者只有唯一的选择
    对于形如b-a<a的局面,就是没有自由度的局面,操作唯一,所以可以直接模拟
    对于形如b-a>a的局面,其实这是必胜的局面
    (不要问b-a==a的局面,b是a的倍数显然必胜态)
    综合上述规律,直接模拟即可(详解参考挑程310面):
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. bool moni(int a,int b)  
    25. {  
    26.     bool win = 1;  
    27.     while(1)  
    28.     {  
    29.         if (a>b) swap(a,b);  
    30.         if (b%a == 0) break;  
    31.         if (b-a>a) break;  
    32.         b -= a;  
    33.         win = !win;  
    34.     }  
    35.     return win;  
    36. }  
    37. int main()  
    38. {  
    39.     int a,b;  
    40.     while (cin>>a>>b)  
    41.     {  
    42.         if (a==0&&b==0) break;  
    43.         if ( moni(a,b))  puts(“Stan wins”);  
    44.         else puts(“Ollie wins”);  
    45.     }  
    46.     return 0;  
    47. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    

    include<iostream>

    include<cstdio>

    include<cstring>

    include<algorithm>

    include<queue>

    include<set>

    include<stack>

    include<cmath>

    include<map>

    include<stdlib.h>

    include<cctype>

    include<string>

    define Sint(n) scanf("%d",&n)

    define Sll(n) scanf("%I64d",&n)

    define Schar(n) scanf("%c",&n)

    define Sint2(x,y) scanf("%d %d",&x,&y)

    define Sll2(x,y) scanf("%I64d %I64d",&x,&y)

    define Pint(x) printf("%d",x)

    define Pllc(x,c) printf("%I64d%c",x,c)

    define Pintc(x,c) printf("%d%c",x,c)

    using namespace std;
    typedef long long ll;
    bool moni(int a,int b)
    {
    bool win = 1;
    while(1)
    {
    if (a>b) swap(a,b);
    if (b%a == 0) break;
    if (b-a>a) break;
    b -= a;
    win = !win;
    }
    return win;
    }
    int main()
    {
    int a,b;
    while (cin>>a>>b)
    {
    if (a==0&&b==0) break;
    if ( moni(a,b)) puts("Stan wins");
    else puts("Ollie wins");
    }
    return 0;
    }
    G - Game

    非常神奇,和二分图也联系起来了,想清楚了就是Nim游戏变形
    1. #define mem(a,x) memset(a,x,sizeof(a))  
    2. #include<iostream>  
    3. #include<cstdio>  
    4. #include<cstring>  
    5. #include<algorithm>  
    6. #include<queue>  
    7. #include<set>  
    8. #include<stack>  
    9. #include<cmath>  
    10. #include<map>  
    11. #include<stdlib.h>  
    12. #include<cctype>  
    13. #include<string>  
    14. #define Sint(n) scanf(“%d”,&n)  
    15. #define Sll(n) scanf(“%I64d”,&n)  
    16. #define Schar(n) scanf(“%c”,&n)  
    17. #define Sint2(x,y) scanf(“%d %d”,&x,&y)  
    18. #define Sll2(x,y) scanf(“%I64d %I64d”,&x,&y)  
    19. #define Pint(x) printf(“%d”,x)  
    20. #define Pllc(x,c) printf(“%I64d%c”,x,c)  
    21. #define Pintc(x,c) printf(“%d%c”,x,c)  
    22. using namespace std;  
    23. typedef long long ll;  
    24. /* 
    25.     1. 分成一个二分图 
    26.     <span style=”white-space:pre”>    </span>如果可以从A拿卡片到B,连一条从A到B的边。 
    27.     把所有box编号x满足((x%3==0&&x%2==1) || x%3==1)这个条件的放左边,其他放右边,不难发现  
    28.             a) 只有从左边到右边的边或从右到左的边。  
    29.             b) 所有不能拿卡片出去的box都在左边。 
    30.     2. 证明左边的box并不影响结果。假设当前从右边的局势来看属于输家的人为了  
    31.     摆脱这种局面,从左边的某盒子A拿了n张卡片到B,因为B肯定有出去的边,对手  
    32.     会从B再取走那n张卡片到左边,局面没有变化  
    33.     3. 于是这就相当于所有右边的box在nim游戏。 
    34. */   
    35. int main()  
    36. {  
    37.     int T;cin>>T;  
    38.     int kas = 0;  
    39.     while (T–)  
    40.     {  
    41.         int n;scanf(“%d”,&n);  
    42.         int s = 0;  
    43.         for (int i = 1,x;i <= n;++i)  
    44.         {  
    45.             scanf(”%d”,&x);  
    46. //          if ((i%2==1&&i%3==0)) continue;  
    47.             if ((i%3==0&&i%2==0)||i%3==2) s^=x;  
    48.         }  
    49.         printf(”Case %d: ”,++kas);  
    50.         if (s) puts(“Alice”);  
    51.         else puts(“Bob”);  
    52.     }   
    53.     return 0;  
    54. }  
    #define mem(a,x) memset(a,x,sizeof(a))
    
    
    
    
    

    include<iostream>

    include<cstdio>

    include<cstring>

    include<algorithm>

    include<queue>

    include<set>

    include<stack>

    include<cmath>

    include<map>

    include<stdlib.h>

    include<cctype>

    include<string>

    define Sint(n) scanf("%d",&n)

    define Sll(n) scanf("%I64d",&n)

    define Schar(n) scanf("%c",&n)

    define Sint2(x,y) scanf("%d %d",&x,&y)

    define Sll2(x,y) scanf("%I64d %I64d",&x,&y)

    define Pint(x) printf("%d",x)

    define Pllc(x,c) printf("%I64d%c",x,c)

    define Pintc(x,c) printf("%d%c",x,c)

    using namespace std;
    typedef long long ll;
    /*
    1. 分成一个二分图
    <span style="white-space:pre"> </span>如果可以从A拿卡片到B,连一条从A到B的边。
    把所有box编号x满足((x%3==0&&x%2==1) || x%3==1)这个条件的放左边,其他放右边,不难发现
    a) 只有从左边到右边的边或从右到左的边。
    b) 所有不能拿卡片出去的box都在左边。
    2. 证明左边的box并不影响结果。假设当前从右边的局势来看属于输家的人为了
    摆脱这种局面,从左边的某盒子A拿了n张卡片到B,因为B肯定有出去的边,对手
    会从B再取走那n张卡片到左边,局面没有变化
    3. 于是这就相当于所有右边的box在nim游戏。
    */
    int main()
    {
    int T;cin>>T;
    int kas = 0;
    while (T--)
    {
    int n;scanf("%d",&n);
    int s = 0;
    for (int i = 1,x;i <= n;++i)
    {
    scanf("%d",&x);
    // if ((i%2==1&&i%3==0)) continue;
    if ((i%3==0&&i%2==0)||i%3==2) s^=x;
    }
    printf("Case %d: ",++kas);
    if (s) puts("Alice");
    else puts("Bob");
    }
    return 0;
    }
    B - Gems Fight!

    局面的描述比较复杂,使用状态压缩博弈,一样的博弈原理,从终态去逆推当前面对的局面
    另写了详细题解: HDU 4778 Gems Fight!(博弈+状压)

    这个题才真正让人看到SG的作用,前面说当SG和Nim游戏的异或和的结论结合的时候可能并没有什么感觉
    这题就很好的应用了这点,整个棋盘的sg就是每个格子的sg的异或和

                </div>
                    </div>
    
    展开全文
  • 博弈 SG打表

    2021-06-19 19:40:16
    对于该博弈,我们知道 若 a[1] xor a[2] xor a[3]…xor a[n]==0 先手必败 反之 先手必胜 SG函数(打表) sg[n]代表对于一堆只有n个的石子,两人轮流拿,若sg[n]==0,则先手必败,反之,必胜 首先易知 sg[0]=0,没有...

    Nim游戏

    一共有N堆石子,编号1…n,第i堆中有个a[i]个石子。
    每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子,至少取一颗,至多取出这一堆剩下的所有石子。
    两个人轮流行动,取走最后一个的人胜利。Alice为先手。

    对于该博弈,我们知道

    a[1] xor a[2] xor a[3]…xor a[n]==0
    先手必败
    反之 先手必胜

    SG函数(打表)

    sg[n]代表对于一堆只有n个的石子,两人轮流拿,若sg[n]==0,则先手必败,反之,必胜
    首先易知 sg[0]=0,没有石子,先手必败
    随后,对于sg[n]
    s g [ n ] = m e x ( s g [ n − 1 ] , s g [ n − 2 ] , . . . ) sg[n]=mex(sg[n-1],sg[n-2],...) sg[n]=mex(sg[n1],sg[n2],...)
    mex括号内为所有可以拿取的石子数量

    int sg[maxn];//sg[n] n表示每堆数量
    int s[k];//每次能取的值,下标从0开始,0 ~ k-1,必须有序,可以sort(s,s+k);
    bool vis[maxn];
    const int k;//k是集合s的大小 
    void getsg()
    {
        int i,j;
        for(i=0;i<maxn;i++)
        {
            memset(vis,0,sizeof(vis));
            j=0;
            while(j<k&&s[j]<=i)
            {
              vis[sg[i-s[j]]]=1;
            j++;
            }
            for(j=0;j<maxn;j++)
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
    int main()
    {
        ...
        memset(sg,-1,sizeof(sg));
        getsg();
        if(sg[n]==0) //先手必败
        else    //先手必胜
    
       //如果有多堆,则
       // num=sg[n1]^sg[n2]^sg[n3]^....^sg[nx];
       // if(num==0) 则先手必败
       // else    先手必胜
        ...
    }
    

    对于多堆石子的情况
    我们将得到的sg函数
    进行xor运算
    再次进行判断即可。

    阶梯博弈

    对于树,1号为根节点。
    每个节点都有石子,每次操作可以由一个节点,移动任意数量石子,到该点的父节点,Alice和Bob轮流进行操作,最终无法操作(所有石子都在节点1)的人输掉
    在这里插入图片描述
    对于该树
    若Alice将第三层的任何值移动到第二层,Bob随即便可以将其顺势移动到第一层。如此,变对胜负完全没有影响
    由此我们发现,移动奇数层的节点没有意义
    奇数层的节点等同于根节点
    所以我们可以将该模型理解为,所有偶数层节点的一堆石子进行的经典Nim游戏

    翻硬币游戏模型

    在这里插入图片描述

    我们认为
    若0为反面,1为正面
    SG[0]= 0 0 0 0 0 0 …=0
    SG[1]= 1 0 0 0 0 0 …=1
    SG[2]= 0 1 0 0 0 0 …=2

    对于类似
    0 1 0 1 0 0
    我们可以将其拆分为
    0 1 0 0 0 0
    0 0 0 1 0 0
    即 SG[2] ^ SG[4]
    以此类推

    树上删边模型

    在这里插入图片描述
    结论:叶子节点的SG值为0;中间节点的SG值为它的所有子节点的SG值加1后的异或和。
    在这里插入图片描述

    无向图删边模型

    在无向图里,可以将奇环转换为长为1的链,可以将偶环转为一个点(去掉)
    在这里插入图片描述
    可以变为
    在这里插入图片描述

    展开全文
  • 博弈SG函数总结

    2020-10-09 17:55:32
    所有得sg 博弈 或者说是博弈和 无非就是说 谁没得选谁输/谁选了最后一个谁输 (反过来的话是不成立的 )就不是博弈和的问题了 因为 0 你先手败了 但是下一轮是后手先 后手又败了 你先手赢了 0^0=0 但是是先手赢了 ...

    所有得sg 博弈 或者说是博弈和 无非就是说 谁没得选谁输/谁选了最后一个谁输 (反过来的话是不成立的 )就不是博弈和的问题了 因为 0 你先手败了 但是下一轮是后手先 后手又败了 你先手赢了 0^0=0 但是是先手赢了 这种反 nim 要特别考虑
    对于 已经知道的 没得选的 (状态D) SG[D]=0 然后其他的 状态 都有他的n个后继 Di
    SG[D]=mex(SG[D0],SG[D1]…SG[Di]…SG[Dn]);
    对于每一个状态(如果他是多个状态的和的话) 的SG值也无非就是多个状态的 异或和
    SG[D]=0 就是必败态 否则 必胜
    还有对于求先手必胜态时, 先手可以进行的操作(也就是后继的选择)遍历每一种可能
    如果操作过后的状态的 SG 值 为 0 也就是后手必败 则 那一个操作 就是先手 的一种可能选择
    具体方法也就是 打表/dfs

    展开全文
  • 博弈SG函数模板

    2019-10-02 20:43:14
    #define maxn 1e4+10//maxn为堆中最大个数 #define cmax 1005//cmax为取个数的方法总数 ...//记录sg[n](n为堆的个数)sg值 int mex[maxn];//模拟mex运算 int get[cmax];// void get_sg() { // 例如有三种情况的...
    #define maxn 1e4+10//maxn为堆中最大个数
    #define cmax 1005//cmax为取个数的方法总数
    using namespace std;
    int sg[maxn];//记录sg[n](n为堆的个数)sg值
    int mex[maxn];//模拟mex运算
    int get[cmax];//
    void get_sg()
    {
        //   例如有三种情况的取石子方法  get[1] = 1,get[2] = 2,get[3] = k;
        // 然后注意如果题目所要求堆个数过大即要找规律,不能直接用sg函数运算
        memset(sg,0,sizeof(sg));
        //i小于需要求的sg范围:默认堆最大个数maxn内
        for(int i=1;i<=maxn;i++)
        {
            memset(mex,0,sizeof(mex));
            //条件为get[j]必须小于i才合法&&总类数小于cmax
            //要根据不同题目要求来写对应的取法
            for(int j=1;get[j]<=i&&j<=cmax;j++)
                mex[sg[i-j]]=1;//状态转移(注意根据不同题要求来写)
            //比如:此题分堆问题,mex[sg[j]^sg[i-g]]=1;
            for(int j=0;j<=maxn;j++)//j小于等于堆中最大个数
            {
                if(!mex[j])
                {
                    sg[i]=j;
                    break;
                }
            }
           //找规律输出
           // printf("sg[%d]:%d\n",i,sg[i]); 
        }
    }

    转载于:https://www.cnblogs.com/Tianwell/p/11442383.html

    展开全文
  • ACM 博弈 SG函数

    2018-05-31 17:35:25
    要理解SG函数,首先要先知道SG的定理:Sprague-Grudy定理:令N = {0, 1, 2, 3, ...} 为自然数的集合。Sprague-Grundy 函数给游戏中的每个状态分配了一个自然数。结点v的Grundy值等于没有在v的后继的Grundy值...
  • bzoj 1188 博弈sg函数

    2017-01-05 11:54:24
    蛮好的一道博弈题,加深对sg函数理解必备题目(╯‵□′)╯︵┻━┻  关键在于局面的定义和对子游戏的把握 一般情况下,我们直接定义石子数(每一堆)为一个局面,但是在这道题里会发现这么定义子游戏之间会产生...
  • 博弈论 参考文档 论文Game Threory https://pan.baidu.com/s/11P_rF5ZO-FuTPiNtjxcBlw 论文翻译 https://blog.csdn.net/strangedbly/article/details/51137432 适用范围 适用于 Impartial Combinatorial ...
  • 博弈SG函数

    2016-07-21 20:44:46
    题意:  一个棋盘有n行,每行20格子,都有一些棋子,两...终结点是这一行没有棋子可以走,即0,然后逆推出其他结点的SG函数。每一行的状态看成是一个结点,然后把状态二进制压缩,1表示有棋子,0表示空格。 #includ
  • poj2311(博弈SG函数)

    2018-03-07 20:19:11
    //公平组合博弈SG函数模板 SG[x]相当于Nim博弈中一堆石子的个数 //SG[]:0~n的SG函数值 //S[]:为x后继状态的集合 const int MAXN=205; int SG[MAXN][MAXN],S[MAXN]; int getSG(int a,int b) { if(SG[a][b]!=-1)...
  • 且当i,j同为偶数时,SG[i][j]=SG[i/2][j/2]+1。利用这个规律,我们可以快速求出SG值。 代码: #include #include #include #include using namespace std; int SG(int n,int m) { if(n&1&&m&1)return 0; if...
  • 博弈sg函数模板

    2016-12-01 21:34:38
    (1)打表 (2)dfs,(当数据范围太大,无法开出数组的时候) ...无论那种情况,在预处理的过程中都需要有一种意识就是,当你想算一个点的sg...//sg[]:0~n的SG函数值 //hash[]:mex{} int f[K],sg[N],hash[N];
  • 博弈SG函数与SG定理

    2018-07-29 10:45:11
    博弈论:https://blog.csdn.net/luomingjun12315/article/details/4547907 解题方法 巴什博奕(Bash Game):有一堆n个物品,两人轮流从堆中取物品,每次取 x 个 ( 1 ≤ x ≤ m)。最后取光者为胜。给定n,m问先手...
  • UVA 10561 - Treblecross(博弈SG函数)

    千次阅读 2014-07-16 13:46:37
    思路:SG函数,每个串要是上面有一个X,周围的4个位置就是禁区了(放下去必败),所以可以以X分为几个子游戏去求SG函数的异或和进行判断,至于求策略,就是枚举每个位置就可以了 代码: #include #
  • 博弈 - SG函数和SG定理

    2017-03-30 20:42:44
    在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方操作均正确...
  • 1.巴什博弈 只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个,最后取光者得胜。 显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余...
  • Nimm博弈sg函数mex函数

    千次阅读 2017-03-14 19:45:12
    op是sg数组int mex(int x){ if(sg[x] != -1) return sg[x]; bool vis[1005]; for(int i = 0;i ;i++) vis[i] = false; for(int i = 0;i ;i++){ int temp = x-op[i]; i
  • 博弈sg函数

    千次阅读 2016-03-07 15:36:30
    我们把整个博弈过程抽象为有向无环图 1. 几项准备工作: mex求最小非负整数mex{} = 0,mex{0,1,2,4} = 3,mex{1,2,4} = 0 sg[x] =mex{sg[y]|y是x的后继}//就是石头变少的继 这样sg就满足几个性质 1. sg[x] == 0时,...
  • hdu 1536、hdu 1944 S-Nim(博弈SG函数)

    千次阅读 2012-09-04 18:19:56
    题意:多组测试数据 ,输入 k个集合S的元素,m种情况,m种(L堆,每堆hi个)。  若存在移动某堆能到达一个... 每堆看做一个子游戏,SG函数通过递归得到每种堆数的g(); SG函数 定义: 对于一个递增有界的图G(X, F
  • 笔记——博弈 SG函数

    2018-04-13 13:15:52
    博弈问题博大精深啊 。。。sg函数 原理证明不做赘述,直接子额怎么用首先你必须知道P点与N点简单来说P点 ——谁从这个点走谁就输 N点——谁从这个点走谁就赢这两个有大大的关系 只要从必败点(P点)走必然下一步就...
  • 博弈SG】HDOJ1846

    2019-08-20 10:59:59
    和S-Nim这道题很像。看成只有一堆。 题目 Problem Description 十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中...这个短学期,我们讲的是博弈(game)专题;所以,大家现在玩的也是“勇敢者的游戏”...
  • 注意的是: bool类型的数组比int类型的数组快,不超时与超时的区别,在sg组合博弈时,只能在(a1,a2,a3,a4)中取,要特别注意这里面的数字是否是有序的,这个特别重要,下面贴出的两个模板对应了两种情况。...
  • 博弈SG函数

    万次阅读 多人点赞 2016-04-12 21:36:28
    别被文章长度吓到,学会博弈(SG)只用看前1/10。 鉴于讲明白博弈要写好多字,于是找了些论文拼凑,对疑难点加了注释并配上“美图”助解。 Nim游戏 重点结论:对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当...
  • 在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧. 必胜点和必败点的概念:  P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。  N点:必胜点,处于此情况下,双方操作均正确...
  • 知识点 - 博弈SG函数

    2019-08-06 10:35:11
    知识点 - SG函数 解决问题类型: ​ Impartial Combinatorial Games问题 概要 摘自https://blog.csdn.net/strangedbly/article/details/51137432 ​ 在有向无环图的顶点上定义Sprague-Garundy函数。 ​ 首先定义mex...
  • 51 Nod 1067 博弈 SG函数

    2019-02-28 22:27:00
    51 Nod 1067 博弈 SG函数 1067 Bash游戏 V2 1 秒 131,072 KB 10 分 2 级题 有一堆石子共有N个。A B两个人轮流拿,A先拿。每次只能拿1,3,4颗,拿到最后1颗石子的人获胜。假设A...
  • 简单博弈的异或原理加上sg函数就可以,把每一堆石子看成一个单独子游戏。最后的结果就是sg[m],sg[n],sg[p]三者的异或和。 套一下sg函数的模板即可。 代码 #include<stdio.h> #include<string.h> int fib...
  • SG讲解:https://www.cnblogs.com/aiguona/p/9126324.html 检验最好用bool,这道题book[ ]用int超时要了我的老命。 题中没说默认升序,卡到绝望 救命:为什么输入aa[ ]时我从1开始时,并且在第一个for循环中的j也从1...
  • POJ 2505 博弈SG打表

    2017-08-31 09:44:22
    博弈SG打表题意:​ 两个人玩乘法游戏,每个人只能乘以2~9,谁先达到>=n谁胜,先手只能乘以1.思路:​ SG的: 除 任意一步所能转移到的子局面的SG值以外的最小非负整数。直接打表找到规律。#include #include #...
  • Problem Description 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生,它是这样定义的: ... if(sg[n] ^ sg[m] ^ sg[p]) printf("Fibo\n"); else printf("Nacci\n"); } }  

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,050
精华内容 2,820
关键字:

博弈sg