P1247 取火柴游戏 （博弈论）

原题链接：取火柴游戏 - 洛谷

题目描述

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

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

输入格式

第一行，一个正整数 k。

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

输出格式

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

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

Nim游戏

(转载)Nim游戏博弈(收集完全版) - exponent - 博客园

博弈论 套路开始的地方（NIM游戏和Sprague-Grundy函数）_隐形的稻草人哦的博客-CSDN博客

在普通Nim游戏中，a1^a2^a3^……^an=0是必败态

如果一开始 a1^a2^a3^……^an=0，那么先手必败；如果一开始不为0，那么一定可以让一堆石子中的数减小使得下一轮a1^a2^a3^……^an=0

而只要从前往后找到(x ^ a[i]) < a[i])，那么新的a[i]值就是x ^ a[i]，可以让异或结果变为0

AC代码：

#include
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n)

const int N = 5e5 + 10;
int a[N];

int main()
{
    int n;
    cin >> n;
    int x = 0;
    rep(i, n) cin >> a[i], x ^= a[i];
    if(x == 0)
    {
        cout << "lose";
    }
    else
    {
        rep(i, n)
        {
            if((x ^ a[i]) < a[i])
            {
                cout << a[i] - (x ^ a[i]) << " " << i << endl;
                a[i] = a[i] ^ x;
                break;
            }
        }
        rep(i, n) cout << a[i] << " ";
    }
    return 0;
}