题解：CF1677C Tokitsukaze and Two Colorful Tapes
Eddie08012025
·
·
题解
题目性质
首先，发现 ca,cb 均为全排列，将 ca_i,cb_i 连一条边，最后形成的是若干个环。
对于一个环，对答案的贡献就是相连的两个点的权值（填充的数字）之差。
一个显然的性质，就是每个环要对答案做到最大贡献，大的值和小的值要交叉摆放，例如下图，这样放数字对答案的贡献最大：（每个点上的权值不一定代表其真实权值，而是所有权值排序后大小顺序）。
对于一个四个点的环，设其一到四点的真实值分别是 a_1,a_2,a_3,a_4，其对答案的最大贡献为
对于一个五个点的环，设其一到五点的真实值分别是 $b_1,b_2,b_3,b_4,b_5$，其对答案的最大贡献为
$b_5-b_1+b_5-b_2+b_4-b_2+b_4-b_3+b_3-b_1=2\times(b_5+b_4-b_2-b_1)$。
此时可以再手推一下六个点七个点的环找找规律，可以得到，$k$ 个点的环，对答案的贡献是大的 $\lfloor\frac{k}{2}\rfloor$ 个权值减小的 $\lfloor\frac{k}{2}\rfloor$ 个权值。
为了最大化答案，大的权值一定要尽量大，小的权值一定要尽量小。用一个变量 $q$ 记录 $\lfloor\frac{k}{2}\rfloor$ 的总和。答案为
$$ans=2\times\left(\sum_{i=n-q+1}^{n}i-\sum_{i=1}^{q}i\right)=2(n-q)q$$
对于环的处理，有很多方法，我用的是并查集去处理。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[100005],b[100005],p[100005],num[100005];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n;
int q=0,ans=0;
for(int i=1;i<=n;i++){
p[i]=i;
num[i]=1;
cin>>a[i];
}for(int i=1;i<=n;i++){
cin>>b[i];
int a1=find(a[i]),b1=find(b[i]);
if(a1!=b1){
p[a1]=p[b1];
num[b1]+=num[a1];
num[a1]=0;
}
}for(int i=1;i<=n;i++){
if(num[i]<=1)continue;
q+=num[i]/2;
}int i,j;
ans=2*(n-q)*q;
cout<<ans<<"\n";
}return 0;
}
```