【AtCoder】137C Distinct Numbers题解

题目大意

给定一个 $n$ 个数的集合，Alice 和 Bob 轮流操作，Alice 先操作，每次选最大的数，将其减少任意值，再放回集合（需一直满足集合中元素互不相同，且 $a_i \ge 0$）。

原题链接

思路

这是一道相当妙的博弈论，这个游戏是个 ICG，也就是说存在必胜策略。我们把数都从小到大排序（每次执行操作后也排序）。

我们假设：

• 先手把 $a_n$ 减少到比 $a_{n-1}$ 大一点的位置，即 $a_n = a_{n-1} + 1$。
• 如果先手把 $a_n$ 减少到比 $a_{n-1}$ 大更多（$a_n > a_{n-1} + 1$），那么先手可以直接把它减少到 $a_{n-1} + 1$，而后手只能继续减少。
• 如果先手把 $a_n$ 减少到小于 $a_{n-1}$，那么后手就利用 $a_n > a_{n-1} + 1$ 的策略反制。

那么假如 $a_n = a_{n-1} + 1$，游戏双方只能不断将 $a_n$ 减少到 $a_n = a_{n-1}$，直到无法操作——因为一旦不满足这个条件，另一方就能利用 $a_n > a_{n-1} + 1$ 的策略反制。

一直这么做的话，最终集合一定是 $0, 1, 2, \ldots, n-1$，且操作次数就是 $a_n - (n-1)$（与其它数无关，因为每次减少都不能和其它数重合，减少操作都在 $[0, a_n]$ 范围内）。

所以：

• 若 $a_n > a_{n-1} + 1$：Alice 可以先手制造优势，Alice 必胜。
• 否则：若 $a_n - (n-1)$ 为奇数，Alice 必胜；否则 Bob 必胜。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 3e5 + 7;

int n, a[maxN];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    if(a[n] - a[n - 1] > 1)
        printf("Alice\n");
    else {
        if((a[n] - (n - 1)) % 2)
            printf("Alice\n");
        else
            printf("Bob\n");
    }
    return 0;
}