HDU 6628 permutation 1 (暴力)

2019 杭电多校 5 1005

题目链接：HDU 6628

比赛链接：2019 Multi-University Training Contest 5

Problem Description

A sequence of length is called a permutation if and only if it's composed of the first positive integers and each number appears exactly once.

Here we define the "difference sequence" of a permutation as . In other words, the length of the difference sequence is and the -th term is

Now, you are given two integers . Please find the permutation with length such that the difference sequence of which is the -th lexicographically smallest among all difference sequences of all permutations of length .

Input

The first line contains one integer indicating that there are tests.

Each test consists of two integers in a single line.

Output

For each test, please output integers in a single line. Those integers represent a permutation of to , and its difference sequence is the -th lexicographically smallest.

Sample Input

7
3 1
3 2
3 3
3 4
3 5
3 6
20 10000

Sample Output

3 1 2
3 2 1
2 1 3
2 3 1
1 2 3
1 3 2
20 1 2 3 4 5 6 7 8 9 10 11 13 19 18 14 16 15 17 12

Solution

题意：

定义排列 的 "difference sequence" 为 。现在给定 和 ，求长度为 的所有排列中 "difference sequence" 的字典序第 小的排列。

题解：

暴力 STL 全排列

题目给定 的范围不超过 ，而 ，因此可以预处理 的情况，当 时暴力求 的全排列。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

struct P {
    int num[10];
    string str;
} ans[10][maxn];

int cmp(P p1, P p2) {
    return p1.str < p2.str;
}

int main() {
    int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    for(int i = 2; i <= 8; ++i) {
        int cnt = 1;
        do {
            // for(int j = 0; j < i; ++j) {
            //     cout << a[j] << " ";
            // }
            // cout << endl;
            for(int j = 1; j <= i; ++j) {
                ans[i][cnt].num[j] = a[j];
                if(j < i) ans[i][cnt].str += a[j + 1] - a[j] + 'A';
            }
            ++cnt;
        } while(next_permutation(a + 1, a + 1 + i));
        sort(ans[i] + 1, ans[i] + cnt, cmp);
        // for(int j = 1; j < cnt; ++j) { for(int k = 1; k <= i; ++k) cout << ans[i][j].num[k] << ""; cout << endl;}
    }
    int T;
    cin >> T;
    while(T--) {
        int n, k;
        scanf("%d%d", &n, &k);
        if(n <= 8) {
            for(int j = 1; j <= n; ++j) {
                printf("%d", ans[n][k].num[j]);
                printf("%s", j == n? "\n": " ");
            }
        } else {
            int a[30];
            a[1] = n;
            for(int i = 2; i <= n; ++i) {
                a[i] = i - 1;
            }
            for(int i = 0; i < k - 1; ++i) {
                next_permutation(a + 1, a + 1 + n);
            }
            for(int i = 1; i <= n; ++i) {
                printf("%d", a[i]);
                printf("%s", i == n? "\n": " ");
            }
        }
    }
    return 0;
}