洛谷P3480 [POI2009] KAM-Pebbles 题解

题目链接：P3480 [POI2009] KAM-Pebbles

题意：

有 $N$ 堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。

两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件。

谁没有石子可移时输掉游戏。问先手是否必胜。

输入格式：

多组输入，第一行一个整数 $u$ 代表数据组数（$1\le u\le 10$）

接下来共 $2u$ 行，每两行代表一组数据：

第一行只有一个整数 $n~(1\le n\le 1000)$，表示石子堆数；

第二行有 $n$ 个整数用空格隔开，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆的石子个数，保证 $a_1\le a_2\le a_3\le \cdots\le a_n$。

对于每组数据，保证石子总数不超过 $10000$。

输出格式：

输出 $u$ 行，如果第 $i$ 组数据先手必胜，输出 TAK，否则输出 NIE。

设 $a_i$ 为第 $i$ 堆石子的个数，记 $b_i = a_i - a_{i-1}$ 。当我们在第 $i$ 堆拿了 $x$ 个石子时，

会使 $b_i \gets b_i - x$ ，并且 $b_{i + 1} \gets b_{i + 1} + x$ 。这相当于把第 $i$ 堆中的 $x$ 个石子转移到了 $i+1$ 堆。

那么这就是一个翻转的阶梯博弈（阶梯 Nim 游戏），判断和 $n$ 奇偶性相同的堆的异或和是否为 $0$ 即可。

这里简单介绍一下阶梯博弈吧。

有 $n$ 堆石子，每次可以从第 $i$ 堆的石子中拿走一部分放到第 $i-1$ 堆中，

或者把第 $1$ 堆中的石子拿走一部分。无法操作的人算输。求先手是否有必胜策略。

结论：阶梯博弈先手必胜当且仅当奇数堆的石子数异或和不为 $0$ 。

证明考虑先手的策略。考虑按照最优策略，首先将奇数堆中的石子转移到偶数堆，

当对方将奇数堆的石子转移到偶数堆，相当于进行对于奇数堆的普通 Nim 游戏，继续按最优策略即可；

当对方将偶数堆的石子转移到奇数堆，则我们可以把这部分石子继续往下拿，没有改变奇数堆的局势。

于是我们简单证明了阶梯博弈和奇数堆的 Nim 游戏等价。$\square$

时间复杂度 $\mathcal{O}(Tn)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int a[N], b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq;
    while(qwq--)
    {
        int n, res = 0; cin >> n;
        rep(i, 1, n) cin >> a[i];
        rep(i, 1, n) b[i] = a[i] - a[i - 1];
        for(int i = n; i > 0; i -= 2) res ^= b[i];
        cout << (res ? "TAK" : "NIE") << '\n'; 
    }
    return 0;
}