Problem - 1819A - Codeforces

快速计算mex

int calcMex(vector<int> v) {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end())
	int n = int(v.size());
    for (int i = 0; i < n; ++i) if (v[i] != i) return i;
    return n;
}

<cassert> 调试宏

assert(条件表达式)

为真值，继续执行。非真值，终端报错。

\(std\)

//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

template <class A, class B>
bool smin(A &x, B &&y)
{
    if (y < x)
    {
        x = y;
        return true;
    }
    return false;
}

template <class A, class B>
bool smax(A &x, B &&y)
{
    if (x < y)
    {
        x = y;
        return true;
    }
    return false;
}

template <class T>
int calcMex(vector<T> v)
{
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int n = int(v.size());
    for (int i = 0; i < n; ++i)
        if (v[i] != i)
            return i;
    return n;
}

bool solveTest()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> leftOcc, rightOcc;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        rightOcc[a[i]] = i;
        if (!leftOcc.count(a[i]))
            leftOcc[a[i]] = i;
    }
    int mex = calcMex(a);
    if (leftOcc.count(mex + 1))
    {
        int L = leftOcc[mex + 1], R = rightOcc[mex + 1];
        for (int i = L; i <= R; ++i)
        {
            a[i] = mex;
        }
        int mx = calcMex(a);
        assert(mx <= mex + 1);
        return mx == mex + 1;
    }
    for (int i = 0; i < n; ++i)
    {
        assert(a[i] != mex);
        if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]]))
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cout << (solveTest() ? "Yes" : "No") << '\n';
    }
    return 0;
}

• 遇到 mex 的题目，一定要利用 mex 的特性。
• 比如这题，原数组的 mex 肯定是原数组中未出现的，而且 mex + 1 是可以继承于原数组（只要再加入 mex 并且确保没有 mex + 1 即可）