CF1983D 题解
Skadi_H
·
·
题解
前言
大佬们的思路似乎都是基于逆序对考虑的，这里给出另一种思考的角度。
题意简述
给定长度为 n 的两个数组 a 和 b。
每次操作，可以选出四个数 l,r,x,y 满足 1 \leq l \leq r \leq n , 1 \leq x \leq y \leq n,r-l=y-x。将 a_l,a_r 交换，b_x,b_y 交换。
问是否能在若干次操作后是的 a,b 两数组相同。
# 思路
刚读到这个题，感觉是一道构造性质的题目，于是进行了一番手玩。
首先如果 **$a,b$ 两数组的元素组成不同**，直接**输出 `NO`** ，故接下来的讨论基于两数组的元素组成相同。
而注意到对于任意 $n$ 的排列 $p$ ，我们总能通过一些 $l=x,r=y$ 的操作使得数组 $a$ 与数组 $b$ 分别变为以 $p_i$ 为下标的排序方式，故接下来我们能够**任意调换任意一对 $a_i,b_i$ 的相对位置**。
接下来我们定义:
若存在一个集合 $\{s_1,s_2,...,s_k\}$，满足集合 $\{a_{s_1},a_{s_2},...,a_{s_k} \}$ 与集合 $\{b_{s_1},b_{s_2},...,b_{s_k} \}$ 相同，且对于任意包含 $s_1$ 的集合，$k$ 为最小值，则称下标 $\{s_1,s_2,...,s_k\}$ **组成一个 $k$ 元环**。
举例来说，对于下面一种情况：
```
1 2 3 4 5 6 7 8 9
2 3 1 6 4 5 8 7 9
{1,2,3}组成3元环
{4,5,6}组成3元环
{7,8}组成2元环
{9}组成1元环
```
这道题的本质实际上就是**判断是否能将两数组匹配为 $n$ 个 $1$ 元环**。
下面我们来手玩一些情况。
首先对于这个：
```
1 2
2 1
```
这是一个 **$2$ 元环**，是在样例中也出现了的**死局**，实际上这也是整道题目当中**唯一可能出现的无解的情况**。
紧接着，我们钦定一种操作方案，我们可以进行 $n-2$ 组操作，第 $i$ 组操作的目标是**将 $b$ 数组中的 $i$ 达到正确的位置**。
他们均可以使用：
- 先将 $b$ 数组中的 $i$ 移动到 $i+1$ 的位置
- 再将其移动到 $i$ 位置。
达成目标。
（由于每对数字的相对位置可以任意调换，这里省去了每组操作后对 $a$ 数组重新排序的步骤。）
这个构造方案还是很容易能得到的，不过下面还是给出证明，觉得简单可以直接跳：
对于第一步，由于前 $i-1$ 次操作保证了 $b$ 中 $1$ 到 $i-1$ 均已正确排序，则令 $t_i$ 为当前 $i$ 在数组 $b$ 当中的位置，很显然 $t_i>i$ 。我们可以至少选择 $l=x=i+1,r=y=t_i$进行一次操作，达成目标。
对于第二步，我们只需要选择 $l=n-1,r=n,x=i,y=i+1$ 即可达成目标。
故我们只需要判断最终操作后的末两位是否匹配即可，这是容易观察得到的。所以我们的构造方案出现的 $k$ 元环当中保证了 $k \leq 2$ 且 $2$ 元环最多只有一个。
接下来是这个 $3$ 元环：
```
1 2 3
2 3 1
```
很显然我们能够按照如下步骤进行操作：
```
1 2 3 -> 1 3 2 1 2 3
2 3 1 2 1 3 -> 1 2 3
```
由此可得 **$3$ 元环**有解。
下面是 $4$ 元环：
```
1 2 3 4 -> 1 4 3 2 1 4 2 3 -"sort(a)"->
2 3 4 1 2 1 4 3 -> 1 2 4 3
v v
1 2 3 4
1 4 3 2 2元环 NO
^ ^
```
它最终转变为了 $2$ 元环。
```
1 2 3 4 5 -> 1 5 3 4 2 1 5 3 2 4 -"sort(a)"->
2 3 4 5 1 2 1 4 5 3 -> 1 2 4 5 3
1 2 3 4 5 -> 1 2 5 4 3 1 2 5 3 4
1 5 4 3 2 1 5 2 3 4 -> 1 2 5 3 4 YES
```
它成功的匹配了。
事实上，我们有**结论 $1$**：
对 $k>2$ 时，任何 $k$ 元环都可以通过有限次操作得到**两个匹配的位置和一个 $k-2$ 元环**。
证明如下：
这里用一个长度为7的序列举例：
```
v v v v v v v v
1 2 3 4 5 6 7 -> 1 2 3 7 5 6 4 -> 1 2 3 5 7 6 4 -> 1 2 3 5 4 6 7 -> 1 2 3 4 5 6 7
1 2 4 5 6 7 3 1 2 4 3 6 7 5 1 2 3 4 6 7 5 1 2 3 4 5 7 6 1 2 3 4 7 5 6
^ ^ ^ ^ ^ ^ ^ ^
```
我们成功的将一个 $5$ 元环变成了与原先方向相反的 $3$ 元环不过这并不影响匹配。事实上，这个结论可以类似的推广，但可能写出来会有点占地方，故供感兴趣的读者自行尝试。
根据上述结论，我们可以将所有的环通过多次操作变为不超过 $2$ 元的环，故在初始时我们**只关心每个环元数的奇偶性**，并且**奇元环能够完成匹配，偶元环最终会剩下一个不能匹配的 $2$ 元环**。
不过，我们还有一种情况：
当两个 $2$ 元环挨在一起的时候，他们可以相互交换，使得四个位置均被匹配。
```
v v
1 2 3 4 -> 1 2 4 3
2 1 4 3 1 2 4 3
^ ^
```
所以我们就能得到**结论 $2$**：
**任意两个 $2$ 元环可以互相消耗**。
综合上述两个结论，我们就得到了只有一行的判断算法：
**在上述“环”的定义下，如果偶元环的个数为偶数，输出`YES`，否则输出`NO`。**
然后就结束了，代码也很好写。
在实现的时候，由于每个环之间操作具有独立性，我们只需要对每个环的元数进行计算并统计即可，不需要在算法当中对 $a,b$ 数组进行任何修改操作。
# 代码
```
#include <bits/stdc++.h>
using namespace std;
int t,n,cnt;
int a[200005],b[200005],pos[200005],arr[200005];
bool vis[200005];
void clear(){//清空函数
for(int i=1;i<=n;i++){
pos[a[i]]=0;
vis[i]=0;
arr[i]=0;
}
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n;
bool flag=1;
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
if(!pos[b[i]]){
flag=0;//如果有未同时出现在a,b数组的数字，直接输出NO
break;
}
}
if(!flag){//上述情况的特判
cout<<"NO\n";
clear();
continue;
}
//这里直接在a，b数组上反复横跳
for(int i=1;i<=n;i++){
arr[i]=pos[b[i]];
}
cnt=0;//偶环个数
for(int i=1;i<=n;i++){
if(vis[i])
continue;
int siz=0,pos=i;
while(!vis[pos]){
vis[pos]=1;
siz++;
pos=arr[pos];
}
if(!(siz&1))//如果为偶环，计数器++
cnt++;
}
//输出结果
if(cnt&1)
cout<<"NO\n";
else
cout<<"YES\n";
clear();//多测清空好习惯
}
return 0;
}
//Skadi_H
```
# 后记
审核老师辛苦了！