题目地址：洛谷：【P2148】[SDOI2009]E&D – 洛谷、BZOJ：Problem 1228. — [SDOI2009]E&D

题目描述

小E 与小W 进行一项名为“E&D”游戏。
游戏的规则如下： 桌子上有2n 堆石子，编号为1..2n。其中，为了方便起见，我们将第2k-1 堆与第2k 堆 （1 ≤ k ≤ n）视为同一组。第i堆的石子个数用一个正整数Si表示。 一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆 石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子 数必须保证大于0。显然，被分割的一堆的石子数至少要为2。 两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为1，则此时 没有石子可以操作，判此人输掉比赛。
小E 进行第一次分割。他想知道，是否存在某种策 略使得他一定能战胜小W。因此，他求助于小F，也就是你，请你告诉他是否存在必胜策略。 例如，假设初始时桌子上有4 堆石子，数量分别为1,2,3,1。小E可以选择移走第1堆， 然后将第2堆分割（只能分出1 个石子）。接下来，小W 只能选择移走第4 堆，然后将第3 堆分割为1 和2。最后轮到小E，他只能移走后两堆中数量为1 的一堆，将另一堆分割为1 和1。这样，轮到小W 时，所有堆的数量均为1，则他输掉了比赛。故小E 存在必胜策略。

题意简述

有一个游戏，给偶数堆石子，两个相邻石子为一组，游戏的每次操作要选出一组，将其中一堆石子移走并将另外一堆分成两堆作为新的一组石子。当一方无法进行操作的时候即输，求是否存在先手必胜策略。

输入输出格式

输入格式：
第一行是一个正整数T（T ≤ 20），表示测试数据数量。接下来有T组 数据。 对于每组数据，第一行是一个正整数N，表示桌子上共有N堆石子。其中，输入数据保 证N是偶数。 第二行有N个正整数S1..SN，分别表示每一堆的石子数。

输出格式：
包含T 行。对于每组数据，如果小E 必胜，则输出一行”YES”，否则 输出”NO”。

输入输出样例

输入样例#1：

2
4
1 2 3 1
6
1 1 1 1 1 1

输出样例#1：

YES
NO

说明

【数据规模和约定】
对于20%的数据，N = 2；
对于另外20%的数据，N ≤ 4，Si ≤ 50；
对于100%的数据，N ≤ 2×10^4 ，Si ≤ 2×10^9 。

题解

参考资料：bzoj1228 [SDOI2009]E&D（博弈【规律） – CSDN博客
这里可以将一组石子视为一个独立的Nim游戏，根据SG定理，所有组的SG值异或和非0即为先手必胜，反之为先手必败。
一组石子的SG如何来求，我们当然可以采用爆搜，但是时间不允许。然后我们可以打个表，设SG(x, y)为一组的状态为(x, y)时的SG值，发现SG值有以下规律：
SG(x, y) = \begin{cases} 0, & x, y都是奇数 \\ SG(\lceil \frac{x}{2} \rceil, \lceil \frac{y}{2} \rceil) + 1, & x, y至少有一个是偶数 \end{cases}
于是现在这个搜索的复杂度就变成了O(\log n)的了，现在我们有了一个O(n \log n)的优秀做法。
关于这张表长什么样子，可以看参考资料那位同学的博文。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

int T, n, x, y;

inline int sg(int x, int y) {
    if((x & 1) && (y & 1)) return 0;
    else if(!(x & 1) && !(y & 1)) return sg(x >> 1, y >> 1) + 1;
    else if(x & 1) return sg((x + 1) >> 1, y >> 1) + 1;
    else return sg(x >> 1, (y + 1) >> 1) + 1;
}

int main() {
    T = readint();
    while(T--) {
        int res = 0;
        n = readint() >> 1;
        for(int i = 1; i <= n; i++) {
            x = readint(); y = readint();
            res ^= sg(x, y);
        }
        if(res) puts("YES"); else puts("NO");
    }
    return 0;
}