CF1508B Almost Sorted

· · 题解

题目传送门。

题意简述：定义一个排列 a_1,a_2,\cdots,a_n 是 “几乎有序” 的，当且仅当对于每一个位置 i\ (1\leq i<n)，满足 a_{i+1}\geq a_i-1。请求出长度为 n 的所有 “几乎有序” 的排列中，字典序第 k 小的那一个。 多组询问，1\leq \sum n\leq 10^5，1\leq k\leq 10^{18}。

考虑一个 “几乎有序” 的排列满足什么性质：给定的 a_{i+1}\geq a_i-1 保证了相邻的若干个递减的数，一定是依次减 1 的。因此，最终排列的形式一定是 b_1,b_1-1,\cdots,1,b_2,b_2-1,\cdots,b_1+1,\cdots,n,n-1,\cdots,b_c+1 。

上面的形式又可以这样描述：将 1\sim n 从左到右排成一排，相邻的两个数间有空隙。现在选择若干（设为 c）个空隙，并将这个排列切成 c+1 段区间（也就是在 b_1,b_2,\cdots,b_c 右边切一刀），将每一段区间翻转，就可以得到一个 “几乎有序”的排列。

不难发现，每一种切割方案，就对应了一个 “几乎有序” 的排列。反过来，如果有一个 “几乎有序” 的排列，那么我们就可以构造出相应的切割方案。也就是说，切割方案与符合条件的排列是一一对应的。

切割方案有 2^{n-1} 个（n-1 个空隙可以选择切或不切），所以 “几乎有序” 的排列个数就是 2^{n-1}。

至于字典序，可以证明：如果将所有空隙是（0）否（1）切割看成一个从左往右的二进制数，设其十进制数值为 v，那么该排列在所有长度为 n 的 “几乎有序” 的排列中，字典序第 v+1 小。

简要证明：设长度为 n 的二进制数从左到右的每一位分别为第 1,2,3,\cdots,n 位。考虑两个二进制数 x,y，不妨设 x>y。假设它们对应的切割方案所得到的排列为 ax,ay，那么因为 x>y，我们总能找到一个位置 i 使得 x,y 的前第 i-1 位都相同，且 x 的第 i 位为 1，y 的第 i 位为 0。注意 1 代表不切割，0 代表切割。这样一来，如果 ay_p=i，那么 ax_p>i，且 p 之前的所有位置 j\ (1\leq j<p) 都有 ax_j\geq ay_j。得证。

代码比较好写，注意特判一下 n\geq 62 的情况（此时 2^n>k）

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

using ll = long long;

ll n,k;
void solve(){
    cin>>n>>k,k--;
    if(n<62&&k>>n-1)return puts("-1"),void();
    for(int i=1,p=1;i<=n;i=p+1,p=i){
        while(p<n&&n-p<=62&&(k>>n-p-1)&1)p++;
        for(int j=p;j>=i;j--)cout<<j<<" ";
    } cout<<endl;
}

int main(){
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}