cf688div2 D. Checkpoints

题目链接
题意：
一个闯关游戏有n关（k<=2000)，闯关者通过每一关的概率为1/2，如果没通关会回到离他最近的一个复活点，初始和最后一个关卡一定有复活点，中间关卡可能有也可能没有复活点。问你怎样设置关卡和复活点，使得闯关者通过全部关卡的数学期望为k(k<10e18)。
思路：
首先可以分析小数据。
这样一个游戏[1,0,0,0]，通过每一关的期望次数[16,8,4,2];
假如期望为30，输出1 0 0 1 1;
[1,0,0,]->[8,4,2];
假如期望为16，输出1 0 0 1；
如果期望k为奇数，这是不可能的，输出-1。
可以先初始化一个数组A，存2的等比数列，2^60大约是10e19;
对于每一个k,从后往前比较与A数组的大小，往前迭代就行了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e3+5;
const int mod=1e9+7;
ll a[N],b[N];
int main(){
int t;cin>>t;
a[0]=1;
for(int i=1;i<=61;i++){
a[i]=a[i-1]*2;
}
//cout<<a[60]<<endl;
while(t--){
ll k;cin>>k;
if(k%2) cout<<"-1"<<endl;
else{
ll res=k,cnt=0;
for(int i=61;i>=1;i--){
if(res>=a[i]){
res-=a[i];
b[cnt]=1;
for(int j=cnt+1;j<cnt+i;j++)
b[j]=0;
b[cnt+i-1]=1;
cnt+=i;
}
if(res==0) break;
}
cout<<cnt<<endl;
b[cnt-1]=1;
for(int i=0;i<cnt;i++){
cout<<b[i]<<' ';
}
cout<<endl;
}
}
return 0;
}

最后

以上就是细腻月光为你收集整理的cf688div2 D. Checkpoints的全部内容，希望文章能够帮你解决cf688div2 D. Checkpoints所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。