巴什博弈

巴什博弈(Bash Game):只有一堆n个物品，两个人轮流取1物品，规定每次最少取一个，最多取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）的倍数，就能最后获胜。

结论：

只要n%(m+1)!=0,先取者一定获胜。

但是，如果不是任意取1~m个而是给一个集合S={a1,a2,a3....an},只能取ai个，或者反一下两人轮流加1~m，加到大于等于n就算赢，或者乘到n，这些变形该怎么办？

分析此类问题主要方法是P/N分析：

P点：即必败点，某玩家位于此点，只要对方无失误，则必败；

N点：即必胜点，某玩家位于此点，只要自己无失误，则必胜。

三个定理：

一、所有终结点都是必败点P（上游戏中，轮到谁拿牌，还剩0张牌的时候，此人就输了，因为无牌可取）；

二、所有一步能走到必败点P的就是N点；

三、通过一步操作只能到N点的就是P点；

算法实现：

步骤1:将所有终结位置标记为必败点（P点）；（终结位置指的是不能将游戏进行下去的位置）
步骤2:将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；
步骤4:如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。

为了方便，我把用P/N分析法且是单数操作的全部归类为巴什博弈。（分类错了请见谅）

例题一

硬币游戏1

题目链接：挑战程序设计博弈篇上的

题目大意：x枚硬币，给定大小为k的集合S={a1,a2....ak}，Alice和Bob轮流取硬币，每次取的数目要为ai，取走最后一枚则获胜，谁会赢？

解题思路：利用P/N分析，设j为剩余硬币数，j=0为必败态。那么有以下两个规则：

　　　　　①对于某个i,j-ai为必败态，那么j就是必胜态（N）。

　　　　　②对于任意i,j-ai都是必胜态，j就是必败态（P）。

根据这些规则，我们只要按照j从小到大的顺序递推确定各点是必胜态还是必败态态，最后只要看x点是必胜还是必败就能知道谁获胜了。

代码：

 1 #include<cstdio> 
 2 const int N=1e4+5;
 3 int a[105];
 4 bool win[N];
 5 
 6 int main(){
 7     int x,k;
 8     while(scanf("%d%d",&x,&k)){
 9         for(int i=1;i<=k;i++){
10             scanf("%d",&a[i]);
11         }
12         win[0]=false;//j=0是必败态
13         
14         for(int j=1;j<=x;j++){
15             bool flag=false;
16             for(int i=1;i<=k;i++){
17                 //如果某个i令j-a[i]是必败态，则j为必胜态 
18                  if(a[i]<=j&&!win[j-a[i]]){
19                      flag=true;
20                      break;
21                  }         
22             }
23             win[j]=flag;
24         }
25         if(win[x]) puts("Alice");
26         else    puts("Bob");
27     }
28 }

例题二

HDU 2149 Public Sale

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2149

题目大意：初始价格为0，两个人轮流加价，加价范围是1~N，谁先把价格加到大于等于M谁就获胜。现在的要求是第一个人加价多少可以获得胜利，如果不能就输出“none”。

解题思路：用P/N分析发现了规律，只要通过加价t可以使得(M-t)%(N+1)那先手就会获胜，反之如果找不到t也就是t=0，那么就是“none”。

代码：

 1 #include<cstdio>
 2 int main(){
 3     int m,n;
 4     while(~scanf("%d%d",&m,&n)){
 5         bool flag=false;
 6         if(m%(n+1)==0)
 7             printf("none");
 8         else{
 9             printf("%d",m%(n+1));
10             //n>m的情况
11             for(int i=m+1;i<=n;i++)
12                 printf(" %d",i);
13         }
14         printf("
");
15     } 
16     return 0;
17 }

例题三

HDU 1517 A Multiplication Game

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1517

题目大意：两个人玩游戏，轮流操作，给你一个数字n以及p=1，每次可以从2~9中任选一个数字，并把它与p相乘，谁能先使得p>=n，谁就是胜者。

看了大牛的解法终于对P/N分析有了一点理解：

根据P/N分析的方法，先将终结位置[n,无穷]标记为P点。

然后找所有能到达P点的点[n/9,n-1]标记为N点。

接着找到只能进入N点的点[n/9/2,n/9-1]标记为P点。

循环以上两次操作，判断出1这个点是否为必胜点。

代码：

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 int main(){
 7     LL n;
 8     while(~scanf("%lld",&n)){
 9         int x=0;
10         while(n>1){
11             x++;
12             if(x&1)
13                 n=ceil((double)n/9);
14             else
15                 n=ceil((double)n/2);
16         }
17         if(x&1)
18             printf("Stan wins.
");
19         else
20             printf("Ollie wins.
");
21     }
22 }
23