博弈论试题集.doc

(一)巴什博奕(BashGame):只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。最后取光者得胜。    显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余得物品,:如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1—k个,结果剩下(m+1)(r—1)个,以后保持这样得取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)得倍数,就能最后获胜。    这个游戏还可以有一种变相得玩法:两个人轮流报数,每次至少报一个,最多报十个,(一)时间限制:3000 ms |  内存限制:65535 KB难度:2描述一天,TT在寝室闲着无聊,与同寝得人玩起了取石子游戏,而由于条件有限,她/。设有一堆石子,数量为N(1<=N<=1000000),两个人轮番取出其中得若干个,每次最多取M个(1<=M<=1000000),最先把石子取完者胜利。我们知道,TT与她/她得室友都十分得聪明,那么如果就是TT先取,她/她会取得游戏得胜利么?输入第一行就是一个正整数n表示有n组测试数据输入有不到1000组数据,每组数据一行,有两个数N与M,之间用空格分隔。输出对于每组数据,输出一行。如果先取得TT可以赢得游戏,则输出“Win",否则输出“Lose”(引号不用输出)样例输入21000 11100样例输出LoseWin最优解:#include〈iostream>usingnamespacestd;intmain(){ intk;ﻩlongm,n;ﻩcin>>k;ﻩwhile(k--) { ﻩcin>>n>>m;ﻩﻩif(n%(m+1)==0)ﻩ ﻩcout<<"Lose"〈〈endl; else cout〈<"Win"〈<endl;ﻩ}}巴什博弈变形:有两种解,依实际情况而定:取石子(七)时间限制:1000 ms |  内存限制:65535 KB难度:1描述Yougth与Hrdv玩一个游戏,拿出n个石子摆成一圈,Yougth与Hrdv分别从其中取石子,谁先取完者胜,每次可以从中取一个或者相邻两个,Hrdv先取,输出胜利着得名字。输入输入包括多组测试数据。ﻫ每组测试数据一个n,数据保证int范围内。输出输出胜利者得名字。样例输入23样例输出HrdvYougth解一:#include<cstdio>intn;intmain(){while(~scanf("%d",&n)) printf(n>=3?”Yougth\n":"Hrdv\n");return0;}解二:3得倍数得就是Yougth嬴#include<iostream>usingnamespacestd;intmain(){ﻫint a;ﻫwhile(cin〉>a)ﻫ{if(a%3!=0)cout<<"Hrdv”〈<endl;ﻫelsecout〈<"Yougth"<<endl;ﻫ}return0;}尼姆博弈基本思想:       两人从n堆物品中取任意个,先取完者胜。       即将n堆物品得数量异或,得到得值如果为0,则先手败,反之先手胜。       如果要求先手在胜得条件下,到奇异局势得方法数,则判断异或得值与每一堆原值异或后(结果应该表示该堆没有参加异或时得异或值)与原值比较大小,如果小于,则方法数加一。且对应得方法后,(二)时间限制:3000 ms  | 内存限制:65535 KB难度:5描述小王喜欢与同事玩一些小游戏,今天她们选择了玩取石子。游戏规则如下:共有N堆石子,已知每堆中石子得数量,并且规定好每堆石子最多可以取得石子数(最少取1颗)。两个人轮流取子,每次只能选择N堆石子中得一堆,取一定数量得石子(最少取一个),并且取得石子数量不能多于该堆石子规定好得最多取子数,,并且游戏双方都绝对聪明,现在给您石子得堆数、每堆石子得数量与每堆石子规定得单次取子上限,请判断出小王能否获胜。输入第一行就是一个整数T表示测试数据得组数(T<100)每组测试数据得第一行就是一个整数N(1〈N<100),表示共有N堆石子,随后得N行每行表示一堆石子,这N行中每行有两个数整数m,n表示该堆石子共有m个石子,该堆石子每次最多取n个。(0〈=m,n〈=2^31)输出对于每组测试数据,输出Win表示小王可以获胜, 11 1样例输出LoseLose提示注意下面一组测试数据ﻫ2ﻫ