题解 AT1999 【Candy Piles】

· · 题解

Description

有 n 堆石子，每堆石子有 a_i 个，两人轮流操作。要么取走石子最多的一堆，要么将每堆石子取走 1 个。谁取走最后 1 个石子，谁就输了。假设两人都足够聪明，求先手必胜还是后手必胜。

(1 \leq n \leq 10^5,1 \leq a_i \leq 10^9)

Solution

不妨先按 a_i 从大到小排序。对于石子最多的一堆，只要不直接取完，那么这堆石子仍然是最多的。

举个例子，对于 \{a\} = \{7,7,7,6,4,4,4,2,2\}，排完序后能够得到下图。

对于取走石子最多的一堆，实际就是消去最左边一行；对于取走每堆石子取走 1 个，实际就是消去最下面一行。

我们不妨再把点阵转化为一个网格图。

从原点开始，每人每次可以选择向右或向上移动一格，向右代表消去最左边一行，向上代表消去最下面一行。很容易发现，当走到网格图的边界（下图中的实线部分）时，所有石子刚好被取完。

显然边界上的点都是必败点，因为谁走到边界谁就输了。

对于任意一个不在边界上的点，如果它的上面和右面都是必败点，那么这个点一定是必胜点。如果它的上面和右面有一个是必胜点，那它就是必败点。（下图用 ○ / × 分别表示必败点和必胜点）

因为从原点 (0,0) 出发，所以当原点是必胜点时，后手必胜；原点是必败点时，先手必胜。

将整个网格图构造出来复杂度太大，所以考虑找规律：

除了边界外，同一对角线上的点全部是相同类型的点。

我们可以通过算出原点最右上方且不在边界上的点的类型，来知道原点是必胜点还是必败点。

找到以原点为左下角的最大正方形，设其右上方顶点为 (i,i) 。当它到最上面且不在边界上的点的距离和最右面且不在边界上的点的距离其中一个为奇数时，这个点为必败点，反之这个点为必胜点。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5;
int n, a[MAXN + 5];

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    sort(a + 1, a + n + 1, greater<int>());
    for (int i = 1; i <= n; ++i)
        if (i + 1 > a[i + 1]) {//找到以原点为左下角的最大正方形，其右上方顶点为 (i, i) 
            int j = 0;
            for (; a[j + i + 1] == i; ++j);
            if (((a[i] - i) & 1) || (j & 1)) puts("First");
            else puts("Second");
            break;
        }
    return 0;
}