【ICPC】2022 昆明站 D题 题解

定义一种序列的合法划分:从左往右依次选择，可以把该数归到 S A SA SA中，或者 S B SB SB中，假如随意划分，有 2 n 2^n 2n中划分方法，但需要满足:

• S A SA SA 是不严格递增序列
• S B SB SB 是不严格递减序列

一个序列有很多种合法的划分，现在给定 k k k，请构造一种序列，它的合法划分数刚好是 k k k

题目链接

我们需要找到一种方便计算其结果的构造
考虑一个不严格递增序列 1 , 1 , 1 , 2 , 2 , 2 , 2 , 2 , 3 , 3... x , x , x 1,1,1,2,2,2,2,2,3,3...x,x,x 1,1,1,2,2,2,2,2,3,3...x,x,x。

上述序列的合法构造就是，任选一个数，任选一些和它相同的数放到 S B SB SB中，剩下的放 S A SA SA中。

那么对于每一个中数 i i i, 合法情况就是 i ∗ c n t [ i ] i * cnt[i] i∗cnt[i], c n t [ i ] cnt[i] cnt[i]是 i i i的数。但是需要注意的是，所有情况中，有一种是所有数都不放入 S B SB SB中，那么这些情况会重复。除了第一次计算不用减去，剩余的 i i i的情况都需要减去 1 1 1。

所有总的方案数就是 1 + ∑ 2 c n t [ i ] − 1 , i ∈ [ 1 , n ] 1 + sum 2^{cnt[i]}-1,i in [1,n] 1+∑2cnt[i]−1,i∈[1,n]
而这种构造方式，是可以构造出所有的自然数的。

我们直接从最高位枚举 c n t [ i ] cnt[i] cnt[i],如果 k > ( 1 < < c n t [ i ) ] k > (1 << cnt[i)] k>(1< （剩下 1 1 1时就可以结束了）

#include 
#include 
#include 
using namespace std;

int k, t = 1;
vector ans;

int main()
{
    scanf("%d", &k);
    if(k == 0)
        printf("12n1 1 4 5 1 4 1 1 4 5 1 4n");
    else if(k == 1)
        printf("6n1 1 4 5 1 4n");
    else {
        for(int i = 29; i >= 0; --i) {
            while(k > (1 << i) - 1) {
                k -= (1 << i) - 1;
                for(int j = 1; j <= i; ++j)
                    ans.push_back(t);
                ++t;
            }
            if(k == 1)
                break;
        }
        printf("%dn", ans.size());
        for(int i = 0; i < ans.size(); ++i)
            printf("%d ", ans[i]);
    }
    return 0;
}