题解：CF286A Lucky Permutation

思绪

这题是一道找规律的标题。一眼看不出规律可以先写个暴力输出一下。

1. bool check()
2. {
3.         for(int i=1;i<=n;i++)
4.         {
5.                 if(a[a[i]]!=n-i+1)
6.                 {
7.                         return 0;
8.                 }
9.         }
10.         return 1;
11. }
12. void dfs(int now)
13. {
14.         if(flag)return;
15.         if(now==n+1)
16.         {
17.                 if(check())
18.                 {
19.                         flag=1;
20.                         for(int i=1;i<=n;i++)
21.                         {
22.                                 cout<<a[i]<<" ";
23.                         }
24.                         exit(0);
25.                 }
26.                 return;
27.         }
28.         for(int i=1;i<=n;i++)
29.         {
30.                 if(!vis[i])
31.                 {
32.                         vis[i]=1;
33.                         a[now]=i;
34.                         dfs(now+1);
35.                         vis[i]=0;
36.                 }
37.         }
38. }

复制代码

输出前十四个答案，答案如下。

1. 1
2. -1
3. -1
4. 2 4 1 3
6. 2 5 3 1 4
7. -1
8. -1
9. 2 8 4 6 3 5 1 7
11. 2 9 4 7 5 3 6 1 8
12. -1
13. -1
14. 2 12 4 10 6 8 5 7 3 9 1 11
16. 2 13 4 11 6 9 7 5 8 3 10 1 12
17. -1

复制代码

我们发现答案是四个为一轮。当 nnn 取模 444 即是 222 大概 333 时答案为 −1-1−1。那剩下的两种答案直接构造数组。
数组构造方法，具体见图与代码。

代码

1. #include<bits/stdc++.h>
2. #include<cstring>
3. #include<queue>
4. #include<set>
5. #include<stack>
6. #include<vector>
7. #include<map>
8. #define ll long long
9. #define lhs printf("\n");
10. using namespace std;
11. const int N=3e5+10;
12. const int M=2024;
13. const int inf=0x3f3f3f3f;
14. int n,a[N];
15. int main()
16. {
17.         scanf("%d",&n);
18.         if(n%4==2 or n%4==3)
19.         {
20.                 printf("-1");
21.                 return 0;
22.         }
23.         if(n%4)
24.         {
25.                 int mid=(1+n)/2;
26.                 a[mid]=mid;
27.                 for(int i=1;i<mid;i+=2)
28.                 {
29.                         a[i]=i+1;
30.                 }
31.                 for(int i=mid+2;i<=n;i+=2)
32.                 {
33.                         a[i]=i-1;
34.                 }
35.                 for(int i=n-1;i>mid;i-=2)
36.                 {
37.                         a[i]=n-i;
38.                 }
39.                 for(int i=mid-1;i>1;i-=2)
40.                 {
41.                         a[i]=n-i+2;
42.                 }
43.                 for(int i=1;i<=n;i++)
44.                 {
45.                         printf("%d ",a[i]);
46.                 }
47.         }
48.         else
49.         {
50.                 int mid=n/2;
51.                 a[mid]=mid+2;
52.                 for(int i=1;i<mid;i+=2)
53.                 {
54.                         a[i]=i+1;
55.                 }
56.                 for(int i=mid-2;i>=2;i-=2)
57.                 {
58.                         a[i]=n-i+2;
59.                 }
60.                 for(int i=n-1;i>mid;i-=2)
61.                 {
62.                         a[i]=n-i;
63.                 }
64.                 for(int i=mid+2;i<=n;i+=2)
65.                 {
66.                         a[i]=i-1;
67.                 }
68.                 for(int i=1;i<=n;i++)
69.                 {
70.                         printf("%d ",a[i]);
71.                 }
72.         }
73.         return 0;
74. }
75. /*
76. 1
77. -1
78. -1
79. 2 4 1 3
81. 2 5 3 1 4
82. -1
83. -1
84. 2 8 4 6 3 5 1 7
86. 2 9 4 7 5 3 6 1 8
87. -1
88. -1
89. 2 12 4 10 6 8 5 7 3 9 1 11
91. 2 13 4 11 6 9 7 5 8 3 10 1 12
92. */

复制代码