1、讀書破萬卷 下筆如有神 USACO 三月份試題 簡體中文版本 By xzh *華麗的分割線* 青銅組問題 *華麗的分割線* 四道題目，編號從 11 到 14 *華麗的分割線* 問題 11：極品飛車 貝西正在為一場即將到來的大獎賽準備她的賽車。她希望購買一些部件來提高這輛賽車的性能。他的賽車質量為 M (1 = M = 1,000)，加速度為(1 = F = 1,000,000)。在賽車的配件店有 N(1 = N = 20)個零件，編號分別為 1 到 N。只要他愿意，貝西可以買任意多個或者任意少個零件。 第 P_i 個零件增加加速度 F_i (1 = F_i = 1,000,000)，同時重量為

2、 M_i (1 = M_i = 1,000)。根據牛頓第二定律，F=MA，F 為加速度，M 為質量，A 為速度。為了使她的賽車最大限度的發揮它的加速度的同時減少重量，她應該安裝哪些組件？ 假設一輛賽車，他的初始加速度為 1500，初始重量為 100，有四種零件可以選擇： i F_i M_i 1 250 25 2 150 9 3 120 5 8 200 4 讀書破萬卷 下筆如有神 如果只添加零件 2，他的速度將是(1500+150)/(100+9) = 1650/109 = 15.13761。 下面是一個表格，表現了添加或不添加不同的零件后賽車的速度。 （0 表示未添加，1 表示已添加） 部件

3、總和 總和 1234 F M F/M 0000 1500 100 15.0000 15.7407 108 1700 0001 15.4286 105 0010 1620 113 1820 16.1062 0011 15.1376 109 0100 1650 117 15.8120 1850 0101 0110 1770 15.5263 114 F/M 最高的 0111 1970 122 16.1475 - 125 14.0000 1000 1750 14.6617 133 1950 1001 130 1010 1870 14.3846 2070 1011 15.0000 138 1900 13

4、4 14.1791 1100 1101 142 2100 14.7887 1110 139 2020 14.5324 1111 2220 15.1020 147 讀書破萬卷 下筆如有神 最終，最佳的方案是選擇 2，3 和 4 號部件 問題名稱: boost 輸入格式： 第一行：三個整數：F,M 和 N 從第二行到第 N+1 行：第 I+1 行有兩個整數：F_i 和 M_i 樣例輸入：(文件 boost.in): 1500 100 4 250 25 150 9 120 5 200 8 輸出格式 第一到 P 行：P 個貝西應該給他的賽車增加的額外部件的編號，每個一行。如果一個也不要增加，輸出NON

5、E（不帶引號） 。 輸出順序應該是遞增，因此，如果零部件的最優解集為（2,4,6,7） ， 那么輸出應為 2,4,6,7，而不是例如 4,2,7,6 之類的。 樣例輸出：（文件 boost.out）： 2 3 4 讀書破萬卷 下筆如有神 *華麗的分割線* 問題 12：傳說中的十六進制轉換 貝西在給杰西上課。她在講一些關于二進制的有趣的事實。一般來說計算機所有數字存儲為 0和 1。杰西對于這些有一些不清楚，于是貝西給他做了以下的練習： 編寫一個程序，把一個一個無符號的十六進制數轉換成八進制（基數為 8）的形式。十六進制數最多只能有 100000 個數字，包含數字和大寫字母從 A 至 F。 注意！

6、十六進制數是一種特殊的表示數字的方式（基數為 16） 。 0-9 的數字仍符合 0-9，然后A（大寫 A！）代表 10，B 代表 11，等等（到 F 為止） 。 例如，十六進制數 A10B 對應的十進制是 10 * 16 3 1 * 16 2 0 * 16 11 * 1 = 41227。相應的八進制（基數為 8）是 120413，即 1 * 8 5 2 * 8 4 0 * 8 3 4 * 8 2 3 * 1 * 8= 41227。 提示：有一個更簡單的方法從十六進制轉換為八進制數比起從十六進制轉換到十進制再到八進制。你可以試一試二進制（基數為 2） 。 問題名稱：hex 輸入格式： 第一行：一

