题目链接
翻译
每个阶段都有 (frac{1}{2}) 的几率失败，失败了会回到上一个存档点。
想让玩家的期望尝试次数为 (k)，问你能否设计出一个不超过 (2000) 级台阶的策略，满足这个要求。
题解
如果只有一个 (1) 的话，那么期望尝试次数为 (2)。假设后面出现了一个 (0)，即 10，那么到达第 (2) 层且通过了第二层(能够到达第三层了)的期望次数
是多少呢? 第一层通过了，次数是 (2)，然后到达第二层，进行一次尝试。也即 (2+1=3)。但是第二层也只有 (frac{1}{2}) 的几率成功。
所以也应该要乘 (2)，即到达第二层且通过第二层的期望次数为 (2*(2+1)=6)。(失败了就要重新从第一层再上)
不难看出，假设 100000... 的长度为 (i)，设 (x_i) 表示 (i) 层都通过的期望次数。则 (x_{i+1}=2*(x_i+1)) 也即 (x_i = 2^{i+1}-2)
并且，只要再出现一个 (1) 了，就要重新算期望，即 (1) 把不同的段分隔开了。
然后说下构造策略，首先，(x_i) 总是一个偶数，所以 (k) 为奇数直接 (-1)
然后，对于所给的偶数期望 (k)，我们可以这么玩。会发现 11000.. (注意这里开头有两个连续 (1),长度设为 (i+1)) 对应的需要重新试的次数为 (2^{i+1})，因为加上了第一个 (1) 的两次。
只不过这里 (i>=1)，所以，对于 (kge4) 的时候，我们只要用 (11000..) 这样对应的 (2^{(i+1)}) 去减 (k) 就好。
因为二进制分解的缘故，我们总能让 (k) 对应的二进制中大于等于 (2^2) 对应的位都变成 (0)，因此一直减的结果就是 (k) 最后等于 (2) 或者 (0)。
等于 (2) 的时候再补一个 (1) 就好啦。
构造出来的层数是 (1+2+3...log_2K) 这个数量，不会超过 (2000)。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
vector<int> ans;
int main(){
// freopen("C://1.cppSourceProgram//rush.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while (T--){
LL k;
cin >> k;
//[1] 特殊判断
if (k % 2 == 1){
cout << -1 << endl;
continue;
}
//[2] 用1(期望值为2, 10000...0(1000..0长度为 i 期望值为2^(i+1)-2
//合在一起就是 2^(i+1), 但是这里 i >= 1
//所以如果k >= 4, 那么就用11000的 batch 减
ans.clear();
while (k >= 4){
ans.push_back(1);
ans.push_back(1);
LL cur = 4;
int i = 1;
while (cur*2 <= k){
cur*=2;
i++;
}
for (int j = 1;j <= i-1; j++){
ans.push_back(0);
}
k -= cur;
}
//k=2或k=0
if (k == 2){
ans.push_back(1);
}
cout << (int)ans.size() << endl;
int len = ans.size();
for (int i = 0;i < len; i++){
cout << ans[i];
if (i == len-1){
cout << endl;
}else{
cout << " ";
}
}
}
return 0;
}