【ICPC】2022 昆明站 D题 题解

题目大意

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

• $S_A$ 是不严格递增序列
• $S_B$ 是不严格递减序列

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

题目链接

思路

我们需要找到一种方便计算其结果的构造

考虑一个不严格递增序列 $1,1,1,2,2,2,2,2,3,3\ldots x,x,x$。

上述序列的合法构造就是，任选一个数，任选一些和它相同的数放到 $S_B$ 中，剩下的放 $S_A$ 中。

那么对于每一种数 $i$，合法情况就是 $2^{cnt[i]}$，其中 $cnt[i]$ 是数 $i$ 的个数。但是需要注意的是，所有情况中，有一种是所有数都不放入 $S_B$ 中，那么这些情况会重复。除了第一次计算不用减去，剩余的 $i$ 的情况都需要减去 $1$。

所有总的方案数就是

$$1 + \sum_{i \in [1,n]} (2^{cnt[i]} - 1)$$

而这种构造方式，是可以构造出所有的自然数的。

我们直接从最高位枚举 $cnt[i]$，如果 $k > (1 \ll cnt[i]) - 1$，那就减去它，同时 $i$++。（剩下 $1$ 时就可以结束了）

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int k, t = 1;
vector<int> ans;

int main()
{
    scanf("%d", &k);
    if(k == 0)
        printf("12\n1 1 4 5 1 4 1 1 4 5 1 4\n");
    else if(k == 1)
        printf("6\n1 1 4 5 1 4\n");
    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("%d\n", ans.size());
        for(int i = 0; i < ans.size(); ++i)
            printf("%d ", ans[i]);
    }
    return 0;
}