[CF 335E]Counting Skyscrapers题解翻译

题目翻译:


题解翻译:


这道题中的摩天大楼描述了被称作跳跃表(Skip List)的数据结构。跳跃表在某种意义上和AVL、红黑树相似,因为它支持O(logN)的插入,操作和查找(包括上下界查询),同时支持常数时间的在排序顺序中前后移动。跳跃表和任何树结构都不同,因为它有实用的,不需要线程锁的(所谓‘无锁’),线程安全的实现方式。无锁跳跃表被用作MemSQL中主要的存储数据结构,并且Bob使用的,穿过摩天大楼的算法是一种O(logN)的方法,它能让人们估算跳跃表的大小。因此,如果Bob最终得到的数值是n,则跳跃表真实大小的期望值就是n(因此如果输入文件的第一行是Bob,你就只需要读入第二行的数并输出它)。形式化的证明十分简单,我们把它留给读者。奇怪的是,逆命题并不成立。如果跳跃表的大小是n,那么估算算法的期望返回值比n要大。对于一个远大于2^h的n,估算值收敛于n-1+2^h,但这个问题同时还包含了n较小的数据。


让我们每次将解的层数增加1.当H=0时,期望的估算值自然是N。现在对于加上的每一层,我们都可以加上这一层溜索的期望花费,并同时减去它们下方溜索的期望花费。最终我们将得到总共的期望花费。


对于高度为H的某一层,让我们考虑左侧和右侧的一些塔,并计算它们之间存在一条溜索的可能性。令L是两座塔之间的距离。一条可能存在的,长度为L,高度为H的溜索的确存在,如果它两端的塔都足够地高(每个都有1/(2^H)的概率),并且中间的L-1座塔都较低(每个都有1-(1/(2^H))的概率)。因此这样一条溜索存在的概率是(1/(2^2H))*(1-(1/(2^H))^(L-1))。


现在,假设这样一条溜索存在,它下方溜索的期望数量是多少?它就是高度H-1的塔的数量加1。L-1座塔中的每一个都有1/(2^H-1)的概率高度为H-1(注意到它的高度至多是H-1)——运用条件概率公式P(A|B)=P(A∩B)/P(B)来计算这个。因此一个长度为L,高度为H的溜索下方溜索的期望数量是1+(L-1)/(2^H-1)。


对于每个长度L,在每一层都有N-L条长度为L的可能溜索。对于所有可能的溜索,我们把它出现的概率乘以它的花费,求和得到总的期望值。


因而最终答案就是:



事实上内层循环可以用矩阵乘法计算,运行时间为O(HlogN)。——虽然数据范围足够小,用矩阵乘法是高射炮打蚊子——O(H*N)就行了。


译者注1:

以下是对Bob情形的证明,即题解中“留给读者”的部分:

假设Bob即将走一条高度为h的溜索(此时他所在的大楼高度>=h),这条溜索的长度期望是多少?

此时Bob站在这条溜索的左端点,而未知的部分只有溜索越过的大楼和溜索的右端点。换句话说,这条溜索期望增加多少栋大楼?

容易发现,某栋大楼高度>=h的概率是1/(2^h)。即,在2^h栋楼中才期望出现一个高度>=h的楼。因而,这条高度为h的溜索的期望长度是2^h。

也就是说,一条花费2^h的溜索的期望长度是2^h。由于Bob的计数器一开始是1,所以很容易得出,大楼数的期望就是计数器最终的值n。


译者注2:

以下是对“高度为H-1的概率为1/(2^H-1)”的证明:

显然我们已经知道这栋楼的高度

根据条件概率公式,P(高度为H-1 | 高度1-(1/(2^H))) = 1/(2^H-1)。


译者注3:

为什么只需要减去高度为H-1的溜索呢?因为对于这条高度为H的溜索,其两端大楼的高度都>=H,因而在上一个阶段中高度都>=H-1,因此在上一个阶段,这两栋楼之间只存在高度为H-1的溜索。


代码:

#include
#include
#include
#include
#include
using namespace std;
char name[20];
int N,H;
int main(){
	scanf("%s",name);
	scanf("%d%d",&N,&H);
	if(name[0]=='B'){
		printf("%d\n",N);
		return 0;
	}
	double po=1,ans=0;
	for(int i=1;i<=H;i++){
		po*=2;
		double t=1;
		for(int j=1;j<=N;j++){
			ans+=(N-j)/po/2*t*(po-j)/(po-1);
			t*=1-1/po;
		}
	}
	printf("%.10lf\n",ans+N);
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注