免费注册域名网站,定制制作网站公司,做ui必要的网站,wordpress foter以为又要掉分了#xff08;结果没掉说明太菜了#xff09;#xff0c;写完ABC还有45分钟#xff0c;推式子一直没啥结果#xff0c;最后10分钟想到D题的一个性质#xff0c;可惜没时间了~
D. Checkpoints
Heltion大佬题解 性质#xff1a;把形如100…01 \ 0 \ 0 \dots…以为又要掉分了结果没掉说明太菜了写完ABC还有45分钟推式子一直没啥结果最后10分钟想到D题的一个性质可惜没时间了~
D. Checkpoints
Heltion大佬题解 性质把形如100…01 \ 0 \ 0 \dots01 0 0…0的序列看成一个关卡不难知道总的期望步数是每一个这样关卡期望的叠加。最后10分钟才看出来~
然后就参考上述题解如果上述关卡中有nnn个stage那么通过此关卡的期望步数是2(n1)−22^{(n1)}-22(n1)−2 连续通过nnn个stage的期望是EnE_nEn那么有期望递推式En1(En1)12×En112×0E_{n1}(E_{n}1)\frac{1}{2}×E_{n1}\frac{1}{2}×0En1(En1)21×En121×0 已经走了En1E_{n}1En1步有一半的几率从头再来即12×En1\frac{1}{2}×E_{n1}21×En1还有一半的几率成功不需要再走即12×0\frac{1}{2}×021×0
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
int main()
{IO;int T1;cinT;while(T--){ll k,res0;cink;if(k1) {cout-1\n;continue;}// 2^(n1)-2vectorll v;while(k){ll n1;while((1lln2)-2k) n;v.push_back(n);resn;k-(1lln1)-2;}coutres\n;for(auto t:v){cout1 ;for(int i1;it;i) cout0 ;}cout\n;}return 0;
}期望题还要多做做要加油哦~