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

作者: wjyyy 分类: NIM博弈,博弈,数学,解题报告 发布时间: 2018-09-04 15:27

点击量:23

 

    博弈里简单的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;
}

说点什么

avatar
  Subscribe  
提醒
/* */