# CF688div2 1453D. Checkpoints(期望递推构造)

2020-12-07 10:48:10

1 2 \frac{1}{2} 21的概率成功通过第 i i i个关卡

1 2 \frac{1}{2} 21的概率一步穿过, 1 2 \frac{1}{2} 21的概率一步失败,还需要期望 x x x通过

f [ i ] = f [ i − 1 ] + 1 + 1 2 ∗ [ f [ i − 1 ] + ( f [ i ] − f [ i − 1 ] ) ] f[i]=f[i-1]+1+\frac{1}{2}*[f[i-1]+(f[i]-f[i-1])] f[i]=f[i1]+1+21[f[i1]+(f[i]f[i1])]

1 2 \frac{1}{2} 21的概率突破了第 i i i个关卡,不需要加额外的花费

1 2 \frac{1}{2} 21的概率没有突破回到一开始的位置 1 1 1

f [ i ] = 2 ∗ f [ i − 1 ] + 2 f[i]=2*f[i-1]+2 f[i]=2f[i1]+2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+10;
int f[maxn],k;
vector<int>ans;
signed main()
{

f[1] = 2;
for(int i=2;i<=60;i++)	f[i] = 2*f[i-1]+2;
int t; cin >> t;
while( t-- )
{

ans.clear(); int flag = 1;
cin >> k;
while( k )
{

for(int i=60;i>=1;i--)
if( f[i]<=k )
{

k-=f[i];	ans.push_back(1);
for(int j=2;j<=i;j++)	ans.push_back(0);
break;
}
if( k%2==1 ){

flag=0; break; }
}
if( ans.size()>2000 )	flag=0;
if( flag == 0 )	cout << -1;
else
{

cout << ans.size() << endl;
for(int i=0;i<ans.size();i++)
cout << ans[i] << " ";
}
cout << endl;
}
}


https://my.oschina.net/u/4296470/blog/4777716