洛谷 P1247 取火柴游戏 题解【博弈论】【NIM博弈】

点击量：211

    博弈里简单的NIM博弈问题。

目录

题目描述

输入\(k\)及\(k\)个整数\(n_1,n_2,\cdots ,n_k\)，表示有\(k\)堆火柴棒，第\(i\)堆火柴棒的根数为\(n_i\)；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。

 

谁取走最后一根火柴为胜利者。

 

例如：\(k=2\)，\(n_1=n_2=2\)，\(\mathrm{A}\)代表你，\(\mathrm{P}\)代表计算机，若决定\(\mathrm{A}\)先取：

\(\mathrm{A}:(2,2)\rightarrow (1,2)\){从一堆中取一根}

\(\mathrm{P}:(1,2)\rightarrow (1,1)\){从另一堆中取一根}

\(\mathrm{A}:(1,1)\rightarrow (1,0)\)

\(\mathrm{P}:(1,0)\rightarrow (0,0)\){\(\mathrm{P}\)胜利}

 

如果决定\(\mathrm{A}\)后取：

\(\mathrm{P}:(2,2)\rightarrow (2,0)\)

\(\mathrm{A}:(2,0)\rightarrow (0,0)\) {\(\mathrm{A}\)胜利}

 

又如\(k=3,n_1=1,n_2=2,n_3=3\)，\(\mathrm{A}\)决定后取：

\(\mathrm{P}:(1,2,3)\rightarrow (0,2,3)\)

\(\mathrm{A}:(0,2,3)\rightarrow (0,2,2)\)

 

\(\mathrm{A}\)已将游戏归结为\((2,2)\)的情况，不管\(\mathrm{P}\)如何取\(\mathrm{A}\)都必胜。

 

编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出“lose”。

 

输入输出格式

输入格式：

第一行，一个正整数\(k\)，

 

第二行，\(k\)个整数\(n_1,n_2,…,n_k\)。

 

输出格式：

如果是先取必胜，请在第一行输出两个整数\(a,b\)，表示第一次从第\(b\)堆取出\(a\)个。第二行为第一次取火柴后的状态。如果有多种答案，则输出\(<b,a>\)字典序最小的答案(即\(b\)最小的前提下\(a\)最小)。

 

如果是先取必败，则输出“lose”。

 

输入输出样例

输入样例#1：

3
3 6 9

输出样例#1：

4 3
3 6 5

输入样例#2：

4
15 22 19 10

输出样例#2：

lose

说明

\(k\le 500000,n_i\le 10^9\)

题解：

    传统的“取石子问题”，在剩下\((1,1)\)两堆石子时必败。推广到一般情况，则\(n_1\bigoplus n_2\bigoplus \cdots \bigoplus n_k=0\)时必败。因为异或运算是可逆的，因此无论对手做出什么决策，只要自己能把局面恢复到所有值异或等于零，对手就一定失败。

证明：

    当A的回合为\(n_1\bigoplus n_2\bigoplus \cdots \bigoplus n_k=0\)时，要么此时\(\forall i,n_i=0\)，要么剩下不止一堆，而如果只取一堆，这个结果就必将改变，那么\(n_1\bigoplus n_2\bigoplus \cdots \bigoplus n_k>0\)，这时B只需要让这个异或和等于0，A的局面总是必败，因为到最后总有一次会满足\(\forall i,n_i=0\)。

    下证B一定有决策让异或和等于0。

    假设异或和为\(x=01001010_{(2)}\)，只要\(n_i\)中找一个数变为\(n_i\bigoplus x\)，就可以让异或和变回\(0\)。不过我们还要保证这一堆的火柴减少，不能直接找一个\(n_i>x\)。既然异或和中第\(6\)位（左数第一个为\(1\)的位）为1，那么一定存在一个第\(6\)位为\(1\)的数\(n_i\)。而\(n_i\bigoplus x<n_i\)，因为减少了\(2^6\)，所以后面的\(0\sim 5\)位无论怎么变都不会超过\(2^6-1\)，所以\(n_i\)会减小。这样我们就找到了\(n_i\)，只要让它变成\(n_i\bigoplus x(<n_i)\)，异或和就会变成\(x\bigoplus x=0\)，让对手必败。

    所以我们只需要找到从左到右数第一个（题目要求）\(n_i\)满足\(n_i\ \mathrm{and}\ \mathrm{highbit}(x)>0\)的数（定义highbit类似于lowbit，就是为1的最高位），取走它的\(n_i-(n_i\bigoplus x)\)根火柴，它就变成了\(n_i\bigoplus x\)，也满足了题意，也正好这样就是唯一值。

Code：

#include<cstdio>
#include<cstring>
int a[555555];
int main()
{
    int n,tt=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        tt^=a[i];//异或和
    }
    if(!tt)//异或和为0自己就必败
    {
        puts("lose");
        return 0;
    }
    int hst=-1,t=tt;
    while(t)
    {
        ++hst;//求highbit
        t>>=1;
    }
    for(int i=1;i<=n;++i)
        if(a[i]&(1<<hst))
        {
            printf("%d %d\n",a[i]-(a[i]^tt),i);
            a[i]-=a[i]-(a[i]^tt);
            break;//只取一处所以要break
        }
    for(int i=1;i<=n;++i)
        printf("%d ",a[i]);
    return 0;
}