博弈论之尼姆博弈和阶梯尼姆博弈浅析

尼姆问题的解法及异或运算

尼姆问题的定义:

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

尼姆问题解法:

尼姆问题的解法在20世纪初由哈佛大学的一个叫做Charles Leonard Bouton的数学家提出,使用异或运算符便可以简单解决此类问题,其思路是每堆小石子作累异或运算,若最后结果为$0$,则先手必败,若为$1$则先手必胜。由于本文本意并非是要探讨其中的数学问题,所以就不作证明了(因为笔者本人也不太懂),反正AC就行.
这里简单的介绍一下异或运算把,异或运算的规则是相同则为$0$,不同则为$1$,具体可以去看看我之前写的关于位运算的文章。由于本文本意并非是要探讨其中的数学问题,所以就不作证明了(因为笔者本人也不太懂),反正AC就行。

阶梯尼姆博弈

上面我们讲了尼姆问题的解法,但是在算法竞赛中很显然,不可能直接考察原题,而多以阶梯尼姆问题的形式出现。
让我来看看一道尼姆问题的经典题

POJ 1704
题意:每次可以向左移动一个棋子任意步,不能跨过棋子

那么这种问题我们该如何解决呢,其实也很简单,如果棋子是偶数个,那么我们可以将两个相邻的棋子中间的空格数目视为一堆石子,两堆石子中间的空格不予考虑。说起来可能难以理解,我们来画个图了解一下。

红线所划出的范围便是两对石子的间隙了,这些间隙不予考虑,因为如果移动这些间隙后面的任意一个棋子,我方都总是可以移动与之配对的另外一个棋子而使得当前局面不变。
那么奇数的情况呢,举个例子,假设输入是

如图,在前方添加一个棋子,然后按照偶数的方法计算,在这里分成了两堆,从而转化为标准尼姆问题求解。
$$2xor2=0$$

需要注意的原题中棋盘位置的点的输入并非和样例一样是有序的

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vector<int>nums;
        nums.push_back(0);//对于偶数也添加并不影响其结果,但简化了计算
        for(int i=0;i<n;i++)
        {
            int tmp;
            cin>>tmp;
            nums.push_back(tmp);
        } 
        sort(nums.begin(),nums.end());//排序
        int res=0;
        for(int i=n;i>0;i-=2)
        {
            res^=(nums[i]-nums[i-1]-1);//连续累异或
        }
        if(res==0)cout<<"Bob will win"<<endl;//判断res值
        else cout<<"Georgia will win"<<endl;
    } 
    return 0;
} 

第四届蓝桥杯B组决赛 高僧斗法

问题描述
  古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。
  节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人,其它任意。(如图1所示)
  两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。两个小和尚也不能站在同一台阶,也不能向低级台阶移动。
  两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。
  对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。
输入格式
  输入数据为一行用空格分开的N个整数,表示小和尚的位置。台阶序号从1算起,所以最后一个小和尚的位置即是台阶的总数。(N<100, 台阶总数<1000)
输出格式
  输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解,输出A值较小的解,若无解则输出-1。
样例输入
1 5 9
样例输出
1 4
样例输入
1 5 8 10
样例输出
1 3

该题首先计算石子数量,然后全部异或起来判断是否为0,如果不为0,则转化为阶梯nim问题求解,为0输出-1

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    vector<int>hs;
    int tmp;
    while (cin >> tmp)
    {
        hs.push_back(tmp);
    }
    hs.push_back(hs[hs.size()-1]+1);
    int ans = 0;
    vector<int>nim;
    for (int i = 1; i < hs.size(); i += 2)
    {
        int tmp = hs[i] - hs[i - 1]-1;
        nim.push_back(tmp);
        ans ^= tmp;
    }

    //cout<<nim[0]<<" "<<nim[1]; 
    if (ans == 0)
    {
        cout << -1 << endl;
        return 0;
    }
    int d = 0;
    for (int i = 0; i <nim.size(); i++)
    {

        int tmp = nim[i];
        for (int j = 1; j <= tmp; j++)
        {
            nim[i] = tmp - j;
            int an = 0;
            for (int a = 0; a < nim.size(); a++)
            {
                an ^= nim[a];
            }
            if (an == 0)
            {
                cout << hs[d]<< " " << hs[d]+j;
                goto P;
            }
        }
        d += 2;
        nim[i] = tmp;
    }
P:int a;
    return 0;
}
Last modification:September 30th, 2019 at 05:56 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment