翻译中有一句话：校长将会从每个社团中各选出一个人。
就是一些人被分为一组，从每组中选一些人出来。
这就很容易想到通过二分图的匹配。
\(\operatorname{mex}\) 运算有一个显而易见的贪心：枚举每个值能否被匹配，第一个找不到的值就是答案。
由于 \(\operatorname{mex}\) 运算的值域与 \(n\) 同级，就可以从这方面入手。
我们从每个能力值 \(p_i\) 向社团 \(c_i\) 建边。
假如枚举的值为 \(i\)，与增广路算法相似，如果 \(i\) 能再找到匹配，那么 \(\operatorname{mex}\) 的值一定会大于 \(i\)，否则就找到了 \(\operatorname{mex}\) 运算的答案。
但如果是这样的话，外层需要枚举到 \(d\)，内层要枚举到最大值 \(V\)，再加上匈牙利算法的单次的时间复杂度 \({\mathrm{O}}(m)\)，就会使总时间复杂度高达 \({\mathrm{O}}(dmV)\)，当然会 TLE。
考虑优化。
突然感觉与这道题很像，都是枚举值域，然后匹配。
于是就想到了一个玄学优化：用时间戳来优化常数。
在 CF 上交了一次，应该是数据太水，还过了。
代码：
const int N = 5e3, inf = 1e9 + 7;
int n, m, now, D, T;
int c[N + 5], p[N + 5], d[N + 5];
int mat[N + 5], vis[N + 5];
int cnt, head[N + 5];
struct Edge {
int v, ti, nxt;
} e[N + 5];
int read() {
int ret = 0, sgn = 0;
char ch = getchar();
while (!isdigit(ch)) sgn |= ch == '-', ch = getchar();
while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
return sgn? -ret: ret;
}
void add(int u, int v, int ti) {
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].ti = ti;
head[u] = cnt;
}
bool dfs(int x) {
for (int i = head[x]; i; i = e[i].nxt)
if (e[i].ti > T && vis[e[i].v] != now) {
vis[e[i].v] = now;
if (mat[e[i].v] == -1 || dfs(mat[e[i].v])) { mat[e[i].v] = x; return 1; }
}
return 0;
}
int main() {
n = read(), m = read();
int W = 0;
for (int i = 1; i <= n; i++) p[i] = read(), W = max(W, p[i]);
for (int i = 1; i <= n; i++) c[i] = read();
D = read();
for (int i = 0; i <= n; i++) d[i] = inf; // 初始化到 n。
for (int i = 1; i <= D; i++) d[read()] = i;
for (int i = 1; i <= n; i++) add(p[i], c[i], d[i]);
for (int i = 1; i <= D; i++) {
T = i;
for (int j = 0; j <= m; j++) vis[j] = mat[j] = -1; // mat[j] 的值可能为 0 (p[i] == 0)
bool flag = 0;
for (int j = 0; j <= W; j++) {
now = j;
if (!dfs(j)) {
printf("%d\n", j);
flag = 1;
break;
}
}
if (!flag) printf("%d\n", W + 1);
}
return 0;
}
这样卡一下应该还是不能过，时间复杂度还是没有变。
发现答案肯定是单调不增的，于是倒序枚举，就用一个 \(ans\) 数组记录一下答案，输出即可。
时间复杂度 \({\mathrm{O}}(md)\)
核心代码：
for (int i = D; i; i--) {
T = i;
for (int j = 0; j <= m; j++) vis[j] = 0;
while (dfs(tot)) { // 答案是具有单调性的。
tot++;
for (int j = 0; j <= m; j++) vis[j] = 0;
}
ans[i] = tot;
}