本文共 1613 字，大约阅读时间需要 5 分钟。

cf1509E - Almost Sorted

题意： 定义almost sorted的排列是$a_{i+1}\ge a_i-1$，给出排列长度n，问字典序第k大的排列

可以发现长度为n的满足的排列只有$2^{n-1}$个，注意直接位移会溢出，（n1e5)

自己刚开始在想从长度为n到长度为n+1的转移，前一半是每个数+1然后在开头放1，（没有什么头绪

题解感觉很妙很妙，

将n分块，每一段表示长度为$nu{m}_i$ 的顺序递减序列，这与要求的almost sorted排列一一对应，于是可以将问题转化过来

用0表示每个段的末尾，1表示剩下的，（最后一位必是0于是我们先不管）这样可以很愉快地得到一个二进制，他刚好就是k-1的二进制表示（二进制从0000开始，则第k个就是k-1的二进制

题解给了一张示意图（高度表示数

#include 
   
    using namespace std;typedef unsigned long long ll;ll n, k;string getBin(ll x) {       string s = "";    for (int i = 0; i < n; i++)        s += '0';    k--;    for (ll b = 0; b < min((ll) 60, (ll) (n - 1)); b++) {           if ((k >> b) & 1)            s[n - 2 - b] = '1';    }    return s;}vector
    
      vec;int main() {       ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int T;    cin >> T;    while (T--) {           vec.clear();        cin >> n >> k;        if (n <= 62 && k > (1ll << (n - 1))) {               cout << -1 << endl;            continue;        }        string tmp = getBin(k);        int len = tmp.size();        int cnt = 0;        for (int i = 0; i < len; ++i) {               if (tmp[i] == '0') {                   vec.push_back(cnt + 1);                cnt = 0;            } else {                   cnt++;            }        }        if (cnt) {               vec.push_back(cnt);        }        int nw = 0, pre = 0;        for (auto x: vec) {               pre = nw;            nw = nw + x;            for (int i = nw; i > pre; --i) {                   cout << i << " ";            }        }        cout << endl;    }    return 0;}