程序設(shè)計訓練題目

1、FIRST(一)汽水瓶題目描述小明非常喜歡喝汽水，家門口的超市今天搞活動，2個汽水空瓶或者4個瓶蓋可以換1瓶汽水，小明現(xiàn)在已經(jīng)買了 n瓶汽水，請問通過這個活動可以多得到多少瓶汽水？輸入每行輸入一個整數(shù)n(0n108 )，如果n=0 ,表示輸入結(jié)束，這個樣例不需要處理。輸出每行輸出一個結(jié)果。樣例輸入1 5 0樣例輸出0 10(二)局域網(wǎng)題目描述IPv4的地址是一個32位無符號整數(shù)，一般使用四段式表示，比如192.168.0.1，每一段表示一個字節(jié)的值。子網(wǎng)掩碼也是一個 32位無符號整數(shù)，也可以使用四段式表示，比如 255.255.255.0。 IP地址與子網(wǎng)掩碼 的按位與的結(jié)果得到子網(wǎng)的網(wǎng)絡地址

2、，兩臺主機必須在同一個子網(wǎng)才能通信。比如，主機 A的IP是192.168.0.1 ,子網(wǎng)掩碼是 255.255.255.0 ;主機 B 的 IP 是 192.168.0.2 ,子網(wǎng)掩碼是 255.255.255.0 。所 以，這兩個主機的子網(wǎng)地址都是192.168.0.0 ,它們是可以通信的?，F(xiàn)在給你兩個主機的IP地址與子網(wǎng)掩碼，請判斷一下它們是否屬于同一個子網(wǎng)？輸入IP地址與子網(wǎng)第一行是一個整數(shù) K(10K 10000),表示樣例的個數(shù)。每個樣例占兩行，每行一個主機的 掩碼，使用四段式表示，數(shù)據(jù)保證輸入的IP地址與子網(wǎng)掩碼合法。輸出依次輸出每個樣例的結(jié)果，如果在同一個子網(wǎng)，輸出“Yes；否則

3、輸出“N戌樣例輸入2192.168.0.1 255.255.255.0192.168.0.2 255.255.255.0192.168.0.1 255.255.255.0192.168.1.2 255.255.255.0樣例輸出Yes No（三）最長回文子序列題目描述給一個字符串，任取若干個字符，按照其在字符串中的相對順序，組成的序列，我們稱其為子序列。如果 這個子序列是回文的，我們稱其為回文子序列。求一個字符串最長回文子序列的長度。輸入1000存在多個樣例（樣例數(shù)量不超過100）,每行一個字符串，字符串只包含英文小寫字母，長度不超過輸出每行輸出一個樣例的結(jié)果。樣例輸入abcdaabb aba

4、b abcba樣例輸出123(四)置換給一個置換 P(x ? ), P n (x ? )=x ?,求最小的no比如置換 P=(12 23 34 41 ),P(x 1 ,x 2 ,x 3 ,x 4 )P 2 (x 1 ,x 2 ,x 3 ,x 4 )P 3 (x 1 ,x 2 ,x 3 ,x 4 )P 4 (x 1 ,x 2 ,x 3 ,x 4 ) = (x 4 ,x 1 ,x 2,x 3 )(x 3 ,x 4 ,x 1 ,x 2 )(x 2 ,x 3 ,x 4 ,x 1 )(x 1 ,x 2 ,x 3 ,x 4 )所以n=4 。輸入第一行是一個整數(shù) K(1K 1000),表示樣例的個數(shù)。每個樣

