洛谷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;
}