2010年百度之星程序設(shè)計(jì)方案大賽初賽

1、2008年百度之星程序設(shè)計(jì)大賽初賽第二場(chǎng)題目1. 廣告排名區(qū)間( 10 分)問題背景shifen 廣告消費(fèi)預(yù)估系統(tǒng)可以估計(jì)出一段時(shí)間內(nèi)一個(gè)特定的廣告在檢索結(jié)果中 排在各個(gè)位置的幾率。比如系統(tǒng)對(duì)某廣告的輸出如下：p1=0.03,p2=0.08,p3=0.04 這說明該廣告展現(xiàn)在第 1 位的概率是 3%，展現(xiàn)在第 2 位的概率是 8%，展現(xiàn)在第 3位的概率是4%問題是：如何給出一個(gè)排名估計(jì)區(qū)間 i,j ，使得廣告出現(xiàn)在該區(qū)間中的概率大 于或等于一個(gè)預(yù)設(shè)值p,同時(shí)這個(gè)區(qū)間所包含的元素盡可能的少。也可用數(shù)學(xué)語(yǔ) 言來描述：給定數(shù)p和數(shù)列p1,p2,pn，求i和j(1<=i<=j<=n)

2、，在滿足 pi+pi+1+pj>=p的前 提下讓j-i 最小。一般來說，pi只需保留6位小數(shù)就足夠了。這樣，若令 ai=106pi , a=106p,則 a和所有的ai均為0,106之間的整數(shù)。這樣就避免了對(duì)實(shí)數(shù)的處理。輸入格式第一行包含一個(gè)整數(shù) n(1<=n<=100,000) 。以下n行每行包含一個(gè)0,106內(nèi)的整數(shù)，依次為al, a2,，an。這n個(gè)整數(shù) 之和保證不超過 106。最后一行包含一個(gè)0,106內(nèi)的整數(shù)a。保證所有ai之和不小于a。輸出格式輸出僅一行，包含一個(gè)整數(shù)，即j -i的最小值。樣例輸入75847105218樣例輸出2樣例解釋a2=8,a3=4,a4=7

3、 之和為 19，滿足條件。而任何兩個(gè)相鄰數(shù)之和均小于18。2.LZW網(wǎng)頁(yè)判重(20分)問題背景有一種簡(jiǎn)單的網(wǎng)頁(yè)判重的方法，通過求兩個(gè)網(wǎng)頁(yè)內(nèi)容的最長(zhǎng)公共子序列(LCS)長(zhǎng) 度來判定兩個(gè)網(wǎng)頁(yè)的相似程度。如：（網(wǎng)頁(yè)A）老師：請(qǐng)用“果然”造句。（網(wǎng)頁(yè)B）學(xué)生：先吃水果，然后喝汽水它們的最長(zhǎng)公共子序列為“果然”， 長(zhǎng)度為 2。注意這里的“子序列”并不要求 連續(xù)。類似的，下面兩個(gè)網(wǎng)頁(yè)：（網(wǎng)頁(yè)A）老師：請(qǐng)用“果然”造句。（網(wǎng)頁(yè)B）學(xué)生：先吃水果，然后喝汽水，果然拉肚子 最長(zhǎng)公共子序列還是“果然”，長(zhǎng)度為 2。但不難看出，由于“果然”兩個(gè)字在 網(wǎng)頁(yè)B中也曾連續(xù)出現(xiàn)，第二組網(wǎng)頁(yè)比第一組更加“相似”。為了區(qū)分開這

4、兩 種情況的區(qū)分度，我們改用一種稱為 LZW的理論。為了嚴(yán)格的敘述相似度的計(jì) 算方法，我們首先定義“文本單元”。假定網(wǎng)頁(yè)用一個(gè)不包含空白字符（空格、回車換行、水平制表符）的字符串來 表示。它只包含純文本，沒有標(biāo)簽。在計(jì)算相似度之前，你應(yīng)該首先對(duì)該字符 串進(jìn)行處 理，劃分成一個(gè)個(gè)“文本單元”。每個(gè)文本單位可以是一個(gè)中文字、 英文單詞（由一個(gè)或多個(gè)連續(xù)的半角英文字母和數(shù)字組成， 正規(guī)表達(dá)式為 a-zA- Z0-9+ ）、或者一個(gè)標(biāo)點(diǎn)符號(hào)。根據(jù)上述定義，同一個(gè)標(biāo)點(diǎn)符號(hào)的全角和半角應(yīng)該被作為不同的文本單元，盡 管他們看起來可能很相近；每個(gè)單獨(dú)全角英文和全角數(shù)字都應(yīng)該被看成一個(gè)單 獨(dú)的文本單元，而連續(xù)的

