题目地址

https://codeforces.com/contest/1453/problem/D

题目大意

游戏有若干个关卡，有些关卡前面有存档点，有些关卡没有。

通过每个关卡的概率都是$\frac{1}{2}$，如果失败后从上一次存档的存档点处开始。

输入一个$k$。

输出一个序列，0代表关卡开头没有存档点，1则有。第一个关卡前面肯定是有存档点的。

求一种安排使得打通所有关卡的时间期望为$k$。

解法

以前从来没写过期望相关的题，这次直接懵逼。

我们设当前站在关卡$x$，通过$x$这一关需要的时间期望为$f_x$。

先讨论只有1的情况：

对$[1,1]$这个序列:可以列出

$f_1=1\cdot\frac{1}{2}+\frac{1}{2}\cdot(f_1+1)$

$f_2=1\cdot\frac{1}{2}+\frac{1}{2}\cdot(f_2+1)$

不难理解，前半部分是一次通过，后半部分是这次没通过，那么下次的尝试的期望就是$f_1+1$，$+1$是因为这次失败了，下次的时候就要多花一个时间。

所以如果对于一段长度为n全是1的序列，通关的期望就是$2\cdot n$

接下来讨论有0的情况：

对$[1,0,0]$这个序列:可以列出f_1

$f_1=1\cdot\frac{1}{2}+\frac{1}{2}\cdot(f_1+1)$

$f_2=1\cdot\frac{1}{2}+\frac{1}{2}\cdot(f_2+f_1+1)$，因为2没有存档点，所以要重新打第一关，加上$f_1$

化简出$f_2=f_1+2=4$

$f_3=1\cdot\frac{1}{2}+\frac{1}{2}\cdot(f_1+f_2+f_3+1)$

化简出$f_3=f_1+f_2+2=2\cdot f_1+4=8$

对于一段连续的0，第$i$个0的时间期望就是$2^i$。

—————————–分割线——————————-

如果全放1的话，长度只能放到2000，但是k可以到1e18这么大，所以不行

我们就尽量放0，然后这段0太大了就放个1重新从2开始。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define INF 0x3f3f3f3f
int a[2077];
ll f[2020];
ll k;
void solve(){
    cin>>k;
    if(k%2){cout<<-1<<endl;return;}
    ll now = 0;
    a[1] = 1;
    f[1] = 2;
    now+=2;//a1
    int i;
    for(i=2;now<k;i++){
        if(now+f[i-1]*2<=k){
            a[i] = 0;
            f[i] = f[i-1]*2;
        }
        else{
            a[i] = 1;
            f[i] = 2;
        }
        now+=f[i];
    }
    i--;
    cout<<i<<endl;
    rep(j,1,i){
        cout<<a[j]<<' ';
    }
    cout<<endl;
}

int main(){
    int z;
    cin>>z;
    while(z--) solve();
}