省選01-06noi2003選拔賽試卷

1、NOI2003福建省選手選拔賽試卷考生須知*若試卷中試題字跡不清，考生可以在審題時舉手請求解釋，由考務(wù)人員加以說明。涉及題意理解問題，則不得提問且考務(wù)人員不予解答。*考生上機編程時應(yīng)在指定目錄下工作，并請每隔5分鐘存盤一次。發(fā)生機器故障時由考務(wù)人員確認(rèn)補給修復(fù)時間，且最長不超過10分鐘。*對考生答題測試有嚴(yán)格時間限制，若超時則該測試項判為0分?？忌鷳?yīng)注意優(yōu)化算法。*考生應(yīng)嚴(yán)格遵守考場規(guī)則，不得違紀(jì)。 *考試時間為8時30分至12時，計210分鐘（其中30分鐘為審題時間）。試卷滿分為100分試題一、整數(shù)因子團問題 (30分)問題描述：整數(shù)因子團是一個有趣的智力游戲。游戲規(guī)則如下： 1、給定由n個

2、連續(xù)自然數(shù)組成的序列1，n。2、從當(dāng)前序列中選擇一整數(shù)，它在當(dāng)前序列中至少有2個因子(該整數(shù)本身可以算作一個因子，例如，整數(shù)60的所有因子是：60，30，20，15，12，10，6，5，4，3，2，1。它們構(gòu)成整數(shù)60在當(dāng)前序列中的因子團 )。 3、從當(dāng)前序列中刪去所選整數(shù)的所有因子。 4、重復(fù)步驟2和3，直到空序列或當(dāng)前序列中所有數(shù)字在序列中僅有一個因子。你在游戲中的得分是步驟2中所選擇的數(shù)字的總和。例如，當(dāng)n=6時，給定的序列為1，2，3，4，5，6。一個游戲過程是：步驟2：選擇整數(shù)5；步驟3：從當(dāng)前序列中刪去整數(shù)5的所有因子5，1。當(dāng)前序列改變?yōu)椋?，3，4，6。 步驟2：選擇整數(shù)6；步

3、驟3：從當(dāng)前序列中刪去整數(shù)6的所有因子6，2，3。當(dāng)前序列改變：4。游戲結(jié)束。該游戲的得分是11。另一個游戲過程如下：步驟2：選擇整數(shù)5；步驟3：從當(dāng)前序列中刪去整數(shù)5的所有因子5，1。當(dāng)前序列改變?yōu)椋?，3，4，6。步驟2：選擇整數(shù)4；步驟3：從當(dāng)前序列中刪去整數(shù)4的所有因子4，2。當(dāng)前序列改變?yōu)椋?，6。步驟2：選擇整數(shù)6；步驟3：從當(dāng)前序列中刪去整數(shù)6的所有因子6，3。當(dāng)前序列改變?yōu)榭招蛄?。游戲結(jié)束。該游戲的得分是15。從上面的例子不難看出，游戲的步驟2所選數(shù)字的次序?qū)τ螒虻牡梅钟泻艽笥绊憽?yīng)該如何選擇才能使游戲獲得最大得分?編程任務(wù)：給定正整數(shù)n的值（1 n 120），編程計算按照上述

4、游戲規(guī)則所能得到的最大得分。數(shù)據(jù)輸入：從鍵盤輸入正整數(shù)n的值。結(jié)果輸出: 程序運行結(jié)束時，在屏幕上輸出按照游戲規(guī)則所能得到的最大得分。輸入示例輸出示例615試題二、代表的選派問題 (30分)問題描述：每三年一次的*區(qū)代表大會即將召開，規(guī)定該區(qū)每個單位最多只能派一個人參加這個大會。已知該區(qū)有k個單位，0 k =500，每個單位的人數(shù)都不超過200人，因此最好的情況是每個單位都有一個人參加大會，即在最好的情況下有k個人分別代表其各自的單位參加大會。但是事情往往沒有那么簡單，在現(xiàn)實世界中有的單位可能沒人，有的人可能屬于幾個單位。問題為了使大會開得隆重又有廣泛的代表性，應(yīng)如何選派代表使得有盡量多的人參