7、個十六進制數。前面沒有多余的 0（即 A1，而不是 00A1） 。0本身是一個有效的輸入。 樣例輸入：（文件 hex.in）： 123ABC 讀書破萬卷 下筆如有神 輸出格式： 第一行：一個前面沒有多余零的八進制值。如果輸入為 0，輸出也應為 0。 樣例輸出（文件 hex.out）： 4435274 *華麗的分割線* 問題 13 Master Mind 杰西正在了解在“貝西的膝蓋”節目比賽。 “他們在玩游戲嗎？”她問。 “噢，是的， ”貝茜一本正經地點頭。 “這是一個經典的游戲。 ” Master Mind 是一個典型的多人游戲。一個玩家是 Code maker，她挑選一個四位數字的秘密數 S

8、 (1000 = S =9999)。另一個玩家是 Code breaker。他將猜測這四個數字可能是什么。直到他找到了正確的答案。 每個 Code breaker 猜測 G_i (1000 = G_i = 9999)時，Code maker 將提供一些提示，包括兩個整數。 第一個整數 C_i (0 = C_i = 4)指定了多少猜測的數字是正確的，而且他們在秘密號碼中正確的位置 第一個整數 W_i(0 = W_i = 4-C_i)指定了多少猜測的數字是正確的，但是不屬于 C_i， 因為他們在秘密號碼中錯誤的位置。 讀書破萬卷 下筆如有神 例如，假設 Code maker 的秘密號碼是 2351

9、。如果密碼破譯者猜測 1350，Code maker 將提供反饋 2 1，因為 3 和 5 是在正確的位置的數目，然而 1 在錯誤的位置。又例如，如果秘密號碼是 11223（在位數為五的版本）和猜測是 12322，則反饋將是 2 2。 下面是一個示例游戲，秘密號碼是 2351： 猜測的值 | 正確的數字正確的位置 | 正確的數字錯誤的位置 3157 1 2 1350 2 1 6120 0 2 2381 3 0 2351 4 0 對于這個任務，您將得到 N (1 = N = 100)與在游戲中他們的猜測和反饋。要求輸出最小的四位數字，可以是一個候選的 Code maker 的秘密代碼（即，它滿足

10、所有條件） 。 如果沒有這樣的數字，輸出NONE（不帶引號） 。 輸入格式： 第 1 行：一個整數：N 第二行到第 N+1 行：一個猜測的值以及 Code maker 的反饋。表現為空格分隔的整數：G_i，C_i 和 W_i。 ：）mmind.in 樣例輸入（文件讀書破萬卷 下筆如有神 4 3157 1 2 1350 2 1 6120 0 2 2381 3 0 輸出格式： *第 1 行：單個的整數，是最小的四位數的可能的秘密代碼。如果沒有這樣的數字，輸出一行包（秘密整數的范圍：1000 . 9999）含單詞NONE（沒有引號） 。 樣例輸出（文件 mmind.out）： 2351 *華麗的分割

11、線* 問題 14 最長公共子串 貝西的朋友杰西想進入編程競賽。 “這個任務是什么？“她問道。 貝西，她知道這么多。她說：“這是一個典型的公共子串問題，早在很久以前就有了。看看你是否能解決這個問題。 “ 也許你能做到！讀書破萬卷 下筆如有神 您將得到兩個整數以及 S1 和 S2 這兩個序列。 S1 的長度為 L1 (1 = L1 = 180)，而 S2 的長度為 L1 (1 = L1 = 180)。你的工作是打印出最長公共子串的長度。 S1 和 S2 只含有普通的數字。有序序列 S1 的元素分別為 S1_1，S1_2，.，S1_L1 (-100 = S1_i = 100); S2 的元素分別為

12、S2_1，S2_2，.，S2_L1 (-100 = S2_i = 100)。 一個字串是指數字連續沒有中斷的序列。比如說 1231 的字串有空序列， “1” ， “1 2” ， “1 2 3” ，“1 2 3 4” ， “2” ， “2 3” ， “2 3 1” ， “3”和“3 1” Sub 問題名稱： 輸入格式：L2 L1 和第一行：兩個用空格分隔的整數：S1_i 行：每一行中包含一個整數：L1+1 第二行到第S2_i 行：每一行中包含一個整數：行到第 L1+L2+1L1+2 第 ）：樣例輸入（文件 sub.in 10 12 1 1 1 3 2 3 3 3 讀書破萬卷 下筆如有神 4 5 1