P1247 取火柴游戏博弈nim

佚名 6年前 (2019-05-05) 随笔 1472人围观抢沙发百度已收录

题目描述

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

例如：k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取：

A：(2,2)→(1,2) {从一堆中取一根}

P：(1,2)→(1,1) {从另一堆中取一根}

A：(1,1)→(1,0)

P：(1,0)→ (0,0) {P胜利}

如果决定A后取：

P：(2,2)→(2,0)

A：(2,0)→ 0,0) {A胜利}

又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：

P：(1,2,3)→(0,2,3)

A：(0,2,3)→(0,2,2)

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

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

输入输出格式

输入格式：

第一行，一个正整数k

第二行，k个整数n1，n2，…，nk

输出格式：

如果是先取必胜，请在第一行输出两个整数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



很明显是一个nim游戏 但是要求输出第一次的取法(字典序最小）

所以要求取一次  使得sg（总）==0

先手必胜，即先手可以拿走一些火柴，使得后手必败，而必败态是火柴堆的异或和为零；那么我们求的，就是先手拿走一些火柴后，新的火柴堆异或和为零的方案。设原异或和为XX，易知

a_1\,xor\,a_2\,xor\,a_3\,=\,Xa1xora2xora3=X

a_1\,xor\,a_2\,xor\,a_3\,xor\,X\,=\,0a1xora2xora3xorX=0

运用异或结合律（这里以结合第二个为例）

a_1\,xor(a_2\,xor\,X)xor\,a_3\,\,=\,0a1xor(a2xorX)xora3=0

那么，我们可以把(a_2\,xor\,X)(a2xorX)视为新的一堆火柴，当a_2a2变为(a_2\,xor\,X)(a2xorX)时异或和为零，后手便必败。当然，由于这是取火柴游戏，所以(a_2\,xor\,X)(a2xorX)必须小于a_2a2才行。

异或写在后面一定要加括号！

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=500000+5;
const int M=N;
int a[N];
int main()
{
    int ans=0;
    int n;RI(n);
    rep(i,1,n)
    {
        RI(a[i]);
        ans^=a[i];
    }
    if(!ans)
    {
        printf("lose");
        return 0;
    }
    rep(i,1,n)
    {
        if( (a[i]^ans)<a[i] )
        {
            int d=a[i]-(a[i]^ans);
            printf("%d %d\n",d,i);
            a[i]=a[i]^ans;
            break;
        }
    }
    rep(i,1,n)
        printf("%d ",a[i]);
    return 0;
}