5、加大會？編程任務(wù)： 給定每個單位的人員情況，求出所有單位所能派出的參加大會的最多的人數(shù)。數(shù)據(jù)輸入： 輸入數(shù)據(jù)由文件input2.*給出，不超過k+1行。第1行是單位的個數(shù)，即k的值。從第2行起每個有人的單位各占一行，其中每行列出該單位所有員工的姓名，每個員工的姓名用13個無間隔的英文字母或阿拉伯?dāng)?shù)字表示，姓名與姓名之間用空格隔開。結(jié)果輸出: 程序運行結(jié)束時，在屏幕上輸出參加大會的最多的人數(shù)。輸入文件示例輸出示例Input2.*3a1 a2 a3a1 a12試題三、DNA分子的最佳比對（本題滿分40分）問題描述： DNA分子是人類遺傳信息的載體，它間接地指導(dǎo)蛋白質(zhì)的合成。DNA分子是由四種核苷酸

6、組成的長鏈，這四種核苷酸分別是腺嘌呤核苷酸（用A代表）、鳥嘌呤核苷酸（用G代表）、胞嘧啶核苷酸（用C代表）和胸腺嘧啶核苷酸（用T代表）。習(xí)慣上用一個字符集為A，T，C，G的字符串來表示一個DNA分子序列，如CGTTAGA。 在生物進化過程中，DNA分子可能發(fā)生各種各樣的突變。這種突變形成了生物遺傳信息的改變，從而使生物得以分化，構(gòu)成了生物的多樣性。主要的突變有三種：（1）在一個DNA序列中插入一個新的核苷酸，（2）DNA序列中丟失了一個核苷酸，（3）DNA序列中的某個核苷酸被另一個核苷酸所取代。 所謂兩個DNA序列的一個比對是尋找一種排列方式，使得兩個DNA序列在同樣的位置上有相同的核苷酸，而

7、若在同樣的位置上兩個DNA序列的核苷酸不同，則是由三種突變之一得到。例如，對兩個DNA序列T=ATCAG，T=ACTAG，可以按如下方式比對， 比對1： T T A A T - （“-”表示空白） C C - T A A G G也可以按如下方式比對 比對2： T T A A T C C T A A G G如果兩個DNA序列在相同的位置上有越多相同的核苷酸對，則表明它們之間越相似，即它們存在功能上的相似性和進化史上的親緣關(guān)系。 對于兩個DNA序列的一個比對，規(guī)定如下得分方式：（1）一個同樣的位置上有相同的核苷酸對，則可得1分；（2）一個同樣的位置上有不同的核苷酸對，則得0分；（3）如果在某個位置

8、上一個序列有核苷酸，而另一個序列在該位置上為“-”，則得-2分。例如，比對1的得分是0分，比對2的得分是3分。 編程任務(wù)：對于兩個DNA序列，尋找一種比對方式，使得它們的得分最高。數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為INPUT3.*的文本文件提供，共有2行。第1行為DNA序列T, 第2行為DNA序列T。序列的長度不大于5000。序列中的字母是英文小寫或者大寫字母。結(jié)果輸出:程序運行結(jié)束時，在屏幕上輸出兩個DNA序列比對的最高得分。輸入文件示例輸出示例INPUT3.001AtcagActag3NOI2003福建省選手選拔賽測試記錄姓名學(xué)校測試日期總得分題1輸入輸出滿分時限用時實際輸出實際得分1.120124511.255981551.38221875101.410131685101.511037645101.612045935180題2輸入輸出滿分時限用時實際輸出實際得分2.1INPUT2.0012512.2INPUT2.0023512.3INPUT2.00345512.4INPUT2.004187512.5INPUT2.00574512.6INPUT2.00617351題3輸入輸出滿分時限用時實際輸出實際得分