B. Neko Performs Cat Furrier Transform

图片说明
图片说明

解法

目的就是为了让二进制全变成1，那么直接从最高位的0开始，假如最高位的0位置是h，那么就异或(1<<(h+1))-1,当然如果是偶数次操作，就+1
这样能够保证2次操作最少可以消除一个0，1e6不到20位，所以40次完全足够

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}

//--------------------------------------------

int x;
int ans[maxn],tail;
int total;
void solve(){
    int tim = 10;
    while(true){
        int w = -1,tag = 1;
        for(int i = 31;i>=0;i--){
            if((x>>i) & 1) tag = 0;
            else if(tag == 0){
                w = i;
                break;
            }
        }
        if(w == -1) break;
        total++;
        if(total&1) {
            ans[++tail] = w+1;
            x ^= (1<<(w+1))-1;
        }else{
            x += 1;
        }
    }
    cout<<total<<'\n';
    for(int i = 1;i<=tail;i++) cout<<ans[i]<<" ";
}
int main(){
    // debug_in;

    read(x);
    solve();

    return 0;
}