以為又要掉分了（結(jié)果沒(méi)掉說(shuō)明太菜了），寫完ABC還有45分鐘，推式子一直沒(méi)啥結(jié)果，最后10分鐘想到D題的一個(gè)性質(zhì)，可惜沒(méi)時(shí)間了~

D. Checkpoints

Heltion大佬題解
性質(zhì)：把形如$100\dots 0$的序列看成一個(gè)關(guān)卡，不難知道總的期望步數(shù)是每一個(gè)這樣關(guān)卡期望的疊加。（最后10分鐘才看出來(lái)~

然后就參考上述題解，如果上述關(guān)卡中有$n$個(gè)stage，那么通過(guò)此關(guān)卡的期望步數(shù)是$2^{(n+1)}?2$
連續(xù)通過(guò)$n$個(gè)stage的期望是$E_n$那么有期望遞推式：$$E_{n+1}=(E_n+1)+\frac{1}{2}\times E_{n+1}+\frac{1}{2}\times 0$$
已經(jīng)走了$E_n+1$步，有一半的幾率從頭再來(lái)即$\frac{1}{2}\times E_{n+1}$，還有一半的幾率成功不需要再走即$\frac{1}{2}\times 0$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; int main() {IO;int T=1;cin>>T;while(T--){ll k,res=0;cin>>k;if(k&1) {cout<<-1<<'\n';continue;}// 2^(n+1)-2vector<ll> v;while(k){ll n=1;while((1ll<<n+2)-2<=k) n++;v.push_back(n);res+=n;k-=(1ll<<n+1)-2;}cout<<res<<'\n';for(auto t:v){cout<<"1 ";for(int i=1;i<t;i++) cout<<"0 ";}cout<<'\n';}return 0; }

期望題還要多做做，要加油哦~

總結(jié)

以上是生活随笔為你收集整理的codeforces1453 D. Checkpoints的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。