第四届蓝桥杯决赛 B 组 C/C++—— 高僧斗法

高僧斗法展开目录

古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有 “高僧斗法” 的趣味节目，以舒缓压抑的气氛。节目大略步骤为：先用粮食（一般是稻米）在地上 “画” 出若干级台阶（表示 N 级浮屠）。又有若干小和尚随机地 “站” 在某个台阶上。最高一级台阶必须站人，其它任意。(如下图所示)
两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。

输入数据为一行用空格分开的 N 个整数，表示小和尚的位置。台阶序号从 1 算起，所以最后一个小和尚的位置即是台阶的总数。（N<100, 台阶总数 < 1000）

输出为一行用空格分开的两个整数：A B, 表示把 A 位置的小和尚移动到 B 位置。若有多个解，输出 A 值较小的解，若无解则输出 - 1。

例如：

用户输入：

1 5 9

则程序输出：

1 4

用户输入：

1 5 8 10

则程序输出：

1 3

题解展开目录

这题困扰我还是蛮久的，为了解决这题并且为了免除后顾之忧，我把常见的四大博弈问题 —— 巴什博弈、威佐夫博弈、斐波那契博弈、尼姆博弈都研究了遍。而这题要用到的就是尼姆博弈

巴什博弈和斐波那契博弈适用于一堆的状态

威佐夫博弈适用于两堆

这题之所以用尼姆博弈就是因为它适用于 n 堆，没看过尼姆博弈的先去了解一下

知道这题用什么模型之后，我们要把这题想办法抽象成” 堆 “的状态，其实也不难，两个两个和尚进行配对，他们楼梯号的差值再减一就是一堆的数量，就以 1 5 8 10 为例
我觉得这张图特别能帮助理解，我们看堆 1，1 楼的小和尚只有三种走法，可以抽象成堆 1 有三枚石子；同样的，8 楼的小和尚只有一种走法，所以抽象成堆 2 有一枚石子，此时尼姆堆 N={3 1}

现在问题就来了，两两配对，那如果只有奇数个输入，也就是只有奇数个小和尚，应该怎么办？其实我们把题目抽象为尼姆堆最后都是要对尼姆堆里的数值进行异或运算，对于异或运算有一个性质：x^0=x，一个数对 0 异或还等于这个数。有了这个性质，我们其实只要在尼姆堆里增加个 0 就行，这个 0 就是我们判断如果小和尚个数是奇数，就在后面再增加一个数据，这个数据的值为输入数据的最后一个值 + 1。例如 1 5 8 10 13，此时尼姆堆 N={3,1,0}

问题也抽象出来了，下面就好解决了。我方先手，堆元素全部异或起来结果为 0，我方必输，输入 - 1；如果不为 0，那我们可以改变某一堆的大小，使其异或起来为 0，把必败局面留给对方

这里注意最后一个问题，我们到底应该移动哪一个和尚，以 1 5 8 10 为例，假如我们移动 5，使其产生一个必败局面，但是此时对手可以移动 1，又返还给我们一个必败局面，那这样是没有任何意义的。但是如果我们通过改变 1、8 楼的和尚，形成一个必败局面，此时无论对手走什么，我们都可以跟随，或者是改变另一堆的大小再返还给对方一个必败局面

代码展开目录

#include <bits/stdc++.h>
using namespace std;
int len = 0;
//判断一组Nim堆是否能赢 
bool Nim(int* x)
{
    int i,res = 0;
    int N[100];
    for(i = 0;i < len;i++)
    { 
        N[i] = x[2 * i + 1] - x[2 * i] - 1;
        res ^= N[i];
    }
    if(res == 0)
        return true;
    return false;
}
int main()
{
    int x[100],N[100];
    memset(x,0,sizeof(x));
    int res = 0,i = 0,is = 1,old;
    char s;
    //输入 
    for(i = 0;i < 100 && s != '\n';i++)
    {
        scanf("%d",&x[i]);
        s = getchar(); 
    }
    len = i;
    //如果只有奇数个数据，那么要隐式的在最后增加一个，使其变为偶数 
    if(i % 2)
    {
        x[i] = x[i-1] + 1;
        len++;
    }
    //判断一开始的状态是否是输 
    if(Nim(x))
        cout<<-1;
    //移动和尚            
    else
    {
        for(i = 0;i < len && is == 1;i += 2)
        {
            for(int j = x[i] + 1;j < x[i+1] && is == 1;j++)
            {
                old = x[i];
                x[i] = j;
                if(Nim(x))
                {
                    cout<<old<<" "<<x[i];
                    is = 0;
                }
                x[i] = old;
            }
        } 
    }
    return 0;
}

关于代码我还有两点说明：

1. 关于移动和尚中的 x [i] =old 这一行代码，在试探的过程中，如果异或不为 0，那么我们肯定要继续试探，但是应该将原有的改变全部还原，其实就跟搜索差不多吧，回溯的时候要还原，不然肯定会出现问题
2. 题目是输入一行数据，所以我以回车作为结束符，如果你不知道，就请记住这个框架

for(i = 0;i < 100 && s != '\n';i++)
{
    scanf("%d",&x[i]);
    s = getchar(); 
}