CF1365C Rotation Matching 题解

description：

• 给定两个长度为 $n$ 的 $1\sim n$ 的排列 $a_i,b_i$。

• 你可以对任意一个排列进行若干次长度为 $k$ 的 循环右移或左移；这里的循环移动指每个元素依次向左或右移动 $k$ 个，如果移出边界的元素再折回到排列的头或尾。

• 你需要求出在移动过后最多有多少个对应的位置使得 $a_i=b_i$。

• $1\le n\le 2\times 10^5$，$1\le a_i,b_i\le n$。

• translate by @ShineEternal。

solution：

我们直接在众多种移动方法中保留任意一种其实就行了。

我们对于 $a$ 中的每个元素，记录其与对应的 $b$ 中相等的元素所相差的距离，众数即为答案。

code：

#include<cstdio>
using namespace std;
int abs(int x)
{
	if(x<0)return -x;
	return x;
}
int max(int x,int y)
{
	if(x>y)return x;
	return y;
}
int a[200005],b[200005],dis[200005],mp0[200005],mp[200005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mp0[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		mp[b[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		dis[(n+mp0[i]-mp[i])%n]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,dis[i]);
	}
	if(n==1)printf("1\n");
	else
	printf("%d\n",ans);
	return 0;
}