題目鏈接：點擊查看

題目大意：需要設計一個游戲關卡，由 01 字符串組成，1 表示存檔點，0 表示普通關卡，規定每一步可以從第 i 個關卡前進到第 i + 1 個關卡，不過有 1/2 的概率會成功，剩下 1/2 的概率會失敗，失敗的話會返回最近的存檔點重新開始，現在問如何設計關卡，可以使得到達終點的期望為 k

題目分析：首先不難看出，每經過一個存檔點后，前面的關卡都已經對后續的期望沒有影響了，換句話說相鄰的兩個存檔點組成的一段關卡是互相獨立的

所以我們只需要分析諸如 11 , 101 , 1001 , ... 也就是相鄰兩個存檔點之間 0 的個數與期望的關系即可

首先不難看出，如果是 11 的話，那么第一步如果失敗，那么第二步按理來說會成功，所以期望是 2

101 的話，自己手玩一下不難看出期望是 6，根據手玩的過程也不難看出期望的遞推式是 f[ i ] = ( f[ i - 1 ] + 1 ) * 2

打個表去 OIES 找一下規律，可以發現公式就是?

結合上文中提到的，相鄰兩個存檔點組成的一段關卡是相互獨立的，就可以對題目中給出的 k 進行二進制拆分了，每次用 2^1 和 2^x 去構造，操作復雜度大概是 n * ( n - 1 ) / 2 ，n 是 60，最后結果遠小于 2000

又因為此處最小只能構造出 2^1 = 2，無法構造出 2^0 = 1，所以奇數一律無解

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){LL n;scanf("%lld",&n);if(n&1){puts("-1");continue;}vector<int>ans;for(int i=1;i<=60;i++)if((n>>i)&1){ans.push_back(1);//2if(i>1)//2^n-2{for(int j=1;j<i-1;j++)ans.push_back(0);ans.push_back(1);}}printf("%d\n",ans.size());for(auto it:ans)printf("%d ",it);puts("");}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1453D Checkpoints(概率+构造)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。