题解：CF286A Lucky Permutation

思路

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

bool check()
{
for(int i=1;i<=n;i++)
{
if(a[a[i]]!=n-i+1)
{
return 0;
}
}
return 1;
}
void dfs(int now)
{
if(flag)return;
if(now==n+1)
{
if(check())
{
flag=1;
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
exit(0);
}
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i]=1;
a[now]=i;
dfs(now+1);
vis[i]=0;
}
}
}

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

1
-1
-1
2 4 1 3

2 5 3 1 4
-1
-1
2 8 4 6 3 5 1 7

2 9 4 7 5 3 6 1 8
-1
-1
2 12 4 10 6 8 5 7 3 9 1 11

2 13 4 11 6 9 7 5 8 3 10 1 12
-1

我们发现答案是四个为一轮。当 $n$ 取模 $4$ 等于 $2$ 或者 $3$ 时答案为 $-1$。那剩下的两种答案直接构造数组。

数组构造方法，详细见图与代码。

代码

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lhs printf("\n");
using namespace std;
const int N=3e5+10;
const int M=2024;
const int inf=0x3f3f3f3f;
int n,a[N];
int main()
{
scanf("%d",&n);
if(n%4==2 or n%4==3)
{
printf("-1");
return 0;
} 
if(n%4)
{
int mid=(1+n)/2;
a[mid]=mid;
for(int i=1;i<mid;i+=2)
{
a[i]=i+1;
}
for(int i=mid+2;i<=n;i+=2)
{
a[i]=i-1;
}
for(int i=n-1;i>mid;i-=2)
{
a[i]=n-i;
}
for(int i=mid-1;i>1;i-=2)
{
a[i]=n-i+2;
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
}
else
{
int mid=n/2;
a[mid]=mid+2;
for(int i=1;i<mid;i+=2)
{
a[i]=i+1;
}
for(int i=mid-2;i>=2;i-=2)
{
a[i]=n-i+2;
}
for(int i=n-1;i>mid;i-=2)
{
a[i]=n-i;
}
for(int i=mid+2;i<=n;i+=2)
{
a[i]=i-1;
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
}
return 0;
}
/*
1
-1
-1
2 4 1 3

2 5 3 1 4
-1
-1
2 8 4 6 3 5 1 7

2 9 4 7 5 3 6 1 8
-1
-1
2 12 4 10 6 8 5 7 3 9 1 11

2 13 4 11 6 9 7 5 8 3 10 1 12
*/

原文地址：https://blog.csdn.net/lhschris/article/details/144776993

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！