AcWing——420. 火星人
2021-01-28
火星人
题意:
给定n个数是1-n的排列数,亦或者理解为1-n的置换,然后求向后m个排列数为多少
例如:
1 2 3 4 5 是初始的5个数,让求向后3个的排列数
向后一个:1 2 3 5 4
向后两个:1 2 4 3 5
向后三个:1 2 4 5 3
思路:
给定组合求向后m个排列数 ,dfs(x,f) x代表该填充第x个数,f代表是否从原始的数组转移过来的
当填充到n个数的时候就让m--,当m等于0时输出答案即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int ans[N];
int vis[N];
int temp;
bool an=false;
//给定组合求向后m个排列数
void dfs(int x,bool f){
//若存在即退出
if(an) return;
if(x>n) {
temp--;
if(temp==0) {
for(int i=1;i<=n;i++) {
if(i>1) cout<<' ';
cout<<ans[i];
}
puts("");
an=true;
return ;
}
}
//枚举每一位的值
if(x>n) return ;
int i;
if(f) i=a[x];
else i=1;
for(;i<=n;i++) {
if(!vis[i]) {
vis[i]=1;
ans[x]=i;
if(!f) dfs(x+1,f);
else {
if(i!=a[x]) dfs(x+1,!f);
else dfs(x+1,f);
}
vis[i]=0;
ans[x]=0;
}
}
}
int main()
{
int m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
temp=m+1;
dfs(1,true);
return 0;
}