[蓝桥杯][历届真题]高僧斗法（博弈-Nim博弈）

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

这是一道经典的阶梯Nim博弈问题，想解决这道题 首先要知道Nim博弈（如果知道就直接看代码吧）， Nim博弈就是说，给你几堆小石子 ，让两个玩家分别在这几堆小石子中取出石子（可以将某堆石子全部取出 也可以在某堆中只取一个小石子，当然是不可能不取的，不然还玩撒）。谁取到最后 ，没有石子取就输了。

比如 有 3 堆石子 ，每堆分别为 2 3 4个小石子，如下图所示  

玩游戏都想赢 ，所以 如何取尤为重要，方案有很多，想快速知道如果我方先手 是赢 还是输，直接就用Nim 研究过的成果。

Nim 的做法 就是 将  2 3 4 都转化为2进制再 异或 得出结果，如果结果是非0 那么先手必定赢 如果结果为0 那么先手必输（前提，玩游戏的都想赢 且都很聪明）

 可以看到异或后得到的结果是非0 则先手必胜， 先手遇到如此局面肯定会想办法 将它 变成0 这里先手在个数为4的一堆中取出3个。这堆就变成1个 整个局面的结果 就变成0，那么后手进行操作的话，无论操作 哪一堆，在哪堆中拿多少个石子，看看下图对不对。 肯定会破坏这种局面，让结果变为非0，比如后手在为3堆一堆取走3，

比如后手在为3堆一堆取走3，如下图

现在又到该先手取石子了，这个时候先手肯定要把 2个石子的一堆取出1个来，还剩1个，如图所示

现在又轮到 后手去取石子，现在一眼就可以看出  先手必赢了吧，  后手根据规则 只能拿走一个，然后轮到先手 拿了最后一个，后手就没得办法取 ，游戏就结束了。

现在回过头来 看阶梯Nim博弈问题。 只需要将 阶梯Nim博弈问题转换为Nim博弈问题即可，做如下转换，每两个和尚之间看做一堆，比如 和尚分别站 1  3   5   8   那么可以转换为3堆，分别为 1  1  2，再取异或 就可以知道 先手是否必赢，具体实现可以看代码。（注意； 如果移动了一个小和尚 除了边界 ，会影响相邻两堆的情况，看代码注释）

AC代码

#include<iostream>
#define N 102
using namespace std; 
int main(){
  int a[N],b[N];
    int n = 0,i,j,k,sum = 0;
      while(cin>>a[n])n++;//存储又有多少个小和尚 
     for(i=1; i<n; i++)b[i-1] = a[i] - a[i-1] - 1;// 进行Nim博弈的转换 
       for(i=0; i<n-1; i+=2) sum ^= b[i];//进行异或 
    if(sum==0)cout<<-1<<endl;//若开始局面为0 则必输 
    else//若非0 则必赢，因此 需要找到第一步 将局面变为0 的步骤 
    {
        for(i=0; i<n-1; ++i)//枚举移动第i堆  使得剩下的局面异或等于0，
            for(j=1; a[i]+j<a[i+1]; ++j) {//枚举可以移动的步数  保证 前项移动j 步后 不会超过后项 
			    b[i] -= j;//拿走 j个 ，这里代表 前一个向上移动j步 
                if(i!=0)b[i-1] += j;//它的后一堆b[i]向取走了j个，那莫前一堆 b[i-1] 则要增加j个 第一堆除外 
            sum = 0;
            for(k=0; k<n-1; k+=2) sum ^= b[k];//重新计算局面， 
		   if(sum==0) {cout<<a[i]<<" "<<a[i]+j<<endl; break;}//若变成0  则后手必败，先手必赢。跳出即可； 
            b[i] += j;//回溯 这不是必赢的操作 
            if(i!=0) b[i-1] -= j; 
          }
    }
    return 0;   
}

 题目链接：http://www.dotcpp.com/oj/problem1459.html