博弈论初级逗比题:poj2484 && poj2975 && poj2505
博弈论初初级
1:poj2484 A FUNNY GAME
题目大意:
给N个围成一圈的硬币,设编号为1到n,两个杀马特的逗比轮流取,每次可以取走一个硬币,或两个
编号相邻的硬币,问对于给出的N,哪个逗比赢。
解析题目:
乍一看好像特别牛鼻,实际先取的逗比只要不能一下子全部取完,那么稳输= = ,因为这是一张对称
的图,只要后取的能做到取完后是一张中心对称的图,就稳赢,当然前提是先取的取不完。
所以只有N为1 or 2 时先取的赢,其余稳输。
代码:
#include<cstdio> char ch1, ch2; int main ( ) { while (1) { ch1=getchar(), ch2=getchar(); if (ch1=='0') break; if (ch2==' '&&ch1<='2')printf("Alice "); else printf("Bob "); while (ch2!=' ') ch2=getchar(); } }
2:poj2975 Nim游戏
题目大意:
给你N堆石子,告诉你每堆石子中石子的个数,又来了两个杀马特的逗比,他们轮流取,每次可以取任
意一堆石子的任意数量,最后哪个逗比没得取就为输。问先取的是否有必胜的方法?有几种?
题目解析:
将每堆石子的石子数异或在一起,如果大于零,就代表存在必胜的方法:先取一堆石子使得异或和变为
零,即对方面临的是败态,然后根据它的取数保持石子数的异或和为零,最后就赢了。也就是说只有第一步
可选,方案总数即为第一步方案的总数。分别将每堆石子的数量异或回去,看石子数和异或和的大小关系即
可判断可不可取。
代码:
1 #include<cstdio> 2 int n,he,an,a[1004],i; 3 int main ( ) 4 { 5 while (scanf("%d",&n)!=EOF&&n) 6 { 7 he = 0, an = 0; 8 for (i=1; i<=n; i++) scanf("%d",&a[i]),he^=a[i]; 9 if (!he) { printf("0 "); continue; } 10 for (i=1; i<=n; i++) if ((he^a[i]) <= a[i]) an++; 11 printf("%d ",an); 12 } 13 }