第四届蓝桥杯决赛第四题 高僧斗法 （nim博弈 sg函数）深究

高僧斗法

古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。

节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示N级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。(如图1所示)

两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。
两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。
对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。
输入数据为一行用空格分开的N个整数，表示小和尚的位置。台阶序号从1算起，所以最后一个小和尚的位置即是台阶的总数。（N<100, 台阶总数<1000）
输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解，输出A值较小的解，若无解则输出-1。

例如：
用户输入：
1 5 9
则程序输出：
1 4
再如：
用户输入：
1 5 8 10
则程序输出：
1 3
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

首先来介绍几个概念：
Nim博弈
遇到P-position必败，当且仅当a1^a2^….^an=0 （此处为位的异或运送） 相同取0，相异取1
何种游戏可以被称为nim博弈：
1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。

nim定理有几个很重要的性质：
定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。

如果在博弈过程中，每个局面不可重现，即可对position集合进行拓扑排序。思路分析：递归。
对当前局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略！
由于每个局面的子局面都会存在重叠，故可使用dp和记忆化搜索，但过程太过繁琐。
然而非常棒的一个方法就是各位异或为0（虽然我也不知道为什么）

2.被判为N-position的局面一定可以移动到某个p-position
【证明】 若（a1^a2^a3^…..^an）！=0，一定存在着合法的移动，将ai变成aii后满足，a1^a2^..^aii^…^an=0 ！！同时这一性质也是解决移动的解法！！ 不妨设a1^a2^a3^…..^an=k，则一定存在某个ai它的二进制表示在k的最高位上是1（否则k最高位的1没有k就等于0了！）
这时ai^k

#include<iostream>
#include<stdio.h> 
#include<string>
#define N 100
using namespace std;
int main()
{
    int i, j, k;
    int count=0;

    int monk[N] = { 0 };
    string str;
    getline(cin,str);
    int len = str.length();
    for (j = 0, i = 0; i<len; )
    {
        if (str[i]<'0' || str[i]>'9')
        {
                i++;
        }
        else {
            int n = 0;
            for (; i < len; ++i)
            {
                if (str[i] >= '0'&&str[i] <= '9')
                {
                    n = n * 10 + str[i] - '0';
                }
                else break;
            }
            monk[j++] = n;
        }
    }
    count = j;
    int *a = new int[count];
    for (i = 0, j = 0; j <= (count / 2); j += 2, i++)
    {
        a[i] = monk[j + 1] - monk[j] - 1;
    }
    k = i;
    int sum = a[0];
    for (i = 1; i < k; i++)
    {
        sum ^= a[i];
    }
    if (sum == 0) cout << "-1";
    else {
        for (i = 0; i < k; i++)
        {
            if ((a[i] ^ sum) <= a[i])   j = a[i] ^ sum;
            break;
        }
        cout << monk[2 * i] << " " << monk[2 * i] + a[i] - j;
    }
    delete[]a;
    getchar(); getchar();
    return 0;

}

啊啊啊啊啊啊啊啊啊啊啊啊，我终于写出代码了，其实具备nim博弈的知识下面判断的条件很容易写出，但我就是卡在输入那个地方了，哦吼吼，一会发博文详写。