【題目鏈接】

ybt 1929：【04NOIP普及組】火星人
洛谷 P1088 [NOIP 2004 普及組] 火星人

【題目考點】

1. 深搜回溯

2. STL next_permutation函數

頭文件<algorithm>
函數定義：next_permutation(lb, ub, cmp)
lb：區間下界，為指針或迭代器
ub：區間上界，為指針或迭代器
cmp：函數或仿函數，指定比較規則，默認為less仿函數。
使區間[lb, ub)范圍內的元素變為其下一個排列，復雜度為$O(n)$

如果不傳參數cmp，對整型序列取其下一個排列，其下一個排列就是將[lb, ub)區間內元素的全排列按字典序升序給出后，當前序列的下一個序列。

【解題思路】

火星人的手指排列就是一個1到n的排列，該排列表示的數就是該排列在按字典序排序的1到n的全排列中是第幾個排列。
要想使該排列表示的數加上m，而后得到手指序列，就是要取按字典序排序的在1到n的全排列中，當前排列后的第m個排列。

解法1：深搜回溯

深搜求全排列是深搜回溯的模板題，相信各位同學都會寫的。

#include <bits/stdc++.h>
using namespace std;
int num[10005], n, m;
bool vis[10005];
void dfs(int k)
{if(k > n){for(int i = 1; i <= n; ++i)cout << num[i] << ' ';cout << '\n';return;}for(int i = 1 ; i <= n; ++i) if(!vis[i]){num[k] = i;vis[i] = true;dfs(k + 1);vis[i] = false;}
}
int main()
{cin >> n >> m;dfs(1);return 0;
}

而現在是需要從深搜回溯求全排列的中間某狀態出發，向后繼續搜索，搜索到第m個排列時輸出。

這個過程好比一個話劇，一開始就要從第二幕開始演，那么需要直接布置第二幕的舞臺，相關演員也要好像第一幕都演完了的一樣，直接開始第二幕演出。而不需要重新從第一幕開始演。

當前num數組的初值實際是通過輸入得到的。我們需要讓num數組當前的值是通過搜索得到的。
這是一個預先處理的過程，設bool類型量pre，初值為真，pre為真表示當前在進行預處理，使整個dfs過程達到剛好搜索出輸入的num序列的狀態。
調用dfs(1)，搜索確定第一個數的值，如果第1個數的值是num[1]，那么此時i循環到的值應該是num[1]。
遞歸調用dfs(2)，搜索確定第二個數的值，如果第2個數的值是num[2]，那么此時i循環到的值應該是num[2]
…
調用dfs(k)時，確定第k個數是num[k]，那么該次調用中i應該循環到num[k]。因此在dfs(k)中，for循環i的初值應該設為num[k]。
當k>n時，進入搜索的遞歸出口，此時應該結束預處理，將pre設為假。
而后就開始正常的搜索排列的過程，非預處理狀態下for循環i的初值應該為1。
設計數變量ct，每搜索到一個排列計數增加1。當計數達到m時，找到了輸入序列后的第m序列，將其輸出，而后結束遞歸。

解法2：使用next_permutation

STL中的next_permutation可以取一個序列的下一個排列。循環m次，每次循環取下一個排列，再將序列輸出，即為結果。

【題解代碼】

解法1：深搜回溯

#include <bits/stdc++.h>
using namespace std;
int num[10005], n, m, ct;
bool vis[10005], isPre = true;//isPre：是否在進行預處理 
void dfs(int k)
{if(k > n){if(isPre){isPre = false;return;}if(++ct == m)//如果已經搜索到后面第m個排列，則輸出結果 {for(int i = 1; i <= n; ++i)cout << num[i] << ' ';}return;}if(ct == m)//ct為m表示已經輸出結果，結束搜索 return;for(int i = isPre ? num[k] : 1 ; i <= n; ++i) if(!vis[i]){num[k] = i;vis[i] = true;dfs(k + 1);vis[i] = false;}
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> num[i];dfs(1);return 0;
}

解法2：使用next_permutation

#include <bits/stdc++.h>
using namespace std;
#define N 10005
int n, m, a[N];
int main()
{cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= m; ++i)next_permutation(a+1, a+1+n);for(int i = 1; i <= n; ++i)cout << a[i] << ' ';return 0;
}