CF1672F2 Checker for Array Shuffling 做题记录

给定一个长 nn,值域 [1,n][1,n] 的数组 aa,定义 aa 的排列(任意打乱元素顺序后的数组)bb 的价值为最小的操作次数使得 b=ab=a,一次操作可以:

  • 选定两个 1i<jn1\le i<j\le n,交换 bib_ibjb_j

F1:给定 aa,构造价值最大的 bb

F2:给定 aabb,判断 bb 的价值是否最大;

1n2×1051\le n\le 2\times 10^5

F1 的做法很简单,先考虑 aa 各不相同的情况。那么对于一个 bb,设 nn 个点的有向图 GG 构造方法如下:

  • iibib_iaa 中的位置 jj 连一条有向边;

那么 bb 的价值即为 nG 中的环个数n-G\text{ 中的环个数}

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

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

代码如下:

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 其实也挺简单的,注意到合法的 bb 对应 GG 中环的个数一定等于 aa 中出现次数最多的数的出现次数,那么把出现次数最多的数删掉,如果剩下的数能构成环,则 bb 不合法。

判环直接弄个虚点 ctct,建 (iS)ct(i\in S)\to ctct(iT)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");
}