AT1999 题解

PragmaGCC · 2021-06-11 23:29:18 · 题解

因为我们要选择的是最大的那一堆，所以先将整个序列从大到小排序。

举个例子：

1 1 4 5 1 4 1 9 1 9

排序后变成了这样

9 9 5 4 4 1 1 1 1 1

变成图：

0 0
0 0
0 0
0 0
0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

拿走最大的一堆就是拿走最左端的一列，每堆拿走一个就相当于抽走最底下一行。

然后我们发现这是一个两人在方格上走棋，只能往上或往右，谁先到边界谁输，请问谁必胜的问题。

如果一个点的右方和上方都是必胜点，则这个点为必败点。如果有一个是必败点，那么这个点是必胜点。

在这里边界必败。

将所有点的状态都标出来，定义一个点的状态为 f(x,y)=0/1。

我们发现 f(x,y)=f(x+1,y+1)。

证明：

• 若 f(x,y)=0，则 f(x+1,y)=1,f(x,y+1)=1。所以 f(x+2,y),f(x+1,y+1) 中必有一个是必败态。此时只能为 f(x+2,y)。因此，f(x+2,y+1)=1。同理可推出 f(x+1,y+2)=1。由 f(x+1,y+2)=1,f(x+2,y+1)=1 得到 f(x+1,y+1)=0。
• 若 f(x,y)=1，则 f(x+1,y),f(x,y+1) 中至少有一个为 0，不妨设为 (x,y+1) 。则 f(x+1,y+1)=0。

所以，我们只需要考虑极端（即只能向右/向上）的情况，对比两个方向上到边界的距离即可。

#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
bool cmp(int a, int b) { return a > b; }
int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        if (a[i + 1] < i + 1) {
            int cnt = 0;
            while(a[i+cnt+1] == i) cnt++;
            const bool f = ((a[i] - i) & 1) || (cnt & 1);
            puts(f ? "First" : "Second");
            break;
        }
    }
    return 0;
}