5、例占一行，第一個整數(shù)是n(10n100 ,以后的n個整數(shù)x i ,1 xi n且x i是唯一的，(1x 1 2x 2 ? nx n ) 表示一個置換。輸出輸出一個樣例的結(jié)果。樣例輸入33 1 2 33 2 1 33 2 3 1樣例輸出123(五)20482048是大家非常喜歡的一款小游戲，給定一個 2048的局面，和下一步的指令，請計算出變化后的局面。2048的游戲規(guī)則如下： 游戲是一個4X4的格子 玩家可以使用上、下、左、右控制數(shù)字方格滑動， 每滑動一次，所有的數(shù)字方塊都會往滑動的方向靠攏，相同數(shù)字的方塊在靠攏、相撞時會相加。 不斷的疊加最終拼湊出 2048這個數(shù)字就算成功 每次滑動后，會在

6、某個空白格子中出現(xiàn)隨機的2或者4,如果不存在空白格子，則游戲結(jié)束。輸入第一行是一個整數(shù) K,表示樣例的個數(shù)。每個樣例的前4行，每行4個整數(shù)，如果整數(shù)為 0表示空白格子，其他為數(shù)字。每個樣例的第5行，是指令，指令為LEFT,DOWN,RIGHT,UP, 依次表示滑動的方向。輸出輸出每個樣例的結(jié)果，每個樣例后輸出一個空行。樣例輸入32 2 0 02 0 2 02 0 0 20 0 2 2 LEFT 2 0 2 0 2 2 2 2 0 2 0 2 4 2 2 0 LEFT 2 4 2 2 0 2 2 0 0 4 4 4 0 0 0 2 LEFT樣例輸出4 0 0 04 0 0 04 0 0 04 0

7、 0 04 0 0 04 4 0 04 0 0 04 4 0 02 4 4 04 0 0 08 4 0 0SECOND（一）矩陣題目描述 編寫一個程序，將1n2按行依次填入 nXh的矩陣，執(zhí)行若干條行或者列的循環(huán)移動的指令, 再將數(shù)字按行依次取出。指令如下：指令含義L x y x行循環(huán)左移y次 R x y x行循環(huán)右移y次 U x y x列循環(huán)上移y次 D x y x列循環(huán)下移y次輸入第一行是一個整數(shù) K,表示樣例的個數(shù)。每個樣例的第一行是兩個整數(shù)n（14i司0）和m（1由司000）,分別表示矩陣的大小和指令的條數(shù)。以后的m行是m條指令，矩陣的行列按 1開始計數(shù)，指令滿足 1叔阡1,1或句-1

8、。輸出每行輸出一個樣例的結(jié)果，數(shù)字之間用一個空格隔開，行末無空格。樣例輸入43 1L 1 13 1R 1 13 1U 1 13 1D 1 1樣例輸出3 1 2 4 5 6 7 8 94 2 3 7 5 6 1 8 97 2 3 1 5 6 4 8 9（二）0 和 1題目描述一個01字符串，長度是 n,其中1比0多m個，請問不同的排列方案數(shù)有多少個？輸入第一行是一個整數(shù) K,表示樣例的個數(shù)。以后每行兩個整數(shù)n和m, 1嘀33,0mn o輸出每行輸出一個樣例的結(jié)果。樣例輸入42 02 13 03 1樣例輸出2003線索第一個樣例為01和10;第二、三個樣例不存在這樣的串；第四個樣例為 011,10

9、1,110（三）子申題目描述求一個字符串長度為n的子串中出現(xiàn)次數(shù)最多的字典序最小的子串，及其出現(xiàn)次數(shù)。比如字符串為aaabbb,子串長度為 2時,子串為aa,ab,bb）,分別出現(xiàn)2,1,2次。由于aa的字典序 比bb要小，所以答案為“aa,出現(xiàn)次數(shù)為2。輸入存在多個字符串（個數(shù)不超過100）,每行輸入一個字符串和一個整數(shù)，字符串只含小寫英文字母，長度不超過 2000 o整數(shù)表示子串的長度，值不超過10O輸出每行輸出一個樣例的結(jié)果，先輸出答案子串，再輸出出現(xiàn)次數(shù)，中間用一個空格隔開。樣例輸入aabb 2aaabbb 2aaaaaa 3樣例輸出aa 1aa 2aaa 4（四）素因子的種類題目描述

10、給一個整數(shù)n,求其素因子一共有多少種？比如 30,素因子為2,3,5,所以素因子的種類為 3;比如8,素因子為2,所以種類數(shù)為 1。輸入第一行是一個整數(shù) k（1 4司0000） o以后每行一個整數(shù)n（2q詞0 12 ）輸出每行輸出一個樣例的結(jié)果樣例輸入4269999999999891000000000000樣例輸出（五）考試安排題目描述Eric每次考試最頭痛的就是安排考試時間，需要找合適的空閑時間安排考試真的是件很費神的事情。Eric希望你能幫他算一下能哪些時間可以考試，當然 Eric并不想周末進行考試，所以你只需要 計算周1到周5的時間就可以了。我們假設(shè)每天有 11節(jié)課的時間，上午1到4節(jié)，

11、下午5-8節(jié)， 晚上9-11節(jié)。Eric已經(jīng)拿到了參加考試的班級的課表，以及考試需要的時長。注意：考試只能 安排在上午、下午、晚上時段，不能跨區(qū)間。輸入第一行是一個整數(shù) K（1本司00）,表示樣例的個數(shù) 每個樣例的第一行是兩個整數(shù)N（1小司00）,T（24N）,分別表示這些班級課表的條目數(shù)和考試所需的課程節(jié)數(shù)。為了簡化問題，Eric只留下了課表條目的上課時間。以后的N行，每行一個課程的時間，為三個值，D（D Mon,Tue,WeThur,Fri ,SatSun）, S,E（1與E41）,分別表示上課時間為星期D的第S節(jié)到第E節(jié)。輸出每個樣例先輸出一行，為每個樣例合適考試的不同時間段的個數(shù)。然后

12、按時間先后順序，每行輸出一個時間段，分別為 S,D,E ,中間用一個空格隔開。樣例輸入110 3Mon 1 2Tue 1 2Wen 1 2Thur 1 2Fri 1 2Mon 5 6Tue 5 6Wen 5 6Thur 5 6Fri 5 65Mon 9 11Tue 9 11Wen 9 11Thur 9 11Fri 9 11（六）Beautiful Number題目描述現(xiàn)在如果一個數(shù)的二進制中只有1個0,那么我們稱這樣的數(shù)是美麗數(shù)”，比如5 10 =101 2給你一個區(qū)間a,b（1 名/）司0 18）,求區(qū)間內(nèi)有多少個美麗數(shù)輸入第一行是一個整數(shù) K,表示樣例的個數(shù)。每個樣例是兩個整數(shù)a和b。輸出

13、每行輸出一個樣例的結(jié)果。樣例輸入31 22 51 1000000000000000000樣例輸出121712提示 第一個例子中，只有 2是美麗數(shù);第二個例子中，2和5是美麗數(shù);THIRD（一）Robot題目描述機器人一開始站在原點，可以上下左右（分別用“UDLR表示）移動，每次移動一步。 Estrella想知道對于某個指令序列，如果把某一種指令全部替換成另一種指令，新的指令序列可以讓機器人回到原點。輸入存在多個樣例，每個樣例一行，為一條指令序列，長度不超過200。輸出每行輸出一個樣例的結(jié)果，可以輸出“Yes；否則輸出“Nd：樣例輸入LDLLDDD樣例輸出YesNo（二）染色題目描述Alice在

14、玩一個游戲，她在一個rnX n的格子里，隨機涂黑 k個格子。然后她每次可以把一行或者一列的格子染成紅色，但是這一行中不能有黑色的格子。請問她最多能把多少個格子涂成紅 色？輸入第一行是一個整數(shù) T（TW100）,表示樣例的個數(shù)。每個樣例的第一行是m（1喻w 100n（1語w 100k（0米6Xn）。以后的k行,每行兩個整數(shù) x（1玉5）,y（19巧）， 表示（x,y）為黑色格子。每行輸出一個樣例的結(jié)果樣例輸入13 4 21 13 3樣例輸出8（三）矩陣題目描述我們把1N2按下面矩陣的規(guī)律進行排列：145161736? 236151835 987141934 1011121320332524232

15、22132 262728293031請求第一列的累加和。輸入每行一個整數(shù) N（1第W16）,如果N=0表示輸入結(jié)束，這個樣例不需要處理。輸出每行輸出一個樣例的結(jié)果，因為這個值可能很大，請將其對 1,000,000,007取模。樣例輸入12310000000000樣例輸出1510 499999881(四)集合題目描述對于包含整數(shù)多值集合 A=a i ,a 2 ,? ,an,執(zhí)行以下兩步操作1 .將某些元素加上整數(shù) x2 .將某些元素減掉整數(shù) y請問能否使得A的元素全部相等？輸入第一行是一個整數(shù) K(1 100),表示樣例的個數(shù)。每個樣例的第一行是一個整數(shù)n(1訴W 100,000)第二行是a i

16、 |i=1,2,? n,0 至 i 1,000,000,000,輸出每行輸出一個樣例的結(jié)果，如果可以使得元素全部相等輸出Yes,否則輸出No樣例輸入252 1 2 1 351 2 3 4 5樣例輸出YesNo(五)Colombian Number題目描述對于正整數(shù)n ，不存在整數(shù)k，使得n等于k加上k的數(shù)碼累加和，我們稱這樣的數(shù)是哥倫比 亞數(shù)或者自我數(shù)。比如11就不是一個哥倫比亞數(shù)，因為 10加上10的數(shù)碼累加和1等于11;而20則是一個哥倫 比亞數(shù)。輸入 第一行是一個整數(shù) K（K 10,000）,表示樣例的個數(shù)。以后每行一個正整數(shù) n（1磔1W 1,000,000,000）輸出每行輸出一個樣例的結(jié)果，如果是哥倫比亞數(shù)輸出Yes,否則輸出No樣例輸入51232021樣例輸出YesNoYesYesNo（六）Bonus題目描述要過年了，老板準備發(fā)年終獎，老板準備根據(jù)員工的平時表現(xiàn)對比發(fā)放獎金，最低發(fā)888,每檔再增加1000塊。由于工作表現(xiàn)記錄有點問題，可能存在矛盾的描述，所以，如果無法發(fā)放的話，則所有人，每人發(fā)888元。老板把這個任務交給你，希望你幫他算出一共需要給多少獎金，每人需要發(fā)多少獎金？輸入第一行是一個整數(shù) K,表