1、第五屆全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第五屆全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （提（提 高高 組組 競賽用時(shí)：競賽用時(shí)：3 小時(shí)）小時(shí)）第一題第一題 攔截導(dǎo)彈攔截導(dǎo)彈(28(28 分分) ) 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)） ，計(jì)算這套系統(tǒng)最多能攔截多

2、少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）第二題第二題 回文數(shù)回文數(shù)(25(25 分分) )若一個數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。 例如：給定一個 10 進(jìn)制數(shù) 56，將 56 加 65（即把 56 從右向左讀） ，得到 121 是一個回文數(shù)。 又如：對于 10 進(jìn)制數(shù) 87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627

3、 = 1353 STEP4：1353+3531 = 4884 在這里的一步是指進(jìn)行了一次 N 進(jìn)制的加法，上例最少用了 4 步得到回文數(shù) 4884。 寫一個程序，給定一個 N（2=Nk)and(di=dk)顯然有 dn=1，故從 n 逆推至 d1即可,則 MAXdk為所求。 1=k=n第二問顯然要難一點(diǎn)，最直觀的算法是貪心，但是反例也容易找到，如：6 5 1 7 3 2如果第一次打 6 5 3 2,顯然還要打兩次，而最好的方案是 6 5 1/7 3 2。顯然失敗之處在于第一種方案為了多打 3 和 2，把 1 和 7 隔斷了，但事實(shí)上把 3 和 2 留給第二套打還不是一樣！因?yàn)槊總€導(dǎo)彈都要打到，

4、故我們應(yīng)該把注意力放在“打到每一枚導(dǎo)彈”。在上一個例子中，7 是必須打到的， 因?yàn)樗亲罡叩模员赜幸淮螖r截是以 7 開頭的！既然是必須，那么打 7 的同時(shí)順便打一打其他的絕對不比不打差！那么打哪些呢？下面說明：應(yīng)該打后面導(dǎo)彈中最高的一個 K。先定義一個概念：把當(dāng)前能打的最大高度叫做“能力”理由如下：對于 K 以后的導(dǎo)彈，絕對該打 K，因?yàn)閷τ?K 以后的導(dǎo)彈，不打 K 時(shí)能打到的，打了 K 也能打到（K 是最高的嘛！）,K 等于是“白打”，而對于 7 和 K 之間的導(dǎo)彈，打了任何一個就一定不能再打K 了（K 最高嘛！）反正中間的和K 不能一次打，先打不會比后打差！類似的，下一個目標(biāo)是 K

5、后面的最高的。可以證明，該算法是正確的（從略），基礎(chǔ)較好的同學(xué)也可以通過建立有向無環(huán)圖來理解和證明這一算法。程序見附件。第二題 同普及組第二題，參見普及組試題解析第三題 同普及組第三題，參見普及組試題解析第四題 郵票面值設(shè)計(jì)（40 分） 給定一個信封，最多只允許粘貼 N 張郵票，計(jì)算在給定 K（N+k=40) 種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設(shè)計(jì)郵票的面值，能得到最大 max ，使得 1max 之間的每一個郵資值都能得到。 例如，N=3，K2，如果面值分別為 1 分、4 分，則在 l 分-6 分之間的每一個郵資值都能得到（當(dāng)然還有 8 分、9 分和 12 分）：如果面值分別為

6、1 分、3 分，則在1 分-7 分之間的每一個郵資值都能得到。可以驗(yàn)證當(dāng) N=3，K2 時(shí)，7 分就是可以得到連續(xù)的郵資最大值，所以 MAX=7，面值分別為 l 分、3 分。 樣例： INPUT N=3 k=2 OUTPUT 1 3 MAX=7分析不知同學(xué)們第一個感覺是不是遞推？反正我當(dāng)時(shí)是。我想了一會兒，發(fā)現(xiàn)遞推是行不通的，然后一個很自然的思路就是搜索。當(dāng)時(shí)我很不想用搜索，因?yàn)樯舷奘荎=40,N=40,但后來才知道這是出題者的一個疏忽，根本不可能在時(shí)限內(nèi)到 40 的。從下面的測試數(shù)據(jù)中也可以看出來。解狀態(tài)是一個 K 元組(v1,v2,v3.vk),不妨設(shè)：v1V2=R+2,則 R+1 根本不

7、可能取到。遞歸搜索就可以了。本題的難點(diǎn)是如何計(jì)算最大連續(xù)值（以下成為 Q 值）。一個容易想到的方法是枚舉所有的取法，求出可以取到的最大值，再求 Q 值，簡單，但是效率不高。以下是供參考的遞推方法：遞推求 Q 值，保存前 P 個面值用 1,2,3.K 張可以取得的值，再加上第 P+1 張取與不取的情況可以得到前 P+1 個面值用 1,2,3.K 張可以取得的值。即，用 T 張前 P 個面值能得到 S,用 T+1 張前 P+1個面值可以得到 S+VP+1,用 T 張前P+1 個面值也能得到 S.為了使程序易懂，我采用的是簡單的方法，效率低一些，但是好懂一些。以下我競賽時(shí)寫的程序，后來加了很多注釋，將就看一下吧！我先把可能不好懂的地方說一下：1.Cont(x)就是前 x 個元素的 Q 值2.Find(Findstart,Contstart,x)