D.CheckPoint
构造一个0/1序列 ,1表示当前关卡有存档点 0表示没有存档点
每一关通过的概率为1/2 ,问怎么构造才能使得通过所有关卡的期望步数 = k
到达当前关卡 若通过挑战 则步数++,通向下一关;
若不通过 则步数++, 回到目前为止最近一个有存档点的关卡
(回到存档点的关卡也要重新挑战)
若不能构造则输出-1
所有情况下第一关 必然有存档点
题目样例给出了几个情况
当k=8 时 关卡设计为 1 1 1 1
当k=4 时 关卡设计为 1 1
由于通过本关之后到达下一关激活了复活点 所以失败后仍在本关复活
相当于它与前面的关卡设计已经无关
所以通过第i关的期望次数=2 通过所有关的期望是2n
当关卡设计中存在有不含检查点的关卡时
不能通过就会复活在目前为止最近一个有存档点的关卡
状态如上图所示
设$f_x$ 表示从第x关出发 到达下一个检查点所需要的期望步数 (终点也视为检查点)
那么 对于第x 关 它有 1/2 的概率 通关到达下一关 则需要的步数为(1+$f_{x+1}$)
也有1/2的概率失败 回到 上一个检查点 y 则需要的步数为 (1+ $f_y$)
若第x+1关存在检查点 那么 它有 1/2 的概率 通关到达检查点 视为 一个临时的终点 需要1步
也有1/2的概率失败 回到 上一个检查点 y 则需要的步数为 (1+ $f_y$)
若到达一个新的检查点 由于之后的关卡失败也是从这一个检查点重新开始
所以后半段的期望步数与前半段期望步数不相干 通关的期望步数 是所有 (1 0 0 0 …) 段独立 期望的和
对于长度为m形如:1 0 0 0 0 ….. 的连续关卡
可以视为 连续投掷m个硬币 所有正面朝上所需要的期望次数 (若有一枚为反面 则全部重来)
这个问题模型推导 可以参考此处
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define Turnoff std::ios::sync_with_stdio(false)
const int Max=2e5+5; const int Mod=1e9+7; const ll inf=0x3f3f3f3f3f3f; #define P pair<ll,ll>
#define __DEBUG__ #ifdef __DEBUG__ #define DeBug(format, ...) \ { \ fprintf(stdout, "[%s:%d]" format "", \ __FUNCTION__ , __LINE__, ##__VA_ARGS__); \ } #else #define DeBug(format,...) #endif
ll qpow(ll x,ll y){ ll ans=1; while(y){ if(y&1)ans*=x; x*=x;y>>=1; } return ans; } int arr[Max]; int main(void){ Turnoff; int t;cin>>t; while(t--){ ll n;cin>>n; if(n&1){ cout<<-1<<endl; continue; } int now=0; while(n){ ll L=-1,R=61; while(R-L>1){ ll mid=(L+R)>>1; if(qpow(2,mid+1)-2<=n)L=mid; else R=mid; } while(qpow(2,L+2)-2<=n)L++; arr[now]=1; for(int i=1;i<L;i++){ arr[now+i]=0; } now+=L; n-=qpow(2,L+1)-2; } cout<<now<<endl; for(int i=0;i<now;i++)cout<<arr[i]<<" "; cout<<endl; } }
|