5、半角英文字母和數(shù)字應(yīng)被看成一個(gè)整體?？傊?，全角 的字符可以與中文字同等對(duì)待。這樣，網(wǎng)頁(yè)被看成文本單元序列。例如，網(wǎng)頁(yè)“內(nèi)容？ 1 2345 6 ?web2.00#”切分出的文本單元序列為（為了顯示方便，用下劃線分隔各文本單元）： 內(nèi) _容_？ _1 _2 _345_6 _?_?_web2_._00_#而網(wǎng)頁(yè)“ why內(nèi)容相似？1234567890,web#00'的切分結(jié)果為：why_內(nèi) _容 _相 _似 _?_?_1234567890_,_web_#_00黑體部分給出了兩個(gè)網(wǎng)頁(yè)的一個(gè)公共子序列。注意“內(nèi)容”、“ ?”分別在兩 個(gè)網(wǎng)頁(yè)中都是連續(xù)出現(xiàn)的文本單元。為了獎(jiǎng)勵(lì)這種情況，LZW規(guī)定

6、一段由連續(xù)k個(gè)文本單元組成的字符串權(quán)值為k2。在剛才的例子中，“內(nèi)容”、“ ？?”的權(quán) 值均為 4。但“ 00”是一個(gè)數(shù)字串，應(yīng)當(dāng)被看成一個(gè)單獨(dú)的文本單元。所以權(quán)值 僅 為 1。根據(jù)上述規(guī)則， 公共子序列“內(nèi)容 ?00”的權(quán)值為 22+22+1=9。在所有可能的子 序列中，這個(gè)權(quán)值是最大的。給定兩個(gè)網(wǎng)頁(yè)，求他們的LZW相似度，即所有可能的公共子序列中的最大權(quán)值。1）輸入的網(wǎng)頁(yè)內(nèi)容以GBK編碼（參見FAQ）2）除了大小寫英文字母和數(shù)字之外的其他半角字符均視為標(biāo)點(diǎn)符號(hào)。 輸入格式包含兩行，分別是網(wǎng)頁(yè) A和B對(duì)應(yīng)的字符串（不包含空白字符）。每行至少包 含 5 個(gè)字節(jié)，最多包含 200 個(gè)字節(jié)。輸出格

7、式輸出僅一行，包含一個(gè)整數(shù)，為兩個(gè)網(wǎng)頁(yè)的LZW相似度。樣例輸入內(nèi)容？ 123456?web2.00#why 內(nèi)容相似 ?1234567890,web#00樣例輸出9樣例解釋盡管兩個(gè)網(wǎng)頁(yè)里看上去都有“ 123456”但一方面第一個(gè)網(wǎng)頁(yè)中混雜的全角和半 角字符，而另一方面，即使全部改成半角字符，由于數(shù)字串“123456”和“1234567890”將分別看成一個(gè)單獨(dú)的文本單元，因此無(wú)法部分匹配。3. 釘子與木板（ 30 分）問題背景墻上有n個(gè)釘子，編號(hào)為1,2,n。其中釘子i的橫坐標(biāo)為i，縱坐標(biāo)初始為xi ?？梢赃M(jìn)行兩種操作：Okv:豎直移動(dòng)釘子k,坐標(biāo)變?yōu)镵v）。1stv ：若在高度為 v 處放一

8、塊橫坐標(biāo)范圍是 s,t 的水平木板，它將下落到什么 高度？換句話說，求出釘子s,s+1,s+2,t的縱坐標(biāo)中，不超過v的最大值。 如果這些釘子的高度全部大于 v,則木板將落到地上，高度為 0。注意，在T 操作時(shí)，水平木板只是用來測(cè)試的“臨時(shí)木板”，將在測(cè)試后立即被拿走，不 會(huì)影響到后續(xù)測(cè)試工作。輸入格式第一行包含兩個(gè)整數(shù)n,m，即釘子的個(gè)數(shù)和操作的個(gè)數(shù)（1<=n,m<=105。以下 n 行一個(gè)不超過 109 的非負(fù)整數(shù)，即 xi 。輸出格式按照輸入的順序，對(duì)于每個(gè)T操作輸出一個(gè)整數(shù)，即該測(cè)試水平木板的最后高 度。樣例輸入54135791246031013571355樣例輸出5704.圓面覆蓋 （40 分）問題背景在平面上有一個(gè)長(zhǎng)為L(zhǎng),寬為W的長(zhǎng)方形，左下角坐標(biāo)為(0,0)，右上角坐標(biāo)為 (L,W) 。給定一些圓，第 i 個(gè)圓的圓心坐標(biāo)為 (xi,yi) ，半徑為 Ri。你的任務(wù)是求最小的正實(shí)數(shù)k，使得把每個(gè)圓的半徑變?yōu)樵瓉淼膋倍后(即：第 i個(gè)圓半徑變?yōu)閗Ri，圓心位置不變)，長(zhǎng)方形將被這些圓完全覆蓋。 換句話說, 長(zhǎng)方形內(nèi)部或邊界上的任意點(diǎn)均至少在一個(gè)圓的內(nèi)部或邊界上。輸入格