概述
D题链接
题意：有n个点，每个点可以放1也可以不放1，某个人从1开始挑战，包括1，n都要挑战，挑战成功的概率和失败概率一样都是1/2，如果失败了就会回到离i这个点最近的1的点，问最后通关(挑战成功n）的期望步数。
思路:概率论纯属没有学好，看了题解期望原来是有可加性的，对于任意
100000..
1 0 0 0 0 0..
100000..这样的序列，可以构成一个关卡，最后期望就是E的总和。然后我们计算子关卡的期望步数，
E
[
i
]
=
E
[
i
−
1
]
+
1
+
1
/
2
∗
E
[
i
]
+
1
/
2
∗
0
E[i]=E[i-1]+1+1/2*E[i]+1/2*0
E[i]=E[i−1]+1+1/2∗E[i]+1/2∗0
E
[
i
]
E[i]
E[i]代表挑战完第i个关卡需要的期望，那么就是个简单的期望dp罢了，
E
[
i
−
1
]
E[i-1]
E[i−1]走完以后，下一步有两种可以，一种挑战成功到达
E
[
i
−
1
]
E[i-1]
E[i−1]，另一种回到初始点，还需要走
E
[
i
]
E[i]
E[i]步,然后移项
E
[
i
]
=
2
∗
E
[
i
−
1
]
+
2
E[i]=2*E[i-1]+2
E[i]=2∗E[i−1]+2 那么就是通项求和就是
2
n
∗
2
−
2
2^n * 2-2
2n∗2−2那么最后输出一种方案，众所周知，和肯定是偶数，奇数直接无解，偶数从最大的
2
n
∗
2
−
2
2^n * 2-2
2n∗2−2开始构造就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---n");
const int N=210,M=10010;
int main()
{
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
ll k;
cin>>k;
if(k&1)
{
cout<<"-1"<<endl;
continue;
}
vector<ll>res;
int tmp=0;
while(k)
{
int n=1;
while(true)
{
if(( (1ll<<(n+1))-2)>k)
break;
n++;
}
// cout<<k<<" "<<n<<endl;
n--;
res.push_back(n);
tmp+=n;
//cout<<k<<endl;
k-=(1ll<<(n+1))-2;
}
cout<<tmp<<endl;
for(auto x:res)
{
cout<<1<<" ";
x--;
while(x--)
cout<<0<<" ";
}
cout<<endl;
}
return 0;
}
最后
以上就是还单身水蜜桃为你收集整理的D. Checkpoints的全部内容，希望文章能够帮你解决D. Checkpoints所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复