[HDOJ1027]Ignatius and the Princess II

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1027

最近学校断网了，VJ上不去，跑出来上网。

不想写难题，写点简单的不让自己手生。

求n个数的第m个全排列，这题怎么过都可以，不过暴力dfs的时候需要注意一点就是要加一个flag判断是否已经输出当前符合情况的全排列。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <set>
10 #include <stack>
11 #include <list>
12 #include <vector>
13 
14 using namespace std;
15 
16 const int maxn = 1010;
17 int n, m, flag;
18 int vis[maxn];
19 int arr[maxn];
20 
21 void solve(int k) {
22     if(flag) {
23         return ;
24     }
25     if(k == n) {
26         m--;
27         if(!m) {
28             for(int i = 0; i < n; i++) {
29                 printf("%d", arr[i]);
30                 putchar(i < n - 1 ? ' ' : '
');
31                 flag = 1;
32             }
33         }
34     }
35     for(int i = 1; i <= n; i++) {
36         if(!vis[i]) {
37             vis[i] = 1;
38             arr[k] = i;
39             solve(k+1);
40             vis[i] = 0;
41         }
42     }
43 }
44 
45 int main() {
46     // freopen("in", "r", stdin);
47     while(~scanf("%d %d", &n, &m)) {
48         memset(vis, 0, sizeof(vis));
49         flag = 0;
50         solve(0);
51     }
52 }

View Code

STL解法：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 #include <queue>
 8 #include <map>
 9 #include <set>
10 #include <stack>
11 #include <list>
12 #include <vector>
13 
14 using namespace std;
15 
16 int n, m;
17 int arr[1010];
18 
19 int main() {
20     // freopen("in.txt","r",stdin);
21     while(~scanf("%d %d", &n, &m)) {
22         for(int i = 1; i <= n; i++) {
23             arr[i] = i;
24         }
25         while(--m) {
26             next_permutation(arr+1, arr+n+1);
27         }
28         for(int i = 1; i <= n; i++) {
29             printf("%d", arr[i]);
30             putchar(i < n ? ' ' : '
');
31         }
32     }
33 }

View Code