CF1965A Everything Nim 题解

题目链接：Everything Nim

题意：

Alice 和 Bob 又在玩他们该死的游戏。

有 $n(1\le n \le 2\times 10^5)$ 堆石子，记石子数最小的那一堆有 $k$ 个石子

则一轮游戏（一局游戏有若干轮）中，可以选择同时从每个堆中取走 $x(1\le x \le k)$ 个石子。

如果到谁取的时候，没有任何石子存留了，则他就输了。

假设两个人都十分聪明，则当 Alice 先手时是否必胜？

如果最小的堆数为 $1$ ，则 Alice 和 Bob 会一直取，直到出现一个堆不为 $1$ 。

显然他们会取 $\operatorname{mex}(a_i) - 1$ 次，因此 $\mathrm{mex}$ 的奇偶性决定了事实上他们谁是先手。

可以证明，当 $\mathrm{mex}(a_i) < \max(a_i)$ 时，先手必胜，否则取决于 $\mathrm{mex}$ 的奇偶性。

因为先手取 $k-1$ 个可以一直维持自己的先手状态，而在最后剩下的一堆取 $k$ 个可以直接取胜

时间复杂度 $\mathcal{O}(n\log n)$ ，仅排序复杂度

代码：

#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 N ((int)(2e5 + 15))

int a[N], b[N];
void solve()
{
    int n, mex = 1; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) if(mex == a[i]) ++mex;
    if(mex > a[n]) {
        cout << ((a[n] & 1) ? "Alice" : "Bob") << '\n';
    }else {
        cout << ((mex & 1) ? "Alice" : "Bob") << '\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--) solve();
    return 0;
}