博弈论试题集.doc

。（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。 显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，sm),那么先取者要拿走s个物品，如果后取者拿走k（m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。 这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。取石子（一）时间限制：3000ms | 内存限制：65535KB难度：2描述一天，TT在寝室闲着无聊，和同寝的人玩起了取石子游戏，而由于条件有限，他/她们是用旺仔小馒头当作石子。游戏的规则是这样的。设有一堆石子，数量为N（1=N=1000000），两个人轮番取出其中的若干个，每次最多取M个（1=M=1000000），最先把石子取完者胜利。我们知道，TT和他/她的室友都十分的聪明，那么如果是TT先取，他/她会取得游戏的胜利么？输入第一行是一个正整数n表示有n组测试数据输入有不到1000组数据，每组数据一行，有两个数N和M,之间用空格分隔。输出对于每组数据，输出一行。如果先取的TT可以赢得游戏，则输出“Win”，否则输出“Lose”（引号不用输出）样例输入21000 11 100样例输出LoseWin最优解：#includeusing namespace std;int main()int k;long m,n;cink;while(k-)cinnm;if(n%(m+1)=0)coutLoseendl;elsecoutWinendl; 巴什博弈变形：有两种解，依实际情况而定：取石子（七）时间限制：1000ms | 内存限制：65535KB难度：1描述Yougth和Hrdv玩一个游戏，拿出n个石子摆成一圈，Yougth和Hrdv分别从其中取石子，谁先取完者胜，每次可以从中取一个或者相邻两个，Hrdv先取，输出胜利着的名字。输入输入包括多组测试数据。每组测试数据一个n，数据保证int范围内。输出输出胜利者的名字。样例输入23样例输出HrdvYougth解一：#includeint n;int main() while(scanf(%d,&n) printf(n=3?Yougthn:Hrdvn); return 0;解二：3的倍数的是Yougth嬴#includeusing namespace std;int main()int a;while(cina)if(a%3!=0)coutHrdvendl;else coutYougthendl;return 0; 尼姆博弈基本思想： 两人从n堆物品中取任意个，先取完者胜。 即将n堆物品的数量异或，得到的值如果为0，则先手败，反之先手胜。 如果要求先手在胜的条件下，到奇异局势的方法数，则判断异或的值与每一堆原值异或后（结果应该表示该堆没有参加异或时的异或值）与原值比较大小，如果小于，则方法数加一。且对应的方法后，该堆的数目应变为异或的值与每一堆原值异或的值。取石子（二）时间限制：3000ms | 内存限制：65535KB难度：5描述小王喜欢与同事玩一些小游戏，今天他们选择了玩取石子。游戏规则如下：共有N堆石子，已知每堆中石子的数量，并且规定好每堆石子最多可以取的石子数（最少取1颗）。两个人轮流取子，每次只能选择N堆石子中的一堆，取一定数量的石子(最少取一个），并且取的石子数量不能多于该堆石子规定好的最多取子数，等哪个人无法取子时就表示此人输掉了游戏。假设每次都是小王先取石子，并且游戏双方都绝对聪明，现在给你石子的堆数、每堆石子的数量和每堆石子规定的单次取子上限，请判断出小王能否获胜。输入第一行是一个整数T表示测试数据的组数(T100)每组测试数据的第一行是一个整数N(1N100),表示共有N堆石子，随后的N行每行表示一堆石子，这N行中每行有两个数整数m,n表示该堆石子共有m个石子，该堆石子每次最多取n个。(0=m,n=231)输出对于每组测试数据，输出Win表示小王可以获胜，输出Lose表示小王必然会败。样例输入211000 121 11 1样例输出LoseLose 提示注意下面一组测试数据21 12 2正确的结果应该是Win因为小王会先从第二堆石子中取一个石子，使状态变为1 11 2这种状态下，无论对方怎么取，小王都能获胜。最优解#includeint main()int T; scanf(%d,&T);while(T-)int m,n,g,sum=0;scanf(%d,&g);while(g-)scanf(%d%d,&m,&n);sum = m % (n + 1);puts(sum?Win:Lose); 一般解：#include using namespace std;#include bool HandleEachCase();int main()int iCaseCount;ciniCaseCount;while(iCaseCount-)if(HandleEachCase()coutWinendl;elsecoutLoseiCount;for(int i= 0; imn;m%= (n+1);magic= m;return magic != 0;取石子（六）时间限制：1000ms | 内存限制：65535KB难度：3描述最近TopCoder的PIAOYI和HRDV很无聊，于是就想了一个游戏，游戏是这样的：有n堆石子,两个人轮流从其中某一堆中任意取走一定的石子,最后不能取的为输家，注意：每次只能从一堆取任意个，可以取完这堆，但不能不取。假设PIAOYI先取石子，请你帮他判断他是否能赢（假设他们取的过程中不发生失误,他们足够聪明）。输入第一行输入n，代表有n组测试数据(n=10000)以下每组测试数据包含两行：第一行：包含一个整数m，代表本组测试数据有m（m=1000）堆石子；：第二行：包含m个整数Ai(Ai=100)，分别代表第i堆石子的数量。输出若PIAOYI赢输出“PIAOYI”，否则输出“HRDV”注意每组结果占一行。样例输入321 133 8 1125 10最优解：#include#includeusing namespace std;void in(int &a)char ch;while(ch=getchar()9);for(a=0;ch=0&ch=9;ch=getchar() a=a*10+ch-0;int main()int T;in(T);while(T-)int n;in(n);int ans=0;for(int i=0;i!=n;+i)int b;in(b);ans=b;if(ans) puts(PIAOYI);else puts(HRDV);return 0; 取石子（三）时间限制：1000ms | 内存限制：1000KB难度：6描述小王喜欢与同事玩一些小游戏，今天他们选择了玩取石子。游戏规则如下：共有N堆石子，已知每堆中石子的数量，两个人轮流取子，每次只能选择N堆石子中的一堆，取一定数量的石子（最少取一个），取过子之后，还可以将该堆石子中剩下的任意多个石子中随意选取几个放到其它的任意一堆或几堆上。等哪个人无法取子时就表示此人输掉了游戏。注意，一堆石子没有子之后，就不能再往此处放石子了。假设每次都是小王先取石子，并且游戏双方都绝对聪明，现在给你石子的堆数、每堆石子的数量，请判断出小王能否获胜。例如：如果最开始有4堆石子，石子个数分别为3 1 4 2，而小王想决定要先拿走第三堆石子中的两个石子（石子堆状态变为3 1 2 2），然后他可以使石子堆达到的状态有以下几种：3 1 2 2（不再移动石子）4 1 1 2（移动到第一堆一个）3 2 1 2（移动到第二堆一个）3 1 1 3（移动到第四堆一个）5 1 0 2（全部移动到第一堆）3 3 0 2（全部移动到第二堆）3 1 0 4（全部移动到最后）输入可能有多组测试数据(测试数据组数不超过1000)每组测试数据的第一行是一个整数，表示N(1=N=10)第二行是N个整数分别表示该堆石子中石子的数量。（每堆石子数目不超过100）当输入的N为0时，表示输入结束输出对于每组测试数据，输出Win表示小王可以获胜，输出Lose表示小王必然会败。样例输入32 1 321 10样例输出WinLose一般解：#include #include #include using namespace std;bool HandleEachCase();int main()while(HandleEachCase()/empty whilebool HandleEachCase()int iCount;int count101;memset(count, 0, sizeof(count);ciniCount;if(!iCount)return false;int iStone;for(int i= 0; iiStone;+countiStone;int magic = 0;for(int i= 0; i 101 & !magic; +i)magic+= counti&1;if(magic)coutWinendl;elsecoutLoseendl;return true;分析:显然,如果石头是能够两两配对,每一对的数目相同,比如:2,3,2,4可以配对成(2,2),(4,4) ,这样的话就是先拿的输,因为后拿的可以使自己拿完后仍然能够使得两两配对,且每一对的数目相同.刚刚开始的时候,如果已经两两配对了,那么先拿的输了,否则,选拿的可以把最大的动一下手脚,使剩下的两两配对,且每一对的数目相同.最优解：#include#includeusing namespace std;bool ok(int stone)for(int i=0;i!=110;i+)if(stonei&1) return true;return false;int main()int stone110;int n,m;while(cinn & n)memset(stone,0,sizeof(stone);while(n-)cinm;stonem+;cout(ok(stone)?Win:Lose) ak-1 ，而 bk= ak + k ak-1 + k-1 = bk-1 ak-1 。所以性质1。成立。 2。任意操作都可将奇异局势变为非奇异局势。 事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。 3。采用适当的方法，可以将非奇异局势变为奇异局势。 假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b bk，那么，取走b - bk个物体，即变为奇异局势；如果 a = ak ， b ak ，b= ak + k,则从第一堆中拿走多余的数量a - ak 即可；如果a ak ，b= ak + k,分两种情况，第一种，a=aj （j k）,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j k）,从第二堆里面拿走 b - aj 即可。 从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。 那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式： ak =k（1+5）/2，bk= ak + k （k=0，1，2，.,n 方括号表示取整函数)奇妙的是其中出现了黄金分割数（1+5）/2 = 1。618.,因此,由ak，bk组成的矩形近似为黄金矩形，由于2/（1+5）=（5-1）/2，可以先求出j=a（5-1）/2，若a=j（1+5）/2，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。取石子 (四）时间限制：1000ms | 内存限制：65535KB难度：4描述有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。输入输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。输出输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。样例输入2 18 44 7样例输出010最优解：#include #include using namespace std; int main() int m,n;while(cinmn)if (m n)int temp;temp = m;m = n;n =temp;int k = n - m;int data = floor(k*(1.0+sqrt(5.0)/2.0);if (data = m)cout0endl;elsecout1endl; Wythoff Game时间限制：1000ms | 内存限制：65535KB难度：1描述最近ZKC同学在学博弈，学到了一个伟大的博弈问题-威佐夫博弈。相信大家都学过了吧？没学过？没问题。我将要为你讲述一下这个伟大的博弈问题。有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法：一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。我们今天要做的是求前n个必败态。什么是必败态？比如我们把（a，b）称为一种状态，a，b分别为两堆石子中所剩的数目。如果a=0，b=0，我们说该种状态为必败态，因为我不能再进行游戏，即使是可以进行，那也是必败的，你知道，游戏的我们都是非常聪明的。（0,0）（1,2）（3,5）.都是必败态，我们今天要做的就是求前n个必败态。不会？好吧！我再告诉你：假设第n个必败态为（a，b）a为前n-1个必败态中没有出现的最小自然数，b=a+n。这下大家应该明白了吧。好吧，我们的任务就的要前n个必败态。规定第0个必败态为（0,0）。输入多组数据。输入为一个数n（0=n=100000）。输出按照要求求出前n个必败态。输出格式看下面样例。样例输入31样例输出(0,0)(1,2)(3,5)(4,7)(0,0)(1,2)提示注意：每种情况中间没有空格#include#includetypedef struct Nodeint a,b;N;N res100001;void init()res0.a=0;res0.b=0;for(int i=1;i100001;i+)resi.a=(1+sqrt(5)*i/2;resi.b=resi.a+i;int main()int n;init();while(scanf(%d,&n)!=EOF)for(int i=0;i=n;i+)printf(%d,%d),resi.a,resi.b);printf(n);return 0; 本人自己写的代码：#includeint main()int n,k,b,a100001,i,m=0;a0=0;while(scanf(%d,&n)if(n=m)for(k=0;k=n;k+)printf(%d,%d),ak,ak+k);elseprintf(%d,%d),a0,a0);for(k=1;k=0;i-)if(b=(ai+i)b+;else if(b(ai+i)break;ak=b;printf(%d,%d),ak,ak+k);m=n;printf(n);return 0; 取石子（八）时间限制：1000ms | 内存限制：65535KB难度：3描述有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你胜，你第1次怎样取子?输入输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000。a=b=0退出。输出输出也有若干行，如果最后你是败者，则为0，反之，输出1，并输出使你胜的你第1次取石子后剩下的两堆石子的数量x,y,x=y。如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况，假如取一堆的有多种情况，先输出从石子多的一堆中取的情况，且要求输出结果保证第二个值不小于第一个值。样例输入1 2 5 72 20 0样例输出013 53 54 710 01 2最优解：#include#include #include #includeusing namespace std;int main() int a,b,temp,temp2,k,i; while(scanf(%d%d,&a,&b),a+b) if(ab) swap(a,b); k=b-a; temp=k*(1.0+sqrt(5.0)/2.0; if(a=temp) /奇异局势 printf(0n); else printf(1n); if(abs(temp-a)=abs(temp+k-b)&tempa) /两堆 printf(%d %dn,temp,temp+k); if(a=0) /0 0情况，第一种奇异局势 printf(0 0n); for(i=1;ib) break; if(temp=a&temp2b) printf(%d %dn,a,temp2); else if(temp2=a&tempb) printf(%d %dn,temp,a); else if(temp2=b&tempa) printf(%d %dn,temp,b); return 0; Fibonaccis Game（斐波那契博弈）斐波那契博弈模型，大致上是这样的：有一堆个数为 n 的石子，游戏双方轮流取石子，满足：1. 先手不能在第一次把所有的石子取完；2. 之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。约定取走最后一个石子的人为赢家，求必败态。（转）分析： n = 2时输出second； n = 3时也是输出second； n = 4时，第一个人想获胜就必须先拿1个，这时剩余的石子数为3，此时无论第二个人如何取，第一个人都能赢，输出first； n = 5时，first不可能获胜，因为他取2时，second直接取掉剩下的3个就会获胜，当他取1时，这样就变成了n为4的情形，所以输出的是second； n = 6时，first只要去掉1个，就可以让局势变成n为5的情形，所以输出的是first； n = 7时，first取掉2个，局势变成n为5的情形，故first赢，所以输出的是first； n = 8时，当first取1的时候，局势变为7的情形，第二个人可赢，first取2的时候，局势变成n为6得到情形，也是第二个人赢，取3的时候，second直接取掉剩下的5个，所以n = 8时，输出的是second； 从上面的分析可以看出，n为2、3、5、8时，这些都是输出second，即必败点，仔细的人会发现这些满足斐波那契数的规律，可以推断13也是一个必败点。借助“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。n=12时，只要谁能使石子剩下8且此次取子没超过3就能获胜。因此可以把12看成8+4，把8看成一个站，等价与对4进行气喘操作。又如13，13=8+5，5本来就是必败态，得出13也是必败态。也就是说，只要是斐波那契数，都是必败点。所以我们可以利用斐波那契数的公式：fibi = fibi-1 + fibi-2，只要n是斐波那契数就输出No。取石子(五）时间限制：1000ms | 内存限制：65535KB难度：4描述himdd最近很想玩游戏，于是他找到acmj和他一起玩，游戏是这样的：有一堆石子,两个人轮流从其中取走一定的石子,取走最后所有石子的人为赢家,不过得遵循如下规则:1.第一次取不能取完,至少取1颗.2.从第二次开始,每个人取的石子数至少为1,至多为对手刚取的石子数的两倍。himdd事先想知道自己会不会赢，你能帮帮他吗？（每次himdd先手）输入有多组测试数据，每组有一个整数n(2=n264);输出himdd会赢输出Yes,否则输出No;样例输入256样例输出NoNoYes一般解：#includeusing namespace std;int main() long long n,fib100; int i,flag; fib0=2; fib1=3; for(i=2;in&n) flag=0; for(i=0;i100;i+) if(fibi=n) coutNon; flag=1; break; if(flag=0) coutYesn; return 0;Nim Staircase博奕:这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1=j=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上（0号）的人获胜。算法：将奇数楼层的状态异或，和为0则先手必败，否则先手必胜。证明略。例题：Poj1704这道题可以把两个棋子中间间隔的空格子个数作为一堆石子，则原题转化为每次可以把左边的一堆石子移到相邻的右边的一堆中。也就是阶梯尼姆博弈，注意对输入数据先排序，然后倒着往前数（an-an-1-1为第一个），奇数个数到的就做一下xor，其中最前面的看做a1-0-1，参考程序：vart,n,b,i,j:longint;a:array0.1000of longint;beginreadln(t);repeatdec(t);readln(n);for i:=1 to n do read(ai);qsort(1,n);/快排略j:=0;b:=0;for i:=n downto 1 dobegininc(j);if odd(j) then b:=b xor (ai-ai-1-1);end;if b=0 then writeln(Bob will win) else writeln(Georgia will win);until t=0;end.SG函数模板首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex g(y) | y是x的后继 ,这里的g（x）即sgx例如：取石子问题，有1堆n个的石子，每次只能取1，3,4个石子，先取完石子者胜利，那么各个数的SG值为多少？sg0=0，f=1,3,4,x=1时，可以取走1-f1个石子，剩余0个，mexsg0=0，故sg1=1;x=2时，可以取走2-f1个石子，剩余1个，mexsg1=1，故sg2=0；x=3时，可以取走3-f1,3个石子，剩余2,0个，mexsg2,sg0=0,0，故sg3=1;x=4时，可以取走4-f1,3,4个石子，剩余3,1,0个，mexsg3,sg1,sg0=1,1,0,故sg4=2;x=5时，可以取走5-f1,3,4个石子，剩余4,2,1个，mexsg4,sg2,sg1=2,0,1,故sg5=3；以此类推.x 0 1 2 3 4 5 6 7 8.sgx 0 1 0 1 2 3 2 0 1.计算从1-n范围内的SG值。f(存储可以走的步数，f0表示可以有多少种走法)f需要从小到大排序，这个模版f是从1开始的。hash数组大小跟f大小差不多1.可选步数为1m的连续整数，直接取模即可，SG(x) = x % (m+1);2.可选步数为任意步，SG(x) = x; 3. 可选步数为一系列不连续的数，用GetSG()计算/f：可以取走的石子个数/sg:0n的SG函数值/hash:mexint fN,sgN,hashN; void getSG(int n) int i,j; memset(sg,0,sizeof(sg); for(i=1;i=n;i+) memset(hash,0,sizeof(hash); for(j=1;fj=i;j+) hashsgi-fj=1; for(j=0;j=n;j+) /求mes中未出现的最小的非负整数 if(hashj=0) sgi=j; break; 下边补充一点东西。上边那个模版求hash时候并没有考虑fj有效长度，在某些题目中可以通过，比如这个。因为在求斐波那契数列时候肯定多求了一个，而就是因为这个会在求hash时候打破循环。其实总的来说还是这个函数并不严密。因为有的时候f是有有效长度的，如果多出了这个长度就会出现错误，如果你的初值都是0，那么就会取到0，如果是-1，那么就会取到-1，肯定不对。比如这个题。下面这两个模版应该就比较严密了，这个里边的f是从零开始的。转自：1、 sg打表/f：