ICPC2022KunMingD

题目大意

定义一种序列的合法划分:从左往右依次选择，可以把该数归到\(SA\)中，或者\(SB\)中，假如随意划分，有\(2^n\)中划分方法，但需要满足: * \(SA\) 是不严格递增序列 * \(SB\) 是不严格递减序列

一个序列有很多种合法的划分，现在给定\(k\)，请构造一种序列，它的合法划分数刚好是\(k\) 题目链接

思路

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

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

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

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

我们直接从最高位枚举\(cnt[i]\),如果\(k > (1 << cnt[i)]\)，那就减去它，同时\(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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/24/ICPC2022KunMingD/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！