CF1922E Increasing Subsequences 题解

解题思路

因为可以有空集，那么我们首先构造第一段最长的连续上升的序列，那么这段序列中共有 \(2^{\mid s \mid}\) 个上升子序列。接下来我们考虑补全剩余的，我们不妨将剩余的部分全部设为连续不增序列，那么设当前位置在第一段中有 \(k\) 个小于它的，那么添加这个数后可以增加 \(2^{k-1}\) 个子序列，那么直接循环添加，如果增加后超过 \(x\) 了，那么 \(k\gets k-1\) 即可。在循环结束后，如果 \(x\) 任然有剩，那么输出 -1。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define N 205
ll x;int a[N];
int _2[N];
inline void work(){
    scanf("%lld",&x);
    int ce=0;ll y=x;
    while(y){
        _2[++ce]=y&1;
        y>>=1;
    }
    for(register int i=1;i<ce;++i)
        a[i]=i;int n=ce-1;
    x-=1ll*(1ll<<(ce-1));
    int now=ce-1;
    while(x>0){
        while(x<(1ll<<(now-1))&&now>0)
            --now;
        if(now==0) break;
        while(x>=(1ll<<(now-1))&&now>0)
            a[++n]=now,x-=(1ll<<(now-1));
    }if(x){
        puts("-1");
        return;
    }printf("%d\n",n);
    for(register int i=1;i<=n;++i)
        printf("%d ",a[i]);
    putchar('\n');
}
signed main(){
    int T;scanf("%d",&T);
    while(T--) work();
}