1、PAGE PAGE 8組隊選拔賽共有五道題，完成時間共3小時。每題有十組測試數(shù)據(jù)，每組10分，每題100分，共500分。= 運 動 會 題目描述：運動會.doc 輸入數(shù)據(jù)：sports1.in sports10.in 輸出數(shù)據(jù)：sports1.out- sports10.out 數(shù)字游戲 題目描述：數(shù)字游戲.doc 輸入數(shù)據(jù)：Game1.in Game10.in 輸出數(shù)據(jù)：Game1.out Game10.out 雙調路徑 題目描述：雙調路徑.doc 輸入數(shù)據(jù)：bic1.in - bic10.in輸出數(shù)據(jù)：bic1.out- bic10.out 數(shù) 列 題目描述：數(shù)列.doc 輸入數(shù)據(jù)：seq

2、1.in - seq10.in 輸出數(shù)據(jù)：seq1.out - seq10.out 群的計數(shù) 題目描述：群的計數(shù).doc 輸入數(shù)據(jù)：group1.in - group10.in 輸出數(shù)據(jù)：group1.out - group10.out 運動會sports.pas/c/cpp 時間限制：1S 100分 【問題描述 】 某屆運動會共有n個項目，編號為1，2，.，n（1=n=100）。項目無先后順序關系，共有k個人參賽，（1=k=參加人數(shù)，即跑一次，就可決出名次。問題要求給出一種安排，用最少時間（天數(shù)）完成比賽，并保證所有人都能完成參賽項目。n =4，k=4參賽情況 第1人 參加 1，2項目 第2

3、人 參加 1，3項目 第3人 參加 2項目 第4人 參加 4項目安排 第一天 1，4 項目（不唯一） 第二天 2，3 項目共2天，完成比賽n =4，k=2參賽情況 第1人 參加 1，2項目 第2人 參加 3，4項目安排 第一天 1，3 項目（不唯一） 第二天 2，4 項目【輸入文件 】 第一行2個整數(shù)n ，k（數(shù)字間一個空格）以下共有k行，每行表示每人的參賽項目，項目號用一個整數(shù)表示，兩數(shù)之間用一個空格隔開，每行均以0結束【輸出文件 】一個整數(shù)，即天數(shù)【樣 例 】 sports.in4 2 1 2 0 3 4 0sports.out2 數(shù)字游戲Game.pas/c/cpp 時間限制：1S 10

4、0分【問題描述 】考慮下面一個兩個人玩的游戲：在一個游戲板上有N個正整數(shù)（2 = N = 100）排成一列。玩家1先玩。兩個玩家交替從這列數(shù)的兩端取數(shù)。取得的數(shù)值加入玩家的總分中，取完數(shù)后，如果玩家的分數(shù)大于他的對手的分數(shù)，他就贏了。問題寫一個程序執(zhí)行最優(yōu)策略。最優(yōu)策略是指的是與“最好的情況”對抗，你的程序認為對手也是用最優(yōu)策略的。【輸入文件 】：第一行是一個正整數(shù)N，是游戲板上正整數(shù)的數(shù)量；第二行到第N+1行，依次是游戲板上從左到右的N個數(shù)。【輸出文件 】：輸出文件只有一行，兩個數(shù)，分別是玩家1和玩家2的分數(shù)，用一個空格隔開。【樣 例 】game.in6472952game.out11 雙調

5、路徑 bic.pas/c/cpp時間限制： 3S 100分 【問題描述 】如今的道路收費發(fā)展很快。道路的密度越來越大，因此選擇最佳路徑是很現(xiàn)實的問題。城市的道路是雙向的。每條道路有固定的旅行時間以及需要支付的費用。路徑是連續(xù)經(jīng)過的道路組成的。總時間是各條道路旅行時間的和，總費用是各條道路所支付費用的總和。一條路徑越快，或者費用越低，該路徑就越好。嚴格地說，如果一條路徑比別的路徑更快，而且不需要支付更多費用，它就比較好。反過來也如此理解。如果沒有一條路徑比某路徑更好，則該路徑被稱為最小路徑。這樣的最小的路徑有可能不止一條，或者根本不存在路徑。例子下圖給出了一個網(wǎng)絡，每條路有兩個參數(shù)：費用和時間。

6、從1到4有4條路徑。124(fee4, time5), 134(fee4, time5), 1234(fee6, time4)，1324(fee4, time10)。134和 124比 1324更好。有兩種最佳路徑：fee4, time5 (roots 124 and 134) 和 fee6, time4 (root 1234)。問題：從文件bic.in中讀入網(wǎng)絡，計算最小路徑的總數(shù)。費用時間都相同的兩條最小路徑只算作一條。你只要輸出不同種類的最小路徑數(shù)即可。【輸入文件 】：文件的第一行有4個整數(shù)，城市總數(shù)n, 1n100, 道路總數(shù) m, 0m300, 起點和終點城市s，e, 1s,en,

