洛谷题解 CF1716B 【Permutation Chain】

题意翻译

现在有一个长度为 $n$ 的数组 ${1,2,3,4,…,n}$ ,你每次操作可以交换其中任意两个数字的位置,但是要确保除了第一次交换是有两个数字不在原来的位置上外,后续每次操作之后只能增加一个不在原来位置上的数字(其实对应的就是题目中的 longest permutation chain

当所有数字都不在原来的位置时,操作结束

解题过程

首先根据题意,显然本题除了每组询问的 $chain$ 长度唯一外,操作过程并不唯一

题目其实就是要求我们构造一种操作使得符合上述题意

我这里采用的是先交换首位两个数字,再按照右左右左的顺序依次交换相邻两个数(因为第三组样例是)

貌似语言不好说明,那就举个例

$n$ 为奇数的例子

当 $n=5$ 时:

原始数组: $[1,2,3,4,5] \ \operatorname{fixedness}=5$

操作1: $[5,2,3,4,1] \ \operatorname{fixedness}=3$

操作2: $[5,2,3,1,4] \ \operatorname{fixedness}=2$

操作3: $[2,5,3,1,4] \ \operatorname{fixedness}=1$

操作4: $[2,5,1,3,4] \ \operatorname{fixedness}=0$

因此链长为 $5$

$n$ 为偶数的例子

$n=4$ 时:

原始数组: $[1,2,3,4] \ \operatorname{fixedness}=4$

操作1: $[4,2,3,1] \ \operatorname{fixedness}=2$

操作2: $[4,2,1,3] \ \operatorname{fixedness}=1$

操作3: $[2,4,1,3] \ \operatorname{fixedness}=0$

因此链长为 $4$

注意

不要漏了输出原始数组!

代码实现


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<cstdio>
using namespace std;

int n,m,t,num[110],l,r; //l,r分别是目前左右操作的位置
bool pd=false;

int main()
{
scanf("%d",&t);
while(t--)
{
l=1;
scanf("%d",&n);
r=n;
pd=false;
printf("%d\n",n);
for(int a=1;a<=n;++a)
{
num[a]=a;
printf("%d ",num[a]);
}
printf("\n");
if(n%2==0) //n为偶数时
{
while(l!=n/2+1||r!=n/2)
{
if(l==1&&r==n) //第一步
{
int tmp=num[l];
num[l]=num[r];
num[r]=tmp;
for(int a=1;a<=n;++a)
{
printf("%d ",num[a]);
}
printf("\n");
l++;
r--;
continue;
}
else
{
if(pd) //左边交换
{
pd=false;
int tmp=num[l];
num[l]=num[l-1];
num[l-1]=tmp;
for(int a=1;a<=n;++a)
{
printf("%d ",num[a]);
}
printf("\n");
l++;
}
else //右边交换
{
pd=true;
int tmp=num[r];
num[r]=num[r+1];
num[r+1]=tmp;
for(int a=1;a<=n;++a)
{
printf("%d ",num[a]);
}
printf("\n");
r--;
}
}
}
}
else //n为奇数时
{
while(r!=(n+1)/2-1)
{
if(l==1&&r==n) //第一步
{
int tmp=num[l];
num[l]=num[r];
num[r]=tmp;
for(int a=1;a<=n;++a)
{
printf("%d ",num[a]);
}
printf("\n");
l++;
r--;
continue;
}
else
{
if(pd) //左边交换
{
pd=false;
int tmp=num[l];
num[l]=num[l-1];
num[l-1]=tmp;
for(int a=1;a<=n;++a)
{
printf("%d ",num[a]);
}
printf("\n");
l++;
}
else //右边交换
{
pd=true;
int tmp=num[r];
num[r]=num[r+1];
num[r+1]=tmp;
for(int a=1;a<=n;++a)
{
printf("%d ",num[a]);
}
printf("\n");
r--;
}
}
}
}
}
return 0;
}

题目详见:https://www.luogu.com.cn/problem/show?pid=CF1716B