CF1139E Maximize Mex 题解

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;
}

此外，由于此题数据过水，直接正着来，经过一些常数优化也能过。代码在这，仅供参考。