补题记录B. Almost Sorted

B. Almost Sorted

方法:组合数
这题起初看的时候真的毫无头绪啊,大概知道如何构造但是确实不知道如何构造出第k个排列。然后看了一下CF官方的题解之后豁然开朗,实在是太巧妙了。
首先我们要知道,对于相邻的两个数\(a[i]\)和\(a[i + 1]\),如果要满足题意,要不\(a[i + 1] > a[i]\),要不\(a[i] - a[i + 1] = 1\)。因此我们可以知道,一个合法序列中下降的序列一定是逐渐递减的。那么我们可以通过对一个排列1,2,3...n中的一些连续数字,将其倒转即可。当然我们选择的任意两个区间不能有交集,否则就无法满足题意。
那么知道了如何构造之后,我们如何计算出第k个的排列呢?
这里首先要提一个问题:像这样的排列,对于n有几个?
答案:\(2^{n - 1}\)个
回答这个问题就是要引出我们这里一个巧妙的计算方法。我们可以将一段合法排列中的递减序列的末位标记为0,其余标记为1。
例如:1432765这个排列就可以标记为0110110。
容易知道,对于任意一个合法的排列,其最后一位都是0,那么剩下的n-1位可以取0,可以取1。于是总共就有\(2^{n - 1}\)个了。
那么有无解就很好办了,判断\(k\)和\(2^{n - 1}\)的关系即可。
那么我们为什么要用二进制来表示呢,因为相应排列的二进制表达的数(不包括最后一位)+ 1就是这个排列在总共中的第k个。
换句话说,我们把k - 1用二进制表示写出来,然后再转换回排列,就是答案。
那为什么这样一定就是第k个呢?
这个不太好直接证明。但是我们可以通过自己构造找规律的方法,这里用n = 3来举个例子。
合法排列如下
1 2 3 (0 0 0 )
1 3 2 (0 1 0 )
2 1 3 (1 0 0 )
3 2 1 (1 1 0 )
我们可以看出,去掉最后一位就是0~3的二进制表达了。
通过这样的构造方法,我们也知道了如何把二进制转化为排列,就是看0的位置,如果之前没有1的就不用管。如果出现了类似111...0这样连续1然后0结尾的,说明这里是连续递减的序列,我们就把这一段在最初的排序中reverse一下即可。具体看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
inline int lc(int u) {return u << 1;}
inline int rc(int u) {return u << 1 | 1;}
inline int lowbit(int x) {return x & (-x);}
int a[N];
inline void solve() {
    LL n, k; cin >> n >> k;
    if (n < 62 && k > (LL)pow(2, n - 1)) {
        puts("-1");
        return ;
    }
    for (int i = 1; i <= n; i ++ ) a[i] = i;//原始数组
    a[n + 1] = 0;
    k -- ;
    //这里开始分解k
    string s;
    s += '0';
    while (k) {
        s += char((k & 1) + '0');
        k >>= 1;
    }
    while (s.size() < min(n, 63ll)) s += '0';//因为要分解到最多long long的长度
    reverse(s.begin(), s.end());
    if (n > s.size()) {//这里要注意,如果我们把k分解出来之后的长度比n要小,说明我们只要处理后面一段即可,前面就放着
        int last = int(n - s.size() + 1);
        for (int i = (int)n - (int)s.size() + 1; i <= n; i ++ ) {
            int now = i - int(n - s.size() + 1);
            if (s[now] == '1') continue;
            reverse(a + last, a + i + 1);
            last = i + 1;
        }
    } else {
        int last = 1;
        for (int i = 1; i <= n; i ++ ) {
            if (s[i - 1] == '1') continue;
            reverse(a + last, a + i + 1);
            last = i + 1;
        }
    }
    for (int i = 1; i <= n; i ++ ) cout << a[i] << ' ';
    cout << endl;
}
int main() {
//    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while (t -- )
        solve();
    return 0;
}
上一篇:34. Find First and Last Position of Element in Sorted Array


下一篇:【leetcode】高频题目整理_链表篇( High Frequency Problems, Linked List )