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;
}

标题:AcWing——420. 火星人
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/28/1611809742782.html