題意：給定1,2,3...N個數的集合，現在求所有非空子集（相同元素不同位置視為不同）按字典序排序后的第M個集合是什么？

思路：設i個不同元素組成的非空字典序子集為kind[i],通過遞推關系計算出kind[i] = i * (kind[i] + 1)可從計算式上推倒。得到這個關系后就可以通過一位一位的枚舉得到答案了。

代碼如下：

#include <iostream> #include <cstring> using namespace std;int seq[25], idx; long long kind[25]; int vis[25];void deal(int N, long long M) {bool finish = false;while (!finish) {for (int i = 1; i <= N; ++i) {if (M == 1) {seq[++idx] = i;finish = true;break;} else if (M > (kind[N-1] + 1)) {M -= kind[N-1] + 1;} else {seq[++idx] = i;M -= 1;N -= 1;break;}} } }int main() {int N;long long M;kind[1] = 1; for (int i = 2; i <= 20; ++i) {kind[i] = i * (kind[i-1] + 1); // i個不同元素集合的非空字典序子集個數 }while (cin >> N >> M) {memset(vis, 0, sizeof (vis));idx = -1;deal(N, M);int first = 1;for (int i = 0; i <= idx; ++i) {int x;// seq記錄的是一個偽序列，即確定一個數字后又將后面的序列重排 for (int j = 1; j <= N; ++j) {if (!vis[j]) --seq[i];if (!seq[i]) {if (first) {cout << j;first = 0;} else cout << " " << j;vis[j] = 1;break;}}}cout << endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU-2062 Subset sequence 递推的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。