Codeforces Round #688 (Div. 2) D. Checkpoints 【期望 + 构造】

直接贴网上的题解把。

这样构造期望是指数型增长的，所以很大的数很快就构造好了。然后由于自己太弱，第一次看到期望可以通过移项来算，简单的变通都不会，服了啊
E[i] = E[i-1] + 1 + 1/2 * E[i] + 1/2 * 0
E[i-1] + 1:表示从E[i-1]转移到E[i]基础步数为1
+1/2 * E[i]：表示有1/2失败概率他要重走一遍到自身，所以加上走到i的步数期望的1/2
+1/2 * 0 ：表示当前有1/2成功概率，这中情况不需要再走额外步数

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#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 = 2e3+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 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...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------
int T;
ll k;
vector<char> ve;
void solve(){
    ve.clear();
    if(k%2==1) puts("-1");
    else{
        int total = 0;
        while(k>0){
            int cnt = 1;
            ll cur = 2;
            while(cur * 2 + 2 <=k){
                cur = cur * 2 + 2;
                cnt++;
            }
            total += cnt;
            k -= cur;
            for(int i = 1;i<=cnt;i++){
                if(i == 1) ve.pb('1');
                else ve.pb('0');
            }
        }
        printf("%d\n",total);
        int sp = 1;
        for(auto c:ve){
            if(sp) sp = 0;else putchar(' ');
            putchar(c);
        }
        puts("");
    }
}
int main() {
//    debug_in;
//    debug_out;

    read(T);
    while(T--){
        read(k);
        solve();
    }
    return 0;
}