7、se。接下來的m行每行描述了一條道路的信息，包括4個整數(shù)，兩個端點p，r，費用c，以及時間t，1p,rn, pr, 0c100, 0t100。兩個城市之間可能有多條路徑連接。【輸出文件 】：僅一個數(shù)，表示最小路徑的總數(shù)。【樣 例 】Bic.inbic.outComments4 5 1 42 1 2 13 4 3 12 3 1 23 1 1 42 4 2 42該例對應前面的圖。數(shù) 列 seq.pas/c/cpp 時間限制：10 S 100分 【問題描述 】 有這樣一種數(shù)列A1、A2、A3、An，其中A1=0，且對任意一項Ai滿足|Ai-Ai+1|=1（1=in）。設S=A1+A2+A3+An，表

8、示前n項之和。問題：現(xiàn)在給出數(shù)列長度n與數(shù)列前n項之和S，要求：輸出滿足條件的數(shù)列的總數(shù)。輸出滿足條件的100個數(shù)列（如果不滿100個就全部輸出）。【輸入文件 】： 一行，包含兩個整數(shù)n和S（1=n=100），用1個空格隔開。【輸出文件 】 第1行一個整數(shù)t（0=t=263-1），表示滿足條件的數(shù)列總數(shù)。接下來每行輸出一個數(shù)列，數(shù)列各項之間用一個空格隔開。若滿足條件的數(shù)列數(shù)目不滿100個，全部輸出即可。【樣 例 】seq.in4 0seq.out20 -1 0 10 1 0 -1群的計數(shù) group.pas/c/cpp 時間限制： 2S 100分【問題描述 】代數(shù)學研究的基本對象之一群是一些元

9、素的集合。這些元素之間有一種代數(shù)運算，稱之為乘法。兩個群元素的乘積是一個群元素。一個大家習以為常的群是有理數(shù)乘法群，例如，等等，都是這個群中乘法的例子。需要注意的是，如果了此們僅僅考慮有理數(shù)的乘法群，另外的一些運算比如加法是不被討論的。數(shù)學家們把乘法抽象出來，就成為了群。群需要滿足以下三條性質：結合律：對群中的任意元素a,b,c 有 a(bc)=(ab)c單位元：在群中存在唯一的元素e，它對群中任意的元素a有ea=a，ae=a有理數(shù)乘法群的單位元是1逆 元： 對群中任意元素a,都存在群中唯一的元素b,使得ab=ba=e比如有理數(shù)乘法群中，23的逆元就為。從這里可以看出，整數(shù)乘法不能構成一個群。

10、需要注意的是，群的定義中并沒有交換律，就是說ab不一定等于ba，有理數(shù)乘法群作為一個特例，其交換性是沒有普遍的意義的。問題：現(xiàn)在的問題是，給定群的元素的個數(shù)（群的階數(shù)），需要知道這樣的群有多少種。只要滿足上述三條性質，就是群，應該算上。 下面用四階群的例子來說明這個問題。抽象地記群元素為e,a,b,c 只要列出一個乘法表，就可以代表一個群。下面給出推導乘法表的步驟：群1EABcEe (1)a (1)b (1)c (1)Aa (1)e (2)c (3)b (3)Bb (1)c (3)e (4)A (5)Cc (1)b (3)a (5)e (5)有單位元素的性質，可以填上：a*a可能為e,b,c，

11、但不可能為a,否則a*a=a兩邊乘以a的逆元，得到a=e；a*a=b和a*a=c的情況是一樣的，只是乘法表中元素的位置進行了一個變換，本質沒有改變，稱為一個群同構；此時可以把a*a得到的元素稱為b；所以只要討論a*a=e和a*a=b的情況；下面先討論a*a=e的情況a*b不能為a或e，a*b為b的話，a=e，也矛盾，所以a*b=c；同理可填上所有的(3)b*b=e時，b*c=c*b=a，c*c=e，得到群1b*b=a時，b*c=c*b=e，c*c=a，得到群2群2EAbcEe (1)a (1)b (1)c (1)Aa (1)e (2)c (3)b (3)Bb (1)c (3)a (4)e (5)Cc (1)b (3)e (5)a (5)當a*a=b時，按照標號順序可填出下列的群：群 2EAbcEe (1)a (1)b (1)c (1)Aa (1)b (2)c (4)e (3)Bb (1)c (4)e (6)a (5)Cc (