CF1882E2 Two Permutations (Hard Version) 做题记录

给定一个 $n$ 的排列 $a$ 和一个 $m$ 的排列 $b$。

每次操作你可以：

• 选择两个正整数 $1\le i\le n$ 和 $1\le j\le m$；
• 将 $a$ 修改为 $a_{[i+1,n]}a_ia_{[1,i-1]}$，将 $b$ 修改为 $b_{[j+1,n]}b_jb_{[1,j-1]}$；

构造一组操作使得 $p_i=i$ 且 $q_i=i$ 且操作次数最少。如果无解，输出 $-1$。

$1\leq n,m\leq 2500$。

显然若求出 $ma_{0/1}$ 和 $mb_{0/1}$ 表示操作次数为奇/偶数时复原 $a$ 和复原 $b$ 最少需要的操作次数，则最少的操作次数即为 $\min(\max(ma_0,mb_0),\max(ma_1,mb_1))$。

那么 $a$ 和 $b$ 独立。

考虑把 $a$ 放在环上，并加入一个 $0$ 代表开头。对于一次操作，$a$ 从：

$0Aa_iB$

变成了：

$0Ba_iA=a_iA0B$

那么一次操作相当于交换 $a_i$ 和 $0$。

那么枚举 $0$ 最终的位置，问题变成了每次交换 $a_i$ 和 $0$，求把一个 $0\sim n$ 的排列还原的最小操作次数和方案。

那么把置换环找出来，设 $l_{1\sim k}$ 为这些环的大小，其中 $0$ 在 $l_1$ 对应的环中，则最小操作次数显然为 $l_1-1+\sum\limits_{i=2}^k [l_i>1](l_i+1)$。因为除了 $0$ 所在的环，其它的环都要先和 $0$ 交换一次以便把 $0$ 加入当前环。

构造方案是简单的。

而根据置换环的性质，每次操作一定会改变环数的奇偶性，所以所有还原方案的操作次数奇偶性一定相同。

所以只需要找到最少的操作次数即可。

时间复杂度 $O(n^2)$，代码如下：

// Problem: Two Permutations (Hard Version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1882E2
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=2505,inf=1e8;

int n,m;
int a[S],b[S];
int ta[S];
int fa[S],siz[S],pos[S];
vector<int> ansa,ansb;

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

inline int calc(int n,int a[],int x)
{
	for(int i=0;i<=n;i++) ta[(i+x)%(n+1)]=a[i];
	for(int i=0;i<=n;i++) fa[i]=i,siz[i]=0;
	for(int i=0;i<=n;i++) fa[fnd(i)]=fnd(ta[i]);
	for(int i=0;i<=n;i++) siz[fnd(i)]++;
	int res=0;
	for(int i=0;i<=n;i++)
	{
		int rx=fnd(i);
		if(i==0) res+=siz[rx]-1,siz[rx]=1;
		else if(siz[rx]!=1) res+=siz[rx]+1,siz[rx]=1;
	}
	return res;
}

inline void getres(int n,int a[],int x,vector<int> &res)
{
	for(int i=0;i<=n;i++) ta[(i+x)%(n+1)]=a[i];
	for(int i=0;i<=n;i++) pos[ta[i]]=i;
	while(pos[0]!=0)
	{
		int u=pos[0],v=pos[u];
		res.push_back((v-pos[0]+(n+1))%(n+1));
		swap(pos[ta[u]],pos[ta[v]]);
		swap(ta[u],ta[v]);
	}
	for(int i=1;i<=n;i++)
	{
		if(ta[i]!=i)
		{
			res.push_back((i-pos[0]+(n+1))%(n+1));
			swap(pos[ta[0]],pos[ta[i]]);
			swap(ta[0],ta[i]);
			while(pos[0]!=0)
			{
				int u=pos[0],v=pos[u];
				res.push_back((v-pos[0]+(n+1))%(n+1));
				swap(pos[ta[u]],pos[ta[v]]);
				swap(ta[u],ta[v]);
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	int ra[2]={-1,-1},rb[2]={-1,-1};
	for(int i=0;i<=n;i++)
	{
		int val=calc(n,a,i);
		if(ra[val&1]==-1||val<calc(n,a,ra[val&1])) ra[val&1]=i;
	}
	for(int i=0;i<=m;i++)
	{
		int val=calc(m,b,i);
		if(rb[val&1]==-1||val<calc(m,b,rb[val&1])) rb[val&1]=i;
	}
	int r0=inf,r1=inf;
	if(ra[0]!=-1&&rb[0]!=-1) r0=max(calc(n,a,ra[0]),calc(m,b,rb[0]));
	if(ra[1]!=-1&&rb[1]!=-1) r1=max(calc(n,a,ra[1]),calc(m,b,rb[1]));
	if(r0==inf&&r1==inf) return puts("-1"),0;
	if(r0<r1)
	{
		getres(n,a,ra[0],ansa);
		getres(m,b,rb[0],ansb);
	}
	else
	{
		getres(n,a,ra[1],ansa);
		getres(m,b,rb[1],ansb);
	}
	int len=max(ansa.size(),ansb.size());
	printf("%d\n",len);
	for(int i=0;i<len;i++)
	{
		if(i<ansa.size()) printf("%d ",ansa[i]);
		else printf("%d ",i&1?1:n);
		if(i<ansb.size()) printf("%d\n",ansb[i]);
		else printf("%d ",i&1?1:m);
	}
	return 0;
}