题解：CF1943A MEX Game 1

Bronya16A · 2024-03-24 11:23:40 · 题解

题目大意

爱丽丝和鲍勃在大小为 n 的数组 a 上进行另一场博弈。爱丽丝从一个空数组 c 开始。双方轮流下棋，爱丽丝先开始。

轮到爱丽丝时，她从 a 中选取一个元素，将其追加到 c 中，然后从 a 中删除。

轮到鲍勃时，他从 a 中选取一个元素，然后从 a 中删除。

当数组 a 为空时，游戏结束。爱丽丝的分数定义为 c 的 \text{mex}。爱丽丝希望最大化她的得分，而鲍勃希望最小化她的得分。如果双方都以最优方式下棋，求爱丽丝的最终得分。

思路

我们发现如果某一个数的个数大于 1，则我们无论如何都能获得这个数，所以我们只需要考虑某个数的个数小于等于 1 的情况，我们从小到大枚举数，如果这个数没有则这个数就是 \text{mex}，否则我们发现我们只能得到个数为 1 的数当中最小的那个数，其他的都拿不到，最后输出即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define mkp make_pair
#define pll pair<ll,ll>
#define prq priority_queue
using namespace std;
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
ll cnt[200005];
ll x[200005];
vector<ll> g[200005];
int main() {
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll _ = read();
    while (_--) {
        ll n = read();
        for (int i = 1; i <= n; i++) {
            x[i] = read();
            cnt[x[i]]++;
        }
        bool flag = 0;
        for (int i = 0; i <= n; i++) {
            if (!cnt[i]) {
                cout << i << endl;
                break;
            }
            if (cnt[i] == 1 && !flag) {
                flag = 1;
            } else if (cnt[i] == 1) {
                cout << i << endl;
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            cnt[x[i]] = 0;
        }
    }
    return 0;
}