1、全國信息學奧林匹克聯(lián)賽（NOIP2008）復賽普及組一.題目概覽中文題目名稱ISBN號碼排座椅傳球游戲立體圖英文題目名稱isbnseatballdrawing可執(zhí)行文件名isbnseatballdrawing輸入文件名isbn.inseat.inball.indrawing.in輸出文件名isbn.outseat.outball.outdrawing.out每個測試點時限1秒1秒1秒1秒測試點數目10101010每個測試點分值10101010比較方式全文比較全文比較全文比較全文比較題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)二.提交源程序文件名對于pascal語言isbn.passeat.pasball.pasd

2、rawing.pas對于C語言isbn.cseat.cball.cdrawing.c對于C+語言isbn.cppseat.cppball.cppdrawing.cpp三.編譯命令（不包含任何優(yōu)化開關）對于pascal語言fpc isbn.pasfpc seat.pasfpc ball.pasfpc drawing.pas對于C語言gcc o isbnisbn.cgcc o seatseat.cgcc o ballball.cgcc o drawingdrawing.c對于C+語言g+ o isbnisbn.cppg+ o seatseat.cppg+ o ballball.cppg+ o dr

3、awingdrawing.cpp四.運行內存限制運行內存上限50M50M50M50M注意事項：1、文件名（程序名和輸入輸出文件名）必須使用小寫。2、C/C+中函數main（）的返回值類型必須是int，程序正常結束時的返回值必須是0。3、全國統(tǒng)一評測時采用的機器配置為：CPU 1.9GHz， 內存512M， 上述時限以此配置為準。各省在自測時可根據具體配置調整時限。1.ISBN號碼 （isbn.pas/c/cpp）【問題描述】每一本正式出版的圖書都有一個ISBN號碼與之對應，ISBN碼包括9位數字、1位識別碼和3位分隔符，其規(guī)定格式如“x-xxx-xxxxx-x”，其中符號“-”是分隔符（鍵盤上

4、的減號），最后一位是識別碼，例如0-670-82162-4就是一個標準的ISBN碼。ISBN碼的首位數字表示書籍的出版語言，例如0代表英語；第一個分隔符“-”之后的三位數字代表出版社，例如670代表維京出版社；第二個分隔之后的五位數字代表該書在出版社的編號；最后一位為識別碼。識別碼的計算方法如下：首位數字乘以1加上次位數字乘以2以此類推，用所得的結果mod 11，所得的余數即為識別碼，如果余數為10，則識別碼為大寫字母X。例如ISBN號碼0-670-82162-4中的識別碼4是這樣得到的：對067082162這9個數字，從左至右，分別乘以1，2，9，再求和，即0×1+6×2

5、+2×9=158，然后取158 mod 11的結果4作為識別碼。你的任務是編寫程序判斷輸入的ISBN號碼中識別碼是否正確，如果正確，則僅輸出“Right”；如果錯誤，則輸出你認為是正確的ISBN號碼。【輸入】輸入文件isbn.in只有一行，是一個字符序列，表示一本書的ISBN號碼（保證輸入符合ISBN號碼的格式要求）。【輸出】輸出文件isbn.out共一行，假如輸入的ISBN號碼的識別碼正確，那么輸出“Right”，否則，按照規(guī)定的格式，輸出正確的ISBN號碼（包括分隔符“-”）。【輸入輸出樣例1】isbn.inisbn.out0-670-82162-4Right【輸入輸出樣例2】i

6、sbn.inisbn.out0-670-82162-00-670-82162-42.排座椅 （seat.pas/c/cpp）【問題描述】 上課的時候總有一些同學和前后左右的人交頭接耳，這是令小學班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當同學們的座次確定下來之后，只有有限的D對同學上課時會交頭接耳。同學們在教室中坐成了M行N列，坐在第i行第j列的同學的位置是（i，j），為了方便同學們進出，在教室中設置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個辦法，或許可以減少上課時學生交頭接耳的問題：她打算重新擺放桌椅，改變同學們桌椅間通道的位置，因為如果一條通道隔開了

7、兩個會交頭接耳的同學，那么他們就不會交頭接耳了。請你幫忙給小雪編寫一個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學生對數最少。【輸入】輸入文件seat.in的第一行，有5各用空格隔開的整數，分別是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。接下來D行，每行有4個用空格隔開的整數，第i行的4個整數Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個同學會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。輸入數據保證最優(yōu)方案的唯一性。【輸出】輸出文件seat.out共兩行。第一

8、行包含K個整數，a1a2aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、第aK行和第aK+1行之間要開辟通道，其中ai< ai+1，每兩個整數之間用空格隔開（行尾沒有空格）。第二行包含L個整數，b1b2bk，表示第b1列和b1+1列之間、第b2列和第b2+1列之間、第bL列和第bL+1列之間要開辟通道，其中bi< bi+1，每兩個整數之間用空格隔開（行尾沒有空格）。【輸入輸出樣例】seat.inseat.out4 5 1 2 34 2 4 32 3 3 32 5 2 422 4【輸入輸出樣例解釋】34*2+11 2 3 4 5上圖中用符號*、+ 標出了3對會交頭接耳

9、的學生的位置，圖中3條粗線的位置表示通道，圖示的通道劃分方案是唯一的最佳方案。本題貪心可以得滿分的。當然本題的貪心需要預處理下，開2個一維數組，rowi 記錄如果在第i行加通道,可以分割多少對調皮學生,coli記錄如果在第j列加通道,可以分割多少對調皮學生,最后貪心法輸出分割學生最多的前K行和前L列。3.傳球游戲 （ball.pas/c/cpp）【問題描述】上體育課的時候，小蠻的老師經常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。游戲規(guī)則是這樣的：n個同學站成一個圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意）

10、，當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節(jié)目。聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，并假設小蠻為1號，球傳了3次回到小蠻手里的方式有1->2->3->1和1->3->2->1，共2種。【輸入】輸入文件ball.in共一行，有兩個用空格隔開的整數n，m（3<=n<=30，1<=m<=30）。

11、【輸出】輸出文件ball.out共一行，有一個整數，表示符合題意的方法數。【輸入輸出樣例】ball.inball.out3 32【限制】40%的數據滿足：3<=n<=30，1<=m<=20100%的數據滿足：3<=n<=30，1<=m<=30直接dp，似乎說遞推更確切點。f(i,k)表示經過k次傳到編號為i的人手中的方案數。那么可以推出下面的方程：f(i,k)=f(i-1,k-1)+f(i+1,k-1) （i=1或n時，需單獨處理）邊界條件：f(1,0)=1;結果在f(1,m)中4.立體圖 （drawing.pas/c/cpp）【問題描述】小淵是

12、個聰明的孩子，他經常會給周圍的小朋友們講些自己認為有趣的內容。最近，他準備給小朋友們講解立體圖，請你幫他畫出立體圖。小淵有一塊面積為m*n的矩形區(qū)域，上面有m*n個邊長為1的格子，每個格子上堆了一些同樣大小的積木（積木的長寬高都是1），小淵想請你打印出這些格子的立體圖。我們定義每個積木為如下格式，并且不會做任何翻轉旋轉，只會嚴格以這一種形式擺放： +-+ / /| 高+-+ | | +| |/ 寬+-+ 長每個頂點用1個加號+表示，長用3個”-“表示，寬用1個”/”表示，高用兩個”|”表示。字符+ -/ |的ASCII碼分別為43，45，47，124。字符.（ASCII碼46）需要作為背景輸出

13、，即立體圖里的空白部分需要用.代替。立體圖的畫法如下面的規(guī)則：若兩塊積木左右相鄰，圖示為：.+-+-+./ / /|+-+-+ | | | +| | |/.+-+-+.若兩塊積木上下相鄰，圖示為：.+-+./ /|+-+ | | +| |/|+-+ | | +| |/.+-+.若兩塊積木前后相鄰，圖示為：.+-+/ /|.+-+ |./ /| +-+ |/.| | +.| |/+-+.立體圖中，定義位于第(m,1)的格子（即第m行第1列的格子）上面自底向上的第一塊積木（即最下面的一塊積木）的左下角頂點為整張圖最左下角的點。【輸入】輸入文件drawing.in第一行有用空格隔開的兩個整數m和n，

14、表示有m*n個格子（1<=m，n<=50）。接下來的m行，是一個m*n的矩陣，每行有n個用空格隔開的整數，其中第i行第j列上的整數表示第i行第j列的格子上摞有多少個積木（1<=每個格子上的積木數<=100）。【輸出】輸出文件drawing.out中包含題目要求的立體圖，是一個K行L列的字符矩陣，其中K和L表示最少需要K行L列才能按規(guī)定輸出立體圖。【輸入輸出樣例】drawing.indrawing.out3 42 2 1 22 2 1 13 2 1 2.+-+-+.+-+.+-+ / /|./ /|./ /|-+-+ |.+-+ |+-+ |/ /| +-| | +| | +-+ |/+-+ |/| |/ /| +/ /|-+ |+-+-+ |/+-+ |/| +| | | +-| | + |/.| | |/ | |/| +.+-+-+-+-+ |/.| | | | | +.| | | | |/.+-+-+-+-+.Pku原題，編號2330算不上難題，但是比較麻煩，細心點就ok了。先計算