题解 P1088 【火星人】

这一题开始看到有一点蒙逼，但是有一种直觉告诉我，这个顺序就是全排列的顺序，所以我的想法是模拟一下深度优先搜索，就是说第一次搜索的时候直接到达外星人给出的那个结点，然后再慢慢回溯，等到求到的全排列是外星人给出的加上我们要加的数字时，我们就可以直接输出再结束程序了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn=10000+10;
int n,m,a[maxn],flag,flagx;
bool s[maxn];
void dfs(int step)
{
    if(flagx==1)
    return;
    if(step>n)
    {
        flag++;
        if(flag==m+1)//现在到了我们要加上的那个数的全排列的时候，我们就直接地输出，然后标记flagx，一直return，结束程序
        {
            for(int j=1;j<=n;j++)
            printf("%d ",a[j]);
            printf("\n");
            flagx=1;
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(flag==0)i=a[step];//当还在外星人给出的排列这个阶段的时候，我们就直指外星人给出的序列中的数    
        if(s[i]==0)
        {
            s[i]=1;
            a[step]=i;
            dfs(step+1);
            s[i]=0;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    dfs(1);
    return 0;
}