The 2025 ICPC 德国 German Collegiate Programming Contest——M. Mex Hex（使用区间维护可行域）

题目大意

题目大意
有一只魔法山猫会对你进行 $n$ 次攻击，每次攻击有一个潜能值 $p_i$ 。你最终受到的痛苦值为所有未被防御的攻击潜能值的 $\text{mex}$ （即未出现在这些潜能值集合中的最小自然数）。

你拥有一个盾牌，激活后可以持续防御接下来的 $d$ 次攻击。盾牌失效后会强制进入冷却，冷却时间同样持续 $d$ 次攻击，冷却期间无法再次激活。你可以多次激活盾牌，最早可以在第 1 次攻击前激活。

请制定最佳防御策略，使得受到的痛苦值最小。

输入格式
第一行包含两个整数 $n$ 和 $d$ ( $1 \le n \le 10^5$ , $1 \le d \le n$ )，分别表示攻击总数和盾牌持续/冷却时间。
第二行包含 $n$ 个整数 $p_1, \dots, p_n$ ( $0 \le p_i < n$ )，表示每次攻击的潜能值。

输出格式
输出一个整数，表示可以达到的最小痛苦值。

样例 1

1 2	5 1 0 1 0 1 0

解释： $d=1$ 。可以在第 1、3、5 次攻击时激活盾牌（防御区间为 $[1,1], [3,3], [5,5]$ ），冷却区间为 $[2,2], [4,4]$ 。此时只有潜能为 1 的攻击击中你， $\text{mex}(\{1, 1\}) = 0$ 。

样例 2

1 2	5 2 0 1 0 1 0

解释： $d=2$ 。无论如何安排，冷却期间总会漏掉潜能为 0 和 1 的攻击。击中你的集合包含 $\{0, 1\}$ ， $\text{mex} \ge 2$ 。

样例 3

1 2	14 2 8 1 1 0 0 2 0 1 2 1 0 6 4 2

可以像图上一样防御。

样例 4

1 2	4 2 0 1 2 0

解释：最早只能在第 1 次攻击前激活，无法同时防御住第 1 个和第 4 个潜能为 0 的攻击（因为防御完第 1 个后，盾牌在第 2、3 个攻击期间防御，第 4 个攻击时可能刚结束或者在冷却，取决于具体激活时机，但无法跨越防御第 1 个和第 4 个而不防御中间的）。选择防御第 2、3 个攻击，漏掉第 1、4 个攻击（潜能均为 0）， $\text{mex}(\{0, 0\}) = 1$ 。

思路讲解

这道题目其实不是很难，其实就是维护一下可行域就可以了。

那么初始的可行域是从一，就是初始的可行域的左起点是 Max 一和 P 减 d 加一。右起点就是 P。然后在后面的过程当中，我们去不断的更新左起点。一旦当左起点它比右起点还大的时候，左起点比右起点大的时候呢，这个时候就说明我们需要新开一个区间了。然后我们新开区间的左起点，就是可行域的左端点，就是 L 加2乘以 d 和 P 减 d 加一中取一个 max 如果说然后这个可行域的 R 就是 P 。如果说 L 大于 R 那就说明就进不了可行域。就这个是错的，就 return false 就好了。

// 哦，这道题目的难点就在于这个 check 函数
// 负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖
auto check=[&](ll val) -> bool {
    if (g[val].empty()) {
        return true;
    }
    // 维护一段可行起点区间
    // 下面是起始的可行域。
    ll l=max(1ll,g[val][0]-D+1),r=g[val][0];
    for (int i=1;i<g[val].size();++i) {
        ll p=g[val][i];
        ll to_l=max(l,p-D+1);
        // 我们先要检查一下这个 L 啊，这个 L 如果超过这个 R 了以后，我们就需要新建一段区间了。
        if (to_l>r) {
            l=max(l+2*D,p-D+1);
            r=p;
            if (l>r) {
                return false;
            }
        }else {
            l=to_l;
        }
    }
    return true;
};

AC代码

AC
https://qoj.ac/submission/2032675
AC
https://codeforces.com/gym/106129/submission/362772763

源代码

/**
 * Problem: M. Mex Hex
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/M
 * Created: 2026-02-13 14:06:03
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,D;
    cin >> N >> D;
    vector<ll> A(N+2);
    vector<vector<ll>> g(N+2);
    set<ll> st_mex;
    for (int i=0;i<N;++i) {
        st_mex.insert(i);
    }
    for (int i=1;i<=N;++i) {
        cin>>A[i];
        st_mex.erase(A[i]);
        g[A[i]].push_back(i);
    }
    ll mex=*st_mex.begin();
    if (mex==0) {
        cout<<0<<"\n";
        return;
    }
    // 哦，这道题目的难点就在于这个 check 函数
    // 负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖
    auto check=[&](ll val) -> bool {
        if (g[val].empty()) {
            return true;
        }
        // 维护一段可行起点区间
        ll l=max(1ll,g[val][0]-D+1),r=g[val][0];
        for (int i=1;i<g[val].size();++i) {
            ll p=g[val][i];
            ll to_l=max(l,p-D+1);
            // 我们先要检查一下这个 L 啊，这个 L 如果超过这个 R 了以后，我们就需要新建一段区间了。
            if (to_l>r) {
                l=max(l+2*D,p-D+1);
                r=p;
                if (l>r) {
                    return false;
                }
            }else {
                l=to_l;
            }
        }
        return true;
    };
    for (ll i=0;i<mex;++i) {
        if (check(i)) {
            cout<<i<<"\n";
            return;
        }
    }
    cout<<mex<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2032675
AC
https://codeforces.com/gym/106129/submission/362772763

*/

心路历程（WA，TLE，MLE……）

这个 check 函数是负责什么呢？是负责检查该 VAL 是否可以被我们的防御魔法所全部覆盖。直接采用这个贪心啊，它其实是没那么简单的。因为虽然说第一个我们肯定是要覆盖的，但是呢我们并不一定要在第一个位置就启用这个防御魔法，我们可以在其更前面的位置启用这个防御魔法。

// 哦，这道题目的难点就在于这个 check 函数
auto check=[&](ll val) {
    ll st=-INF;
    for (auto p:g[val]) {
        if (p-st+1<=D) {
            continue;
        }
        if (p-st+1<=2*D) {
            return false;
        }
        st=p;
    }
    return true;
};