Description
\(n\) 个学生， \(m\) 个社团。每个学生有一个能力值，且仅属于一个社团。这 \(d\) 天内，每天从 \(m\) 个社团中选人，使得选出的人的能力值的 \(\text{mex}\) 最大。每天会有一个人在选人之前退团。
\(d,m \leq n \leq 5000\)
Solution
巧妙建图题。
-
首先，我们可以很显然的知道要想使得 \(\text{mex}\) 值最大，我们应该贪心地先选能力值小的人，直到有一个能力值不能被表示。
-
再次，我们考虑一个社团只能选一个人进行匹配、一个人和一个能力值相对应。于是我们可以将这个题抽象成一个二分图的问题：将能力值当成左部点，团体当成右部点。将一个社团里每个人的能力值和这个社团连边，跑最大图匹配即可。
-
到了这一步，我们发现这么做的复杂度是 \(O(nmd)\) 的，不足以解决此题，需要进一步优化。我们发现，多一个人的情况肯定不比少一个人的情况差，因此我们可以想出从最后一天倒序考虑，从人员退出转化成人员加入，这样以后枚举能力值的时候就不需要每次从 \(0\) 开始枚举了。时间复杂度降为 \(O(dm)\) ，可以通过。
需要注意的一些坑点：
（1）：因为 \(0\) 也可能是答案，所以 \(match\) 数组每次要初始化成 \(-1\) 而非 \(0\) ；
（2）：题目给出的是学生先离开社团校长再选人，所以倒过来的话就是先选人再把学生加入进去。
Code
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 5e4 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}
int match[N],vis[N],k[N],use[N];
int n,m,d,ans;
stack <int> st;
struct Node{
int p,c;
}a[N];
struct node{
int u,v,next;
}edge[N<<1]; int head[N],num_edge;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
il void add(int from,int to)
{
edge[++num_edge] = (node){from,to,head[from]};
head[from] = num_edge;
}
il bool dfs(int x)
{
for(re int i=head[x];i;i=edge[i].next)
{
int y = edge[i].v;
if(vis[y]) continue;
vis[y] = 1;
if(match[y] == -1 || dfs(match[y]))
{
match[y] = x;
return true;
}
}
return false;
}
il void Main(int id)
{
memset(vis , 0 , sizeof vis);
while(dfs(ans)) { ans++; memset(vis , 0 , sizeof vis);}
st.push(ans);
add(a[k[id]].p,a[k[id]].c);
}
signed main()
{
memset(match , -1 , sizeof match);
n = read() , m = read();
for(re int i=1;i<=n;i++) a[i].p = read();
for(re int i=1;i<=n;i++) a[i].c = read();
d = read();
for(re int i=1;i<=d;i++) k[i] = read() , use[k[i]] = 1;
for(re int i=1;i<=n;i++) if(!use[i]) add(a[i].p,a[i].c);
for(re int i=d;i>=1;i--) Main(i);
while(!st.empty()) cout << st.top() << "\n" , st.pop();
return 0;
}
此外，由于此题数据过水，直接正着来，经过一些常数优化也能过。代码在这，仅供参考。