博弈论相关

------------恢复内容开始------------

巴什博奕

简述

只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个，最后取光者胜

题解

我们称先进行游戏的人为先手，后进行游戏的人为后手

1. 如果 n=m+1，由于一个人最少取 1 个，最多取 m 个，所以先手无论拿走多少个，后手都能一次拿走剩余物品，后手胜
2. 如果 n=（m+1）×r+s，(r 为自然数，s≤m)，先手取胜的方式为：先手第一次拿走 s 个物品，如果后手拿走 k(k≤m) 个，那么先手在拿走 m+1–k 个，即这一轮两人拿走的数和为 m+1，并且由于第一次先手拿走了 s 个，所以剩下 (m+1)×(r−1) 个，以后一直保持这样的取法，无论后手拿走多少个，先手拿走的数量与后手的和总是凑成 (m+1)。那么我们得到如下结论：n%(m+1)=0 时后手必胜，否则先手必胜

代码

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m)
        if(n%(m+1) == 0)
            cout<<"后手必胜"<<endl;
        else
            cout<<"先手必胜"<<endl;
    return 0;
}

变形

如果我们规定，最后取光者输，那么又如何考虑呢？

反过来想，如果先手拿走了 n-1 个，那最后就剩下一个给后手了，后手就输了（因为这一个必拿，拿了他就是最后一个取光的人，他就输了），那么这个问题就转换为，有一堆 n–1 个物品，最后取光者胜不就行了么，当然，操作方式和基础巴什博弈一样，永远跟对方凑 (m + 1)。结论：(n - 1) \% (m + 1) = 0 时，后手胜，反之先手胜

#include<iotream>
using namespace std;
int main()
{
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if((n - 1) % (m + 1) != 0)
            printf("first
");
        else
            printf("second
");
    }
    return 0;
}

威佐夫博弈：适用于两堆石子的情况。

有两堆若干个石子，两个人轮流从某一堆或同时从两堆中取同样多的石子，规定每次至少取一个，多者不限，最后取光者胜

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,k;
    double eqa = (1+sqrt(5.0))/2.0;
    while( scanf("%d%d",&a,&b)!=EOF )
    {
        
        if( a > b )
        {
            a^=b;
            b^=a;
            a^=b;
        }
        k=b-a;
        if( int( k*eqa )==a )  printf("0
");
        else    printf("1
");
    }

尼姆博弈

简述

有若干堆石子，每堆石子的数量都是有限的，合法的移动是 “选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人的时候所有石子堆都已经被拿空了，则判负（因为他此时没有任何合法的移动）

分析

这游戏看上去有些复杂，我们先从简单情况开始研究，如果轮到你时，只剩下一堆石子，那么此时必胜策略肯定是把这堆石子全部拿完，然后对手没有石子拿就输了；如果剩下两堆不相等的石子，必胜策略是通过取多的一堆石子将两堆石子变得相等，之后对手如果在某一堆拿若干颗，你就在另一堆拿同样多的数量，直至胜利；但是如果还剩三堆，应该怎么分析呢？假设有三堆石子（a，b，c），我们前面说到，如果只有两堆石子，并且石子数量满足（n，n），谁先手谁就输。其实我们可以把三堆石子问题转换成两堆，只要满足状态（0，n，n）并且此时是对方先手，那我方按照两堆石子的取法，就能获胜。对于这种（0，n，n）的局势，我们称为奇异局势。对任何奇异局势（a，b，c）都有 a^b^c=0（^ 表示异或），如果我们面对非奇异局势，要如何变为奇异局势呢？假设 a<b<c，我们只要将 c 变为 a^b 即可。道理很简单，因为 a^b^(a^b)=0。要将 c 变为 a^b 也很简单，只要从 c 中减去 c-a^b 即可

例（14，21，39），14^21=27，39-27=12，所以从 39 中拿走 12 个，即可变成奇异局势（14，21.27）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m;
    int a[1001];
    while(cin>>m&&m)
    {
        int res = 0;
        memset(a,0,sizeof(a));
        for(int i = 0;i < m;i++)
        {
            cin>>a[i];
            res ^= a[i];
        }
        if(res == 0)
            cout<<"Grass Win!"<<endl;
        else
            cout<<"Rabbit Win!"<<endl;
    }
    return 0;
}