CF1672F2 Checker for Array Shuffling 做题记录

给定一个长 $n$，值域 $[1,n]$ 的数组 $a$，定义 $a$ 的排列（任意打乱元素顺序后的数组）$b$ 的价值为最小的操作次数使得 $b=a$，一次操作可以：

• 选定两个 $1\le i<j\le n$，交换 $b_i$ 和 $b_j$；

F1：给定 $a$，构造价值最大的 $b$；

F2：给定 $a$ 和 $b$，判断 $b$ 的价值是否最大；

$1\le n\le 2\times 10^5$。

F1 的做法很简单，先考虑 $a$ 各不相同的情况。那么对于一个 $b$，设 $n$ 个点的有向图 $G$ 构造方法如下：

• 从 $i$ 向 $b_i$ 在 $a$ 中的位置 $j$ 连一条有向边；

那么 $b$ 的价值即为 $n-G\text{ 中的环个数}$。

考虑 $a$ 会相同的情况，那么无非就是 $S=\{i,b_i=x\}$ 和 $T=\{i,a_i=x\}$ 之间的 $|S|$ 条有向边可以任意确定，只要保证 $S$ 中的每个点都有出边，$T$ 中的每个点都有入边即可。

注意到若 $G$ 中的两个点 $x,y$ 在同一个环中且满足 $b_x=b_y$，则可以通过交换 $x,y$ 的出边来把这个环分裂成两个环，这显然不花费操作次数。所以价值最大的 $b$ 一定满足 $b_i$ 相同的 $i$ 不在同一个环内，那么直接乱构造就行了。

代码如下：

int n,m,a[S];
vector<int> vec[S],cir[S];
int ans[S];

inline void slove()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) vec[i].clear(),cir[i].clear();
	for(int i=1;i<=n;i++) vec[a[i]].pb(i);
	m=0;
	for(int i=1;i<=n;i++)
	{
		int id=0;
		for(int v:vec[i]) cir[++id].pb(v);
		m=max(m,id);
	}
	for(int i=1;i<=m;i++)
	{
		int ct=cir[i].size();
		for(int j=0;j<ct;j++)
		{
			int u=cir[i][j],v=cir[i][(j+1)%ct];
			ans[u]=a[v];
		}
	}
	for(int i=1;i<=n;i++) write(ans[i],' ');
	write('\n');
}

F2 其实也挺简单的，注意到合法的 $b$ 对应 $G$ 中环的个数一定等于 $a$ 中出现次数最多的数的出现次数，那么把出现次数最多的数删掉，如果剩下的数能构成环，则 $b$ 不合法。

判环直接弄个虚点 $ct$，建 $(i\in S)\to ct$，$ct\to (i\in T)$，然后拓扑判环集可。

代码如下：

int n,a[S],b[S];
vector<int> va[S],vb[S];
int cnt[S];
vector<int> g[S];
int ind[S];
queue<int> q;

inline void slove()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);
	for(int i=1;i<=n;i++) va[i].clear(),vb[i].clear();
	for(int i=1;i<=n;i++) va[a[i]].pb(i),vb[b[i]].pb(i);
	for(int i=1;i<=n;i++) cnt[i]=0;
	int mx=0;
	for(int i=1;i<=n;i++) mx=max(mx,++cnt[a[i]]);
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]==mx)
		{
			va[i].clear(),vb[i].clear();
			break;
		}	
	}
	for(int i=1;i<=n+n;i++) g[i].clear(),ind[i]=0;
	int cnt=n;
	for(int i=1;i<=n;i++)
	{
		cnt++;
		for(int id:vb[i]) g[id].pb(cnt),ind[cnt]++;
		for(int id:va[i]) g[cnt].pb(id),ind[id]++;
	}
	while(!q.empty()) q.pop();
	for(int i=1;i<=n+n;i++) if(ind[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:g[u]) if(--ind[v]==0) q.push(v);
	}
	for(int i=1;i<=n+n;i++) if(ind[i]!=0) return puts("WA"),void();
	puts("AC");
}