2008年百度之星程序设计大赛初赛第二场题目
1.广告排名区间( 10分)
问题背景shifen广告消费预估系统可以估计出一段时间内一个特定的广告在检索结果中排在各个位置的几率。 比如系统对某广告的输出如下p1=0.03,p2=0.08,p3=0.04. . . . . . . . . . . . .
这说明该广告展现在第1位的概率是3%展现在第2位的概率是8%展现在第3位的概率是4%••…
问题是如何给出一个排名估计区间 i,j 使得广告出现在该区间中的概率大于或等于一个预设值p,同时这个区间所包含的元素尽可能的少。也可用数学语言来描述给定数p和数列p1,p2,…,pn求i和j(1<=i<=j<=n)在满足pi+pi+1+…+pj>=p的前提下让j-i最小。
一般来说 pi只需保留6位小数就足够了。这样若令ai=106pi ,a=106p,则a和所有的ai均为0,106之间的整数。这样就避免了对实数的处理。
输入格式
第一行包含一个整数n(1<=n<=100,000) 。
以下n行每行包含一个0,106 内的整数依次为al,a2,… an。这n个整数之和保证不超过106。
最后一行包含一个0,106 内的整数a。保证所有ai之和不小于a。
输出格式
输出仅一行包含一个整数 即j -i的最小值。
样例输入
7
5
8
4
7
10
5
2
18
样例输出
2
样例解释a2=8,a3=4,a4=7之和为19满足条件。而任何两个相邻数之和均小于 18。
2.LZW网页判重(20分)
问题背景
有一种简单的网页判重的方法通过求两个网页内容的最长公共子序列 (LCS)长度来判定两个网页的相似程度。如
网页A老师请用“果然”造句。
网页B学生先吃水果然后喝汽水. . . .
它们的最长公共子序列为“果然” 长度为2。注意这里的“子序列”并不要求连续。类似的下面两个网页
网页A老师请用“果然”造句。
网页B学生先吃水果然后喝汽水果然拉肚子……最长公共子序列还是“果然”长度为2。但不难看出 由于“果然”两个字在网页B中也曾连续出现第二组网页比第一组更加“相似”。为了区分开这两种情况的区分度我们改用一种称为L ZW的理论。为了严格的叙述相似度的计算方法我们首先定义“文本单元”。 假定网页用一个不包含空白字符空格、回车换行、水平制表符的字符串来表示。它只包含纯文本没有标签。在计算相似度之前你应该首先对该字符串进行处理划分成一个个“文本单元”。每个文本单位可以是一个中文字、 英文单词由一个或多个连续的半角英文字母和数字组成 正规表达式为[a-zA-Z0-9]+ 、或者一个标点符号。根据上述定义 同一个标点符号的全角和半角应该被作为不同的文本单元尽管他们看起来可能很相近每个单独全角英文和全角数字都应该被看成一个单独的文本单元而连续的半角英文字母和数字应被看成一个整体。总之全角的字符可以与中文字同等对待。这样 网页被看成文本单元序列。例如 网页“内容 12 3456??web2.00#”切分出的文本单元序列为为了显示方便用下划线分隔各文本单元 内_容_ _1
_2_345_6_?_?_web2_._00_#
而网页“why内容相似 1234567890,we b#00'的切分结果为why_内_容_相_似_?_?_1234567890_,_we b_#_00黑体部分给出了两个网页的一个公共子序列。注意“内容”、 “ ??”分别在两个网页中都是连续出现的文本单元。为了奖励这种情况 L ZW规定一段由连续k个文本单元组成的字符串权值为k2。在刚才的例子中 “内容”、 “ ?”的权值均为4。但“00”是一个数字串应当被看成一个单独的文本单元。所以权值仅为1 。
根据上述规则公共子序列“内容??00”的权值为22+22+1=9。在所有可能的子序列中这个权值是最大的。
给定两个网页求他们的L ZW相似度 即所有可能的公共子序列中的最大权值。
1 输入的网页内容以GBK编码参见FAQ
2 除了大小写英文字母和数字之外的其他半角字符均视为标点符号。输入格式包含两行分别是网页A和B对应的字符串不包含空白字符 。每行至少包含5个字节最多包含200个字节。
输出格式
输出仅一行包含一个整数为两个网页的 LZW相似度。
样例输入
内容 123456??web2.00#why内容相似??1234567890,we b#00
样例输出
9
样例解释
尽管两个网页里看上去都有“ 123456”但一方面第一个网页中混杂的全角和半角字符而另一方面 即使全部改成半角字符 由于数字串“ 123456”和
“1234567890”将分别看成一个单独的文本单元 因此无法部分匹配。
3.钉子与木板 30分
问题背景
墙上有n个钉子编号为1,2,…,n。其中钉子i的横坐标为i纵坐标初始为xi 。可以进行两种操作
O kv:竖直移动钉子k,坐标变为K v 。
1 stv若在高度为v处放一块横坐标范围是[s,t]的水平木板它将下落到什么高度换句话说求出钉子s,s+1,s+2,…,t的纵坐标中不超过v的最大值。 如果这些钉子的高度全部大于v,则木板将落到地上高度为0。注意在T操作时水平木板只是用来测试的“临时木板”将在测试后立即被拿走不会影响到后续测试工作。
输入格式
第一行包含两个整数n,m 即钉子的个数和操作的个数1<=n,m<=105。 以下n行一个不超过109的非负整数 即xi 。
输出格式
按照输入的顺序对于每个T操作输出一个整数 即该测试水平木板的最后高度。样例输入
54
1
3
5
7
9
1246
0310
1357
1355
样例输出
5
7
0
4.圆面覆盖40分
问题背景
在平面上有一个长为L,宽为W的长方形左下角坐标为0,0 右上角坐标为L,W 。给定一些圆第i个圆的圆心坐标为xi,yi 半径为Ri。
你的任务是求最小的正实数k使得把每个圆的半径变为原来的k倍后即第i个圆半径变为kRi 圆心位置不变 长方形将被这些圆完全覆盖。 换句话说,长方形内部或边界上的任意点均至少在一个圆的内部或边界上。
输入格式
输入第一行包含三个整数n,L,W 1<=*=50, 1<=L,Wv=1000 即圆的个数、长方形的长和宽。
以下n行每行三个不超过1000的正整数xi,yi和Ri。
输出格式
仅一行包含一个实数k保留小数点后三位。
样例输入
122
111
样例输出
1.414
整理一下CloudCone商家之前推送的闪购VPS云服务器产品,数量有限,活动推出可能很快机器就售罄了,有需要美国便宜VPS云服务器的朋友可以关注一下。CloudCone怎么样?CloudCone服务器好不好?CloudCone值不值得购买?CloudCone是一家成立于2017年的美国服务器提供商,国外实力大厂,自己开发的主机系统面板,CloudCone主要销售美国洛杉矶云服务器产品,优势特点是...
10gbiz发布了9月优惠方案,针对VPS、独立服务器、站群服务器、高防服务器等均提供了一系列优惠方面,其中香港/洛杉矶CN2 GIA线路VPS主机4折优惠继续,优惠后最低每月仅2.36美元起;日本/香港独立服务器提供特价款首月1.5折27.43美元起;站群/G口服务器首月半价,高防服务器永久8.5折等。这是一家成立于2020年的主机商,提供包括独立服务器租用和VPS主机等产品,数据中心包括美国洛...
PacificRack在本月发布了几款特价产品,其中最低款支持月付仅1.5美元,基于KVM架构,洛杉矶机房,PR-M系列。PacificRack简称PR,QN机房旗下站点,主要提供低价VPS主机产品,基于KVM架构,数据中心为自营洛杉矶机房,现在只有PR-M一个系列,分为了2个类别:常规(Elastic Compute Service)和多IP产品(Multi IP Server)。下面列出几款秒...