我是靠谱客的博主 时尚项链,最近开发中收集的这篇文章主要介绍CF688div2 1453D. Checkpoints(期望递推构造),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

传送门

题意

构造一串长 n n n的零一序列 ( n < = 2000 ) (n<=2000) (n<=2000)

1 2 frac{1}{2} 21的概率成功通过第 i i i个关卡

如果失败,立刻返回小于等于 i i i的最小的 1 1 1位置


观察发现如果单独一个 1 1 1,穿过去的期望步数是 2 2 2

如果要算也很简单,设穿过一个单独的 1 1 1的期望是 x x x

1 2 frac{1}{2} 21的概率一步穿过, 1 2 frac{1}{2} 21的概率一步失败,还需要期望 x x x通过

那么 x = 1 2 ∗ 1 + 1 2 ∗ ( x + 1 ) x=frac{1}{2}*1+frac{1}{2}*(x+1) x=211+21(x+1)

解得 x = 2 x=2 x=2

那么最后构造的序列就可以分解为若干个形如1 0 0 0的形式(当然 1 1 1后面也可以没有 0 0 0)

定义 f [ i ] f[i] f[i]为开头一个 1 1 1,后面跟 i − 1 i-1 i1 0 0 0的期望通过步数

那么由上面的推导得 f [ 1 ] = 2 f[1]=2 f[1]=2

可以得到以下递推式

f [ i ] = f [ i − 1 ] + 1 + 1 2 ∗ [ f [ i − 1 ] + ( f [ i ] − f [ i − 1 ] ) ] f[i]=f[i-1]+1+frac{1}{2}*[f[i-1]+(f[i]-f[i-1])] f[i]=f[i1]+1+21[f[i1]+(f[i]f[i1])]

我解释下这个方程,想突破第 i i i个关卡,前提是突破前 i − 1 i-1 i1个关卡,期望是 f [ i − 1 ] f[i-1] f[i1]

现在用一次机会尝试突破第 i i i个关卡,期望是 1 1 1

1 2 frac{1}{2} 21的概率突破了第 i i i个关卡,不需要加额外的花费

1 2 frac{1}{2} 21的概率没有突破回到一开始的位置 1 1 1

那么首先需要回到第 i − 1 i-1 i1个位置需要 f [ i − 1 ] f[i-1] f[i1],突破第 i i i个关卡需要期望 f [ i ] − f [ i − 1 ] f[i]-f[i-1] f[i]f[i1]

所以得到上面的式子,把右边的 f [ i ] f[i] f[i]移项到左边,解得 f [ i ] f[i] f[i]

f [ i ] = 2 ∗ f [ i − 1 ] + 2 f[i]=2*f[i-1]+2 f[i]=2f[i1]+2

所以发现每一个小单元都是偶数期望,所以当 k k k为奇数无解

否则一定是从大到小构造 1   0   0   0   0... 1 0 0 0 0... 1 0 0 0 0...

因为最后的组成单元是 f [ 1 ] = 2 f[1]=2 f[1]=2,所以只要是偶数的 k k k,都可以构造出来

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+10;
int f[maxn],k;
vector<int>ans;
signed main()
{
	f[1] = 2;
	for(int i=2;i<=60;i++)	f[i] = 2*f[i-1]+2;
	int t; cin >> t;
	while( t-- )
	{
		ans.clear(); int flag = 1;
		cin >> k;
		while( k )
		{
			for(int i=60;i>=1;i--)
				if( f[i]<=k )
				{
					k-=f[i];	ans.push_back(1);
					for(int j=2;j<=i;j++)	ans.push_back(0);
					break;
				}
			if( k%2==1 ){ flag=0; break; }
		}
		if( ans.size()>2000 )	flag=0;
		if( flag == 0 )	cout << -1;
		else
		{
			cout << ans.size() << endl;
			for(int i=0;i<ans.size();i++)
				cout << ans[i] << " ";
		}
		cout << endl;
	}
}

最后

以上就是时尚项链为你收集整理的CF688div2 1453D. Checkpoints(期望递推构造)的全部内容,希望文章能够帮你解决CF688div2 1453D. Checkpoints(期望递推构造)所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(38)

评论列表共有 0 条评论

立即
投稿
返回
顶部