题解 | # 红魔馆的微瑕序位 #
红魔馆的微瑕序位
https://ac.nowcoder.com/acm/contest/127702/F
任意一个长度为
的排列，如果可以交换任意两个元素，最终使其排列递增即
的次数为
置换环是描述排列错位关系的核心结构，在
至的排列里，一群互相占据对方位置的数，顺着本该去的位置追踪，最终会形成一个闭环，这个闭环就是置换环
任意一个排列一定可以唯一的分解成若干个互不相交的置换环的并集，这是置换群伦中的一个基本定理
一个长度为
的置换环中，环中的所有元素，没有一个在正确位置，且元素之间是循环错位的，那么操作一次可将一个长度为的置换环拆成一个长度为的置换环以及一个长度为
的置换环.....由数学归纳法可得到操作次数是
假设长度为的排列中有
个置换环，减去每个置换环少的一个次数，所以就是
次
这道题目求混乱度
，那么就是存在一对相邻的位置交换，其他位置正确
-
如果存在
满足
在一个置换环里面，那么我可以减少一次操作不让
-
如果所有的
这段代码求出置换环的数量，并对每一个
经行编号
vector<int> pid(n + 1);
vector<bool> vis(n + 1);
int idx = 0;
for(int i = 1; i <= n; i ++){
if(vis[a[i]]) continue;
int x = a[i];
idx ++;
while(!vis[x]){
vis[x] = true;
pid[x] = idx;
x = a[x];
}
}
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
void solve(){
int n; cin >> n;
vector<int> a(n + 1), pid(n + 1);
vector<bool> vis(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
int idx = 0;
for(int i = 1; i <= n; i ++){
if(vis[a[i]]) continue;
idx ++;
int x = a[i];
while(!vis[x]){
vis[x] = true;
pid[x] = idx;
x = a[x];
}
}
int flag = 1;
for(int i = 1; i <= n - 1; i ++){
if(pid[i] == pid[i + 1]){
flag = -1;
break;
}
}
cout << n - idx + flag << endl;
return ;
}
signed main(){
HelloWorld;
int tt; cin >> tt;
while(tt --) solve();
return 0;
}
