设一个数组
�
=
{
2
,
3
,
4
,
3
,
5
,
1
}
b={2,3,4,3,5,1}，则
�
(
�
)
=
2
+
3
+
4
+
5
=
14
L(b)=2+3+4+5=14，
�
(
�
)
=
1
+
5
=
6
R(b)=1+5=6。
小芳希望小红构造一个长为
�
n 的排列
�
c，使得
�
(
�
)
+
�
(
�
)
=
�
L(c)+R(c)=k。请你帮帮小红。
也就是说大概是这样的：
联想截图_20250929164249
找到最高的位置，记为
�
p，那么
�
(
�
)
L(a)也就等于
[
1
,
�
]
[1,p]单调增的所有数相加；
�
(
�
)
R(a)等于
[
�
,
�
]
[p,n]从右向左单调增的所有数之和。由于答案要求我们构造一个长度为
�
n的排列，因此
�
n肯定会被计算两次，
�
−
1
n−1会被计算一次，所以
�
(
�
)
+
�
(
�
)
≥
3
×
�
−
1
L(a)+R(a)≥3×n−1。
考虑如何构造：不妨把
�
n方在最后一个位置，
�
−
1
n−1放在
�
n前面的位置，然后将构造
�
k需要的数按大到小放在
�
−
1
n−1的前面，没有用到的数放在
�
−
1
n−1和
�
n的中间即可。对于从
[
1
,
�
−
2
]
[1,n−2]构造
�
−
(
3
×
�
−
1
)
k−(3×n−1)，只需要贪心即可。
void solve() {
int n,k;
cin >> n >> k;
if(k<3*n-1||k>((1+n)*n/2+n)){
cout << -1 << endl;
return;
}
k-=3*n-1;
vector<int> vis(n+1);
vis[n]=vis[n-1]=1;
for(int i=n-2;i>=1;i--){
if(k>=i){
vis[i]=1;
k-=i;
}
}
if(k!=0){
cout << -1 << endl;
return;
}
vector<int> ans;
for(int i=1;i<=n-1;i++){
if(vis[i]) ans.push_back(i);
}
for(int i=1;i<=n-1;i++){
if(!vis[i]) ans.push_back(i);
}
ans.push_back(n);
for(int i:ans) cout << i << " ";
cout << endl;
}
F
对于一个数组，小苯可以做任意次如下操作：
∙
∙ 交换数组中的任意两个元素。
现在小红想要构造一个长为
�
n 的排列
�
a，对所有的
�
�
a
i
都满足
�
�
≠
�
a
i
=i，使得小苯将数组变为升序的最小操作数为
�
k。
请你帮帮小红。
题意：现在要求我们构造一个排列，要求对于任意
�
�
≠
�
a
i
=i，且将其变为
�
�
=
�
a
i
=i的最小操作次数为
�
k，一次操作可以交换排列中任意两个元素的位置。
前置知识：置换环。
我们考虑这样一个排列：
2 3 4 5 1
将其变为升序的最小操作次数为4次，也就是环的大小减1。我们可以对上面这样一个排列建图：
(
�
,
�
�
)
(i,a
i
)。我们通过
�
�
�
dfs可以得到
�
m个连通块，且每个连通块都是一个环，考虑要将这
�
m个连通块进行交换得到
�
n个自环的最小操作次数：首先可以知道交换一定是在环内，连通块之间交换一定是不优的；其次连通块内的最小操作次数为
�
�
�
−
1
sz
i
−1，其中
�
�
�
sz
i
为第
�
i个连通块的大小。这个也是很容易证明的。所以我们可以得到结论：最小操作次数
=
∑
�
=
1
�
(
�
�
�
−
1
)
=
∑
�
=
1
�
�
�
�
−
�
=
�
−
�
=∑
i=1
m
(sz
i
−1)=∑
i=1
m
sz
i
−m=n−m。
现在要求我们最小操作次数为
�
k，所以连通块的数量一定为
�
−
�
n−k，所以我们只需要构造有
�
−
�
n−k个连通块的排列就好。可以按照这样的方式构造一个连通块：对于
[
1
,
�
]
[1,m]，我们要将其构造为一个置换环，只需要让所有元素向左或者右轮循一次就即可，变为
2
,
3
,
4
,
5
,
6
,
…
,
�
,
1
2,3,4,5,6,…,m,1。
那么答案可以贪心构造，每次选择两个元素进行构造，最后所有元素为一组，可以知道环最多为
�
2
2
n
个，所以可以先对
�
k进行边界特判，最小操作次数肯定为
�
−
�
2
n−
2
n
，最大操作次数为
�
−
1
n−1。
void solve() {
int n,k;
cin >> n >> k;
if(k<(n-n/2)||k>n-1){
cout << -1 << endl;
return;
}
int l=1,r=2;
int m=n-k;
vector<int> ans;
while(m>1){
ans.push_back(r);
ans.push_back(l);
l=r+1;
r=l+1;
m--;
}
//最后一个环
r=n;
for(int i=l+1;i<=n;i++) ans.push_back(i);
ans.push_back(l);
for(int i=1;i<=n;i++){
cout << ans[i-1] << " \n"[i==n];
}
}
再多补一个置换环的题：https://codeforces.com/gym/630599/problem/G
题意为给定一个排列，现在可以交换任意两个元素，问使得排列有恰好一个逆序对的最小操作次数。
很显然答案肯定为这个样子
2
,
1
,
3
,
4
,
5
,
6
,
…
,
�
2,1,3,4,5,6,…,n，所以也就是我们将排列变为这个的最小操作次数。由上面的结论，我们可以知道将排列变为
1
,
2
,
3
,
…
,
�
1,2,3,…,n的最小操作次数为
�
−
�
n−m，
�
m为置换环的个数，之后再使用用一次将其变为答案这样。
现在只需要考虑会不会存在比这个操作次数更小的情况，我们发现如果恰好
1
和
2
1和2在同一个置换环内，那么答案为
�
−
�
−
1
n−m−1，否则为
�
−
�
+
1
n−m+1。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> p(n+1);
for(int i=1;i<=n;i++) cin >> p[i];
vector<vector<int>> g(n+1);
for(int i=1;i<=n;i++){
g[i].push_back(p[i]);
}
//可以使用tarjan进行缩点
vector<int> dfn(n+1),low(n+1),color(n+1),inq(n+1);
stack<int> stk;
int sscnt=0,tot=0;
auto tarjan=[&](auto&& self,int u)->void{
dfn[u]=low[u]=++tot;
stk.push(u);
inq[u]=1;
for(int v:g[u]){
if(!dfn[v]){
self(self,v);
low[u]=min(low[u],low[v]);
}else if(inq[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int v;
sscnt++;
do{
v=stk.top();
color[v]=sscnt;
stk.pop();
inq[v]=0;
}while(v!=u);
}
};
for(int i=1;i<=n;i++){
if(!dfn[i])
tarjan(tarjan,i);
}
int ans=n-sscnt;
if(color[1]==color[2]) ans--;
else ans++;
cout << ans << endl;
}
/*
5 1 4 3 2
5 1 2->2 1 5
4 3
*/
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
但是wa了，为什么呢？考虑有问题，因为答案的形式应该为
1
,
2
,
3
,
4
,
5
,
…
,
�
1,2,3,4,5,…,n，只交换其中一对相邻元素的形式，所以我们还需要对每个
(
�
,
�
+
1
)
(i,i+1)考虑是否在同一个置换环内，如果一个都没有，那么答案为
�
−
�
+
1
n−m+1，否则为
�
−
�
−
1
n−m−1。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> p(n+1);
for(int i=1;i<=n;i++) cin >> p[i];
vector<vector<int>> g(n+1);
for(int i=1;i<=n;i++){
g[i].push_back(p[i]);
}
//可以使用tarjan进行缩点
vector<int> dfn(n+1),low(n+1),color(n+1),inq(n+1);
stack<int> stk;
int sscnt=0,tot=0;
auto tarjan=[&](auto&& self,int u)->void{
dfn[u]=low[u]=++tot;
stk.push(u);
inq[u]=1;
for(int v:g[u]){
if(!dfn[v]){
self(self,v);
low[u]=min(low[u],low[v]);
}else if(inq[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int v;
sscnt++;
do{
v=stk.top();
color[v]=sscnt;
stk.pop();
inq[v]=0;
}while(v!=u);
}
};
for(int i=1;i<=n;i++){
if(!dfn[i])
tarjan(tarjan,i);
}
int ans=n-sscnt;
bool ok=false;
for(int i=1;i<n;i++){
if(color[i]==color[i+1]){
ok=true;
break;
}
}
if(ok) ans--;
else ans++;
cout << ans << endl;
}
/*
5 1 4 3 2
5 1 2->2 1 5
4 3
*/
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
