P1088 [NOIP2004 普及组] 火星人（全排列）

题目链接: 火星人

思路分析: 分析题目题意得到，这个题目关于全排列的问题，题目输入N,M分别代表对1——N进行全排列，火星人给出的大数就是1——N全排列的一种情况，对全排列的所有情况进行编号，例如下图：

例如上图N=3,假设M=2,给出一种全排列序列2,1,3那么最后输出应该是3,1,2因为图中2，1，3是全排列的第3种情况加上M得到第五种情况3,1,2。所以分析样例可以得到我们只需要根据题目给出的序列，开始全排列M次的到最后的结果就是题目所要求的.题目两种解法
解法1.使用c++中的全排列函数next_purmutation(),执行一次就会得到一种情况，只需要输入序列循环m次执行得到结果

#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum=0;
int ans[10010];//存储答案

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>ans[i];
	}
	for(int i=1;i<=m;i++){
		next_permutation(ans,ans+n);	
	}
	for(int i=0;i<n;i++){
		cout<<ans[i]<<" ";
	}
	
}

解法2，自定义dfs()全排列函数，从给出的序列开始递归搜索

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10005];//初始化的输入序列
int ans[10005];//保存结果答案
bool vis[10005];//记录是否已经访问过
int cnt=0;//标记是否是第一个初始化序列，cnt！=0说明已经将初始化输入的序列赋值给了ans数组
void dfs(int x){
	//表示已经得到了该序列，不需要继续递归搜索
	if(cnt>m){
		return;
	}
	if(x>n){
		cnt++;//统计序号
		//打印结果
		if(cnt==m+1){
			for(int i=1;i<=n;i++){
					cout<<ans[i]<<" ";
			}
			cout<<endl;
		}
		
		return;
	}
	for(int i=1;i<=n;i++){
		//初始化状态
		if(!cnt){
			//表示第一个数访问
			i=a[x];
		}
		// i 这个数没有访问
		if(!vis[i]){
			//访问这个数字
			vis[i]=true;
			//并将这个数字存储
			ans[x]=i;
			//接着访问接下来的数
			dfs(x+1);
			//回溯
			vis[i]=false;
		}
	}
}
int main(){
	//输入几根手指，也就是对几进行全排列
	//m表示在初始化输入元素的基础上加上多少
	cin>>n>>m;
	//输入初始数输入数组
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1);
}