E. Increasing Subsequences -思维构造

题面

分析

如果构造一个递增序列，如 $1,2,3,4,...$ ，可以发现是存在一定规律的，一一列举。

• 1 —— 有两个上升子序列（1和空序列)。
• 1,2 —— 有四个上升子序列（空序列，1，2，1 2）。
• 1,2,3 —— 有八个上升子序列…
  也就是一个一直递增的长度为 $n$ 的数组可以构成 $2^n$ 个上升子序列，那么对于 $X$ 也就可以先构造出一个最大的递增序列，此时拥有 $2^i$ 个上升子序列，还缺少 $X?2^i$ 个上升子序列，设剩余需要的上升子序列的个数为 $x$ ，那么可以对 $x$ 进行二进制拆分，他的二进制的每一位加在一起可以构成 $x$ ，对于每一位为 $1$ 的二进制位，那么也就可以在构造的数组后面加上相应的数，假如这意味是第 $j$ 位，表示为 $2^j$ ，那么数组末尾就可以添加一个 $j$ ，当将 $x$ 所有二进制位都操作完后，也就得到了满足条件的数组。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    ll x;
    cin >> x;
    vector<int> ans;
    int cnt = 1;
    ll res = 2;
    while(res <= x) {
        ans.push_back(cnt ++);
        res *= 2;
    }
    ///cout << res << endl;
    res /= 2;
    ll d = x - res;
    for(int i = 60; i >= 0; i --) {
        if((d >> i) & 1) ans.push_back(i + 1);
    }
    cout << ans.size() << "\n";
    for(auto j: ans) cout << j << ' ';
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T --) {
        solve();
    }
}