Luogu p1088 [noip2004 popularization group] Martians

Portal ：https://www.luogu.com.cn/problem/P1088

A full permutation problem , You can take the valley of Los Angeles P1706 Write again .

P1706： https://www.luogu.com.cn/problem/P1706

      My first reaction when I saw the topic was DFS, Simulate the process of full permutation , Then find the order given by the Martians , And then look down M A full permutation will find the answer . But the data of the topic is open to 10000, It is obvious that such an approach will time out . So we can't find the order given by Martians slowly , It should be to lock the position of the array in the whole search process in a very short time , And then look down M Time . Ideas have , How to implement it in code ？ Other steps are better , The key is how to quickly find the order given by the Martians ？ 

      This leads to the core code jump of the solution     if (!amount) i = ans[step];  Readers can read the code snippet until the line and then turn to the explanation .

      This line of core code is to jump to the starting position of this search . Why do you write like this ？ Let's start with 1 To 5 For example , In use DFS Realization 1 To 5 When it's all lined up , The first full permutation is 1 2 3 4 5 . Because there are cycles in our search , We were able to enumerate all the cases . So if you put one DFS The recursive work stack of , It's a multiple cycle , So this multi cyclic i It's not the same , Are in a specific position , The number searched is equal to the number . Because we need to quickly find the order given by Martians , Each of the multiple loops of the sequence must be determined i Value . therefore i=ans[step];ans It is the arrangement given by Martians , From this, we can determine each i.

#include<iostream>
#define MAX 10005
using namespace std;
int ans[MAX]; bool visit[MAX];
//ans An array is used to store the sort order ,visit Mark 
int M = 0, N = 0, amount = 0;bool flag = false;
//amount Used to store the current full arrangement 
//flag It is used to judge whether the answer has been found 
void DFS(int step) {
	if (flag)return;
	// If you have found the answer, always return until DFS End of the function 
	if (step > N) {// The border 
		amount++;// A full permutation adds 1
		if (amount == M+1) {
			// The judgment conditions here should be noted that M+1
			// Because the order given by the Martians at the beginning was also added amount in 
			flag = true;// eureka 
			for (int i = 1; i <= N; i++)
				printf("%d ", ans[i]);
			// Output answers and return
			return;
		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (!amount) i = ans[step];
		// Core code , The problem will be solved with understanding 
		// Jump to this DFS The corresponding position of 
		// There is a detailed explanation outside the code segment 
		if (!visit[i]) {
			visit[i] = true;
			ans[step] = i;
			DFS(step + 1);
			visit[i] = false;
		}
		// Typical full arrangement template 
		// If not, you can put  P1706 Study the full permutation problem of, and then do this problem 
	}
}
int main(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		scanf("%d", &ans[i]);
	DFS(1);// from 1 Begin your search 
	return 0;// End of the flower 
}