CF1365C Rotation Matching解题报告

解题报告

CF1365C Rotation Matching解题报告：

更好的阅读体验

前言

一开始看到这道题是不想做的：

这个翻译。。。

最后还是看了一下英文题面，发现真的水。。。然后一下子就做出来了。

题意

题意：给定两个排列$a_1,a_2\cdots a_n$与$b_1,b_2\cdots b_n$，可以将$a$循环移动若干次（一次循环移动指将$a_1,a_2\cdots a_n$变为$a_n,a_1\cdots a_{n-1}$），求$a$排列$b$排列最多能有几个匹配（即相同位置的数相同）。
数据范围：$1\leqslant n\leqslant 2\cdot 10^5$。

分析

分析数据范围，这道题明显是$O(n)$，最多带上一两个$\log$或一个根号。

考虑循环移动的意义——$a$排列内数字的的相对位置不会改变（将环拆成链来看），同时因为$b$排列不会移动，因此对于原排列$a$与经过若干次操作的排列$a'$，存在一个数$d$（$0\leqslant d\leqslant n-1$）使$a_i=a_{(i+d)\ \bmod\ n}'$，即对于任意一个数$k$（$1\leqslant k\leqslant n$），$k$在$a$中的位置与在$a'$中的位置的距离（注意，这里的距离也是将环拆成链看的距离，后面的距离也是指这种距离）都是相等的。

因此，对于任意一个数$k$（$1\leqslant k\leqslant n$），$k$在$a$中的位置与$k$在$b$中的位置的距离就是使这两个数匹配的移动次数。

于是我们可以记录$1$到$n$所有数在$a$排列与$b$排列中的位置，然后计算他们之间的距离，即使它们匹配的移动次数，并记录每个移动次数的出现次数，最大的出现次数便是答案了。

代码

#include<stdio.h>
const int maxn=1000005;
int i,j,k,m,n,ans;
int a[maxn],b[maxn],c[maxn],d[maxn],cnt[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        c[a[i]]=i;
    }
    for(i=1;i<=n;i++){
        scanf("%d",&b[i]);
        d[b[i]]=i;
    }
    for(i=1;i<=n;i++)
        cnt[(c[i]-d[i]+n)%n]++;
    for(i=0;i<n;i++)
        ans=max(ans,cnt[i]);
    printf("%d\n",ans);
    return 0;
}