百度之星程式設計大賽試題

百度之星程式設計大賽試題

百度之星程式設計大賽試題-1 第一題（共四題100分）：連續正整數（10分） 題目描述：一個正整數有可能可以被表示為n(n>=2)個連續正整數之和，如： 15=1+2+3+4+5

15=4+5+6

15=7+8 請編寫程式，根據輸入的任何一個正整數，找出符合這種要求的所有連續正整數序列。 輸入資料：一個正整數，以指令行參數的形式提供給程式。 輸出資料：在标準輸出上列印出符合題目描述的全部正整數序列，每行一個序列，每個序列都從該序列的最小正整數開始、以從小到大的順序列印。如果結果有多個序列，按各序列的最小正整數的大小從小到大列印各序列。此外，序列不允許重複，序列内的整數用一個空格分隔。如果沒有符合要求的序列，輸出“NONE”。 例如，對于15，其輸出結果是：

1 2 3 4 5

4 5 6

7 8

對于16，其輸出結果是：

NONE 評分标準：程式輸出結果是否正确。 百度之星程式設計大賽試題-2 第二題（共四題100分）：重疊區間大小（20分） 題目描述：請編寫程式，找出下面“輸入資料及格式”中所描述的輸入資料檔案中最大重疊區間的大小。 對一個正整數n，如果n在資料檔案中某行的兩個正整數（假設為A和B）之間，即A<=n<=B或A>=n>=B，則n屬于該行；如果n同時屬于行i和j，則i和j有重疊區間；重疊區間的大小是同時屬于行i和j的整數個數。

例如，行（10 20）和（12 25）的重疊區間為[12 20]，其大小為9；行（20 10）和（12 18）的重疊區間為[10 12]，其大小為3；行(20 10)和（20 30）的重疊區間大小為1。 輸入資料：程式讀入已被命名為input.txt的輸入資料文本檔案，該檔案的行數在1到1,000,000之間，每行有用一個空格分隔的2個正整數，這2個正整數的大小次序随機，每個數都在1和2^32-1之間。（為便于調試，您可下載下傳測試input.txt檔案，實際運作時我們會使用不同内容的輸入檔案。） 輸出資料：在标準輸出上列印出輸入資料檔案中最大重疊區間的大小，如果所有行都沒有重疊區間，則輸出0。 評分标準：程式輸出結果必須正确，記憶體使用必須不超過256MB，程式的執行時間越快越好。 百度之星程式設計大賽試題-3 第三題（共四題100分）：字元串替換（30分） 題目描述：請編寫程式，根據指定的對應關系，把一個文本中的字元串替換成另外的字元串。 輸入資料：程式讀入已被命名為text.txt和dict.txt的兩個輸入資料文本檔案，text.txt為一個包含大量字元串（含中文）的文本，以whitespace為分隔符；dict.txt為表示字元串（s1）與字元串（s2）的對應關系的另一個文本（含中文），大約在1萬行左右，每行兩個字元串（即s1和s2），用一個/t或空格分隔。dict.txt中各行的s1沒有排序，并有可能有重複，這時以最後出現的那次s1所對應的s2為準。text.txt和dict.txt中的每個字元串都可能包含除whitespace之外的任何字元。text.txt中的字元串必須和dict.txt中的某s1完全比對才能被替換。（為便于調試，您可下載下傳測試text.txt和dict.txt檔案，實際運作時我們會使用不同内容的輸入檔案。） 輸出資料：在标準輸出上列印text.txt被dict.txt替換後了的整個文本。 評分标準：程式輸出結果必須正确，記憶體使用越少越好，程式的執行時間越快越好。 第四題（共四題100分）：低頻詞過濾（40分） 題目描述：請編寫程式，從包含大量單詞的文本中删除出現次數最少的單詞。如果有多

個單詞都出現最少的次數，則将這些單詞都删除。 輸入資料：程式讀入已被命名為corpus.txt的一個大資料量的文本檔案，該檔案包含英

文單詞和中文單詞，詞與詞之間以一個或多個whitespace分隔。（為便于調試，您可下載下傳

測試corpus.txt檔案，實際運作時我們會使用不同内容的輸入檔案。） 輸出資料：在标準輸出上列印删除了corpus.txt中出現次數最少的單詞之後的文本（

詞與詞保持原來的順序，仍以空格分隔）。 評分标準：程式輸出結果必須正确，記憶體使用越少越好，程式的執行時間越快越好。 總決賽題如下：

 題目描述：八方塊移動遊戲要求從一個含8個數字（用1-8表示）的方塊以及一個空格方塊（用0表示）的3x3矩陣的起始狀态開始，不斷移動該空格方塊以使其和相鄰的方塊互換，直至達到所定義的目标狀态。空格方塊在中間位置時有上、下、左、右4個方向可移動，在四個角落上有2個方向可移動，在其他位置上有3個方向可移動。例如，假設一個3x3矩陣的初始狀态為：

 8 0 3

 2 1 4

 7 6 5

目标狀态為：

 1 2 3

 8 0 4

 7 6 5

則一個合法的移動路徑為：

 8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3

 2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4

 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 另外，在所有可能的從初始狀态到目标狀态的移動路徑中，步數最少的路徑被稱為最短路徑；在上面的例子中，最短路徑為5。如果不存在從初試狀态到目标狀态的任何路徑，則稱該組狀态無解。  請設計算法找到從八方塊的某初試狀态到某目标狀态的所有可能路徑中的最短路徑，并用C/C++實作。   輸入資料：程式需讀入已被命名為start.txt的初始狀态和已被命名為goal.txt的目标狀态，這兩個檔案都由9個數字組成（0表示空格，1-8表示8個數字方塊），每行3個數字，數字之間用空格隔開。假定start.txt和goal.txt不會相同。 

 輸出資料：如果輸入資料有解，輸出一個表示最短路徑的非負的整數；如果輸入資料無解，輸出-1。請在數字輸出後再輸出一回車換行符。

 自測用例：如果輸入為：start.txt和goal.txt，則産生的輸出應為：

5 如果用

7 8 4

3 5 6

1 0 2

替換start.txt中的内容，則産生的輸出應為：

21  如果用

7 5 2

0 6 3

4 1 8

替換start.txt中的内容，則産生的輸出應為：

-1 

 評分規則：我們将首先使用10組不同的start.txt和goal.txt進行測試，每個測試用例的運作時間在一台Intel Xeon 2.80GHz 4 CPU/6G 記憶體的Linux機器上應不超過10秒（記憶體使用不限制），否則該用例不得分； 每個選手的得分由兩部分組成：正确性得分（10秒鐘内能産生正确結果的測試用例數量x10）和時間性能得分（10秒鐘内産生這些正确結果的測試用例的平均運作毫秒數)。正确性得分高的将始終比正确性得分低的排名在前，即使前者的平均運作時間比後者的要長；正确性得分相同的将按平均運作時間的快慢排列。