CCF CSP認證考試歷年真題_第1頁
CCF CSP認證考試歷年真題_第2頁
CCF CSP認證考試歷年真題_第3頁
CCF CSP認證考試歷年真題_第4頁
CCF CSP認證考試歷年真題_第5頁
已閱讀5頁，還剩42頁未讀， 繼續(xù)免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、 歷年真題 2015年12月7日試題編號：201509-1試題名稱：數(shù)列分段時間限制：1.0s內存限制：256.0MB問題描述：問題描述給定一個整數(shù)數(shù)列，數(shù)列中連續(xù)相同的最長整數(shù)序列算成一段，問數(shù)列中共有多少段？輸入格式輸入的第一行包含一個整數(shù)n，表示數(shù)列中整數(shù)的個數(shù)。第二行包含n個整數(shù)a1, a2, , an，表示給定的數(shù)列，相鄰的整數(shù)之間用一個空格分隔。輸出格式輸出一個整數(shù)，表示給定的數(shù)列有多個段。樣例輸入88 8 8 0 12 12 8 0樣例輸出5樣例說明8 8 8是第一段，0是第二段，12 12是第三段，倒數(shù)第二個整數(shù)8是第四段，最后一個0是第五段。評測用例規(guī)模與約定1 n 1000

2、，0 ai 1000。提交確認：以下必須全部滿足才能提交： 我的程序沒有使用package語句來定義包的信息。（如果定義了將無法評測） 我的程序的主類名稱是Main，主類的定義是public class Main。我的程序運行的入口是主類Main中的main函數(shù)，定義為public static void main(String args)。 我的程序是從標準輸入(System.in)中讀入數(shù)據的（使用Scanner等類來處理System.in的輸入視為滿足條件），結果是輸出到標準輸出(System.out)的。 我的程序中沒有“請輸入n”之類的輸入輸出提示，也沒有輸出中間的結果，所有的輸出內

3、容都與題設中的輸出格式相對應。我的輸出格式（包括換行和大小寫等）與題設中輸出格式的要求相符。 試題編號：201509-2試題名稱：日期計算時間限制：1.0s內存限制：256.0MB問題描述：問題描述給定一個年份y和一個整數(shù)d，問這一年的第d天是幾月幾日？注意閏年的2月有29天。滿足下面條件之一的是閏年：1） 年份是4的整數(shù)倍，而且不是100的整數(shù)倍；2） 年份是400的整數(shù)倍。輸入格式輸入的第一行包含一個整數(shù)y，表示年份，年份在1900到2015之間（包含1900和2015）。輸入的第二行包含一個整數(shù)d，d在1至365之間。輸出格式輸出兩行，每行一個整數(shù)，分別表示答案的月份和日期。樣例輸入20

4、1580樣例輸出321樣例輸入200040樣例輸出29試題編號：201509-3試題名稱：模板生成系統(tǒng)時間限制：1.0s內存限制：256.0MB問題描述：問題描述成成最近在搭建一個網站，其中一些頁面的部分內容來自數(shù)據庫中不同的數(shù)據記錄，但是頁面的基本結構是相同的。例如，對于展示用戶信息的頁面，當用戶為 Tom 時，網頁的源代碼是而當用戶為 Jerry 時，網頁的源代碼是這樣的例子在包含動態(tài)內容的網站中還有很多。為了簡化生成網頁的工作，成成覺得他需要引入一套模板生成系統(tǒng)。模板是包含特殊標記的文本。成成用到的模板只包含一種特殊標記，格式為 VAR ，其中 VAR 是一個變量。該標記在模板生成時會被

5、變量 VAR 的值所替代。例如，如果變量 name = "Tom"，則 name 會生成 Tom。具體的規(guī)則如下：·變量名由大小寫字母、數(shù)字和下劃線 (_) 構成，且第一個字符不是數(shù)字，長度不超過 16 個字符。·變量名是大小寫敏感的，Name 和 name 是兩個不同的變量。·變量的值是字符串。·如果標記中的變量沒有定義，則生成空串，相當于把標記從模板中刪除。·模板不遞歸生成。也就是說，如果變量的值中包含形如 VAR 的內容，不再做進一步的替換。輸入格式輸入的第一行包含兩個整數(shù) m, n，分別表示模板的行數(shù)和模板生成時給出

6、的變量個數(shù)。接下來 m 行，每行是一個字符串，表示模板。接下來 n 行，每行表示一個變量和它的值，中間用一個空格分隔。值是字符串，用雙引號 (") 括起來，內容可包含除雙引號以外的任意可打印 ASCII 字符（ASCII 碼范圍 32, 33, 35-126）。輸出格式輸出包含若干行，表示模板生成的結果。樣例輸入11 2<!DOCTYPE html><html><head><title>User name </title></head><body><h1> name </h1>

7、<p>Email: <a href="mailto: email "> email </a></p><p>Address: address </p></body></html>name "David Beckham"email "david"樣例輸出<!DOCTYPE html><html><head><title>User David Beckham</title></he

8、ad><body><h1>David Beckham</h1><p>Email: <a href="mailto:david">david</a></p><p>Address: </p></body></html>評測用例規(guī)模與約定0 m 1000 n 100輸入的模板每行長度不超過 80 個字符（不包含換行符）。輸入保證模板中所有以 開始的子串都是合法的標記，開始是兩個左大括號和一個空格，然后是變量名，結尾是一個空格和兩個右大括號。輸入

9、中所有變量的值字符串長度不超過 100 個字符（不包括雙引號）。保證輸入的所有變量的名字各不相同。試題編號：201509-4試題名稱：高速公路時間限制：1.0s內存限制：256.0MB問題描述：問題描述某國有n個城市，為了使得城市間的交通更便利，該國國王打算在城市之間修一些高速公路，由于經費限制，國王打算第一階段先在部分城市之間修一些單向的高速公路?，F(xiàn)在，大臣們幫國王擬了一個修高速公路的計劃?？戳擞媱澓?，國王發(fā)現(xiàn)，有些城市之間可以通過高速公路直接（不經過其他城市）或間接（經過一個或多個其 他城市）到達，而有的卻不能。如果城市A可以通過高速公路到達城市B，而且城市B也可以通過高速公路到達城市A，

10、則這兩個城市被稱為便利城市對。國王想知道，在大臣們給他的計劃中，有多少個便利城市對。輸入格式輸入的第一行包含兩個整數(shù)n, m，分別表示城市和單向高速公路的數(shù)量。接下來m行，每行兩個整數(shù)a, b，表示城市a有一條單向的高速公路連向城市b。輸出格式輸出一行，包含一個整數(shù)，表示便利城市對的數(shù)量。樣例輸入5 51 22 33 44 23 5樣例輸出3樣例說明城市間的連接如圖所示。有3個便利城市對，它們分別是(2, 3), (2, 4), (3, 4)，請注意(2, 3)和(3, 2)看成同一個便利城市對。評測用例規(guī)模與約定前30%的評測用例滿足1 n 100, 1 m 1000；前60%的評測用例滿足

11、1 n 1000, 1 m 10000；所有評測用例滿足1 n 10000, 1 m 100000。試題編號：201509-5試題名稱：最佳文章時間限制：1.0s內存限制：256.0MB問題描述：問題描述小明最近在研究一門新的語言，叫做Q語言。Q語言單詞和文章都可以用且僅用只含有小寫英文字母的字符串表示，任何由這些字母組成的字符串也都是一篇合法的Q語言文章。在Q語言的所有單詞中，小明選出了他認為最重要的n個。使用這些單詞，小明可以評價一篇Q語言文章的“重要度”。文章“重要度”的定義為：在該文章中，所有重要的Q語言單詞出現(xiàn)次數(shù)的總和。其中多次出現(xiàn)的單詞，不論是否發(fā)生包含、重疊等情況，每次出現(xiàn)均計

12、算在內。例如，假設n = 2，小明選出的單詞是gvagv和agva。在文章gvagvagvagv中，gvagv出現(xiàn)了3次，agva出現(xiàn)了2次，因此這篇文章的重要度為3+2=5?，F(xiàn)在，小明想知道，一篇由m個字母組成的Q語言文章，重要度最高能達到多少。輸入格式輸入的第一行包含兩個整數(shù)n, m，表示小明選出的單詞個數(shù)和最終文章包含的字母個數(shù)。接下來n行，每行包含一個僅由英文小寫字母構成的字符串，表示小明選出的這n個單詞。輸出格式輸出一行一個整數(shù)，表示由m個字母組成的Q語言文章中，重要度最高的文章的重要度。樣例輸入3 15agvaagvagvagvagva樣例輸出11樣例說明15個字母組成的重要度最高

13、的文章為gvagvagvagvagva。在這篇文章中，agva出現(xiàn)4次，agvagva出現(xiàn)3次，gvagva出現(xiàn)4次，共計4+3+4=11次。評測用例規(guī)模與約定在評測時將使用10個評測用例對你的程序進行評測。設s為構成n個重要單詞字母的總個數(shù)，例如在樣例中，s=4+7+6=17；a為構成n個重要單詞字母的種類數(shù)，例如在樣例中，共有3中字母'a','g','v'，因此a=3。評測用例1和2滿足2 n 3，1500 m 2000，s = 40；評測用例3和4滿足m = 20，2 a 3；評測用例5、6和7滿足2000 m 100000；評測用例8滿足

14、n = 2；所有的評測用例滿足1 s 100，1 m 1015，每個單詞至少包含1個字母，保證單詞中僅出現(xiàn)英文小寫字母，輸入中不含多余字符，不會出現(xiàn)重復的單詞。試題編號：201503-1試題名稱：圖像旋轉時間限制：5.0s內存限制：256.0MB問題描述：問題描述旋轉是圖像處理的基本操作，在這個問題中，你需要將一個圖像逆時針旋轉90度。計算機中的圖像表示可以用一個矩陣來表示，為了旋轉一個圖像，只需要將對應的矩陣旋轉即可。輸入格式輸入的第一行包含兩個整數(shù)n, m，分別表示圖像矩陣的行數(shù)和列數(shù)。接下來n行每行包含m個整數(shù)，表示輸入的圖像。輸出格式輸出m行，每行包含n個整數(shù)，表示原始矩陣逆時針旋轉9

15、0度后的矩陣。樣例輸入2 31 5 33 2 4樣例輸出3 45 21 3評測用例規(guī)模與約定1 n, m 1,000，矩陣中的數(shù)都是不超過1000的非負整數(shù)。試題編號：201503-2試題名稱：數(shù)字排序時間限制：1.0s內存限制：256.0MB問題描述：問題描述給定n個整數(shù)，請統(tǒng)計出每個整數(shù)出現(xiàn)的次數(shù)，按出現(xiàn)次數(shù)從多到少的順序輸出。輸入格式輸入的第一行包含一個整數(shù)n，表示給定數(shù)字的個數(shù)。第二行包含n個整數(shù)，相鄰的整數(shù)之間用一個空格分隔，表示所給定的整數(shù)。輸出格式輸出多行，每行包含兩個整數(shù)，分別表示一個給定的整數(shù)和它出現(xiàn)的次數(shù)。按出現(xiàn)次數(shù)遞減的順序輸出。如果兩個整數(shù)出現(xiàn)的次數(shù)一樣多，則先輸出值較

16、小的，然后輸出值較大的。樣例輸入125 2 3 3 1 3 4 2 5 2 3 5樣例輸出3 42 35 31 14 1評測用例規(guī)模與約定1 n 1000，給出的數(shù)都是不超過1000的非負整數(shù)。試題編號：201503-3試題名稱：節(jié)日時間限制：1.0s內存限制：256.0MB問題描述：問題描述有一類節(jié)日的日期并不是固定的，而是以“a月的第b個星期c”的形式定下來的，比如說母親節(jié)就定為每年的五月的第二個星期日。現(xiàn)在，給你a，b，c和y1, y2(1850 y1, y2 2050)，希望你輸出從公元y1年到公元y2年間的每年的a月的第b個星期c的日期。提示：關于閏年的規(guī)則：年份是400的整數(shù)倍時是

17、閏年，否則年份是4的倍數(shù)并且不是100的倍數(shù)時是閏年，其他年份都不是閏年。例如1900年就不是閏年，而2000年是閏年。為了方便你推算，已知1850年1月1日是星期二。輸入格式輸入包含恰好一行，有五個整數(shù)a, b, c, y1, y2。其中c=1, 2, , 6, 7分別表示星期一、二、六、日。輸出格式對于y1和y2之間的每一個年份，包括y1和y2，按照年份從小到大的順序輸出一行。如果該年的a月第b個星期c確實存在，則以"yyyy/mm/dd"的格式輸出，即輸出四位數(shù)的年份，兩位數(shù)的月份，兩位數(shù)的日期，中間用斜杠“/”分隔，位數(shù)不足時前補零。如果該年的a月第b個星期c并不存

18、在，則輸出"none"（不包含雙引號)。樣例輸入5 2 7 2014 2015樣例輸出2014/05/112015/05/10評測用例規(guī)模與約定所有評測用例都滿足：1 a 12，1 b 5，1 c 7，1850 y1, y2 2050。試題編號：201503-4試題名稱：網絡延時時間限制：1.0s內存限制：256.0MB問題描述：問題描述 給定一個公司的網絡，由n臺交換機和m臺終端電腦組成，交換機與交換機、交換機與電腦之間使用網絡連接。交換機按層級設置，編號為1的交換機為根交換 機，層級為1。其他的交換機都連接到一臺比自己上一層的交換機上，其層級為對應交換機的層級加1。所有

19、的終端電腦都直接連接到交換機上。當信息在電腦、交換機之間傳遞時，每一步只能通過自己傳遞到自己所連接的另一臺電腦或交換機。請問，電腦與電腦之間傳遞消息、或者電腦與交換機之間傳遞消息、或者交換機與交換機之間傳遞消息最多需要多少步。輸入格式輸入的第一行包含兩個整數(shù)n, m，分別表示交換機的臺數(shù)和終端電腦的臺數(shù)。第二行包含n - 1個整數(shù)，分別表示第2、3、n臺交換機所連接的比自己上一層的交換機的編號。第i臺交換機所連接的上一層的交換機編號一定比自己的編號小。第三行包含m個整數(shù)，分別表示第1、2、m臺終端電腦所連接的交換機的編號。輸出格式輸出一個整數(shù)，表示消息傳遞最多需要的步數(shù)。樣例輸入4 21 1

20、32 1樣例輸出4樣例說明樣例的網絡連接模式如下，其中圓圈表示交換機，方框表示電腦：其中電腦1與交換機4之間的消息傳遞花費的時間最長，為4個單位時間。樣例輸入4 41 2 23 4 4 4樣例輸出4樣例說明樣例的網絡連接模式如下：其中電腦1與電腦4之間的消息傳遞花費的時間最長，為4個單位時間。評測用例規(guī)模與約定前30%的評測用例滿足：n 5, m 5。前50%的評測用例滿足：n 20, m 20。前70%的評測用例滿足：n 100, m 100。所有評測用例都滿足：1 n 10000，1 m 10000。試題編號：201503-5試題名稱：最小花費時間限制：4.0s內存限制：256.0MB問題

21、描述：問題描述C國共有n個城市。有n-1條雙向道路，每條道路連接兩個城市，任意兩個城市之間能互相到達。小R來到C國旅行，他共規(guī)劃了m條旅行的路線，第i條旅行路線的起點是si，終點是ti。在旅行過程中，小R每行走一單位長度的路需要吃一單位的食物。C國的食物只能在各個城市中買到，而且不同城市的食物價格可能不同。然而，小R不希望在旅行中為了購買較低價的糧食而繞遠路，因此他總會選擇最近的路走?，F(xiàn)在，請你計算小R規(guī)劃的每條旅行路線的最小花費是多少。輸入格式第一行包含2個整數(shù)n和m。第二行包含n個整數(shù)。第i個整數(shù)wi表示城市i的食物價格。接下來n-1行，每行包括3個整數(shù)u, v, e，表示城市u和城市v之

22、間有一條長為e的雙向道路。接下來m行，每行包含2個整數(shù)si和ti，分別表示一條旅行路線的起點和終點。輸出格式輸出m行，分別代表每一條旅行方案的最小花費。樣例輸入6 41 7 3 2 5 61 2 41 3 52 4 13 5 23 6 12 54 66 45 6樣例輸出35162613樣例說明對于第一條路線，小R會經過2->1->3->5。其中在城市2處以7的價格購買4單位糧食，到城市1時全部吃完，并用1的價格購買7單位糧食，然后到達終點。評測用例規(guī)模與約定前10%的評測用例滿足：n, m 20, wi 20；前30%的評測用例滿足：n, m 200；另有40%的評測用例滿足

23、：一個城市至多與其它兩個城市相連。所有評測用例都滿足：1 n, m 105，1 wi 106，1 e 10000。試題編號：201412-1試題名稱：門禁系統(tǒng)時間限制：1.0s內存限制：256.0MB問題描述：問題描述濤濤最近要負責圖書館的管理工作，需要記錄下每天讀者的到訪情況。每位讀者有一個編號，每條記錄用讀者的編號來表示。給出讀者的來訪記錄，請問每一條記錄中的讀者是第幾次出現(xiàn)。輸入格式輸入的第一行包含一個整數(shù)n，表示濤濤的記錄條數(shù)。第二行包含n個整數(shù)，依次表示濤濤的記錄中每位讀者的編號。輸出格式輸出一行，包含n個整數(shù)，由空格分隔，依次表示每條記錄中的讀者編號是第幾次出現(xiàn)。樣例輸入51 2

24、1 1 3樣例輸出1 1 2 3 1評測用例規(guī)模與約定1n1,000，讀者的編號為不超過n的正整數(shù)。試題編號：201412-2試題名稱：Z字形掃描時間限制：2.0s內存限制：256.0MB問題描述：問題描述在圖像編碼的算法中，需要將一個給定的方形矩陣進行Z字形掃描(Zigzag Scan)。給定一個n×n的矩陣，Z字形掃描的過程如下圖所示：對于下面的4×4的矩陣，1 5 3 93 7 5 69 4 6 47 3 1 3對其進行Z字形掃描后得到長度為16的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3請實現(xiàn)一個Z字形掃描的程序，給定一個n×n的

25、矩陣，輸出對這個矩陣進行Z字形掃描的結果。輸入格式輸入的第一行包含一個整數(shù)n，表示矩陣的大小。輸入的第二行到第n+1行每行包含n個正整數(shù)，由空格分隔，表示給定的矩陣。輸出格式輸出一行，包含n×n個整數(shù)，由空格分隔，表示輸入的矩陣經過Z字形掃描后的結果。樣例輸入41 5 3 93 7 5 69 4 6 47 3 1 3樣例輸出1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3評測用例規(guī)模與約定1n500，矩陣元素為不超過1000的正整數(shù)。試題編號：201412-3試題名稱：集合競價時間限制：1.0s內存限制：256.0MB問題描述：問題描述某股票交易所請你編寫一個程序，根據

26、開盤前客戶提交的訂單來確定某特定股票的開盤價和開盤成交量。該程序的輸入由很多行構成，每一行為一條記錄，記錄可能有以下幾種：1. buy p s 表示一個購買股票的買單，每手出價為p，購買股數(shù)為s。2. sell p s 表示一個出售股票的賣單，每手出價為p，出售股數(shù)為s。3. cancel i表示撤銷第i行的記錄。如果開盤價為p0，則系統(tǒng)可以將所有出價至少為p0的買單和所有出價至多為p0的賣單進行匹配。因此，此時的開盤成交量為出價至少為p0的買單的總股數(shù)和所有出價至多為p0的賣單的總股數(shù)之間的較小值。你的程序需要確定一個開盤價，使得開盤成交量盡可能地大。如果有多個符合條件的開盤價，你的程序應當

27、輸出最高的那一個。輸入格式輸入數(shù)據有任意多行，每一行是一條記錄。保證輸入合法。股數(shù)為不超過108的正整數(shù)，出價為精確到恰好小數(shù)點后兩位的正實數(shù)，且不超過10000.00。輸出格式你需要輸出一行，包含兩個數(shù)，以一個空格分隔。第一個數(shù)是開盤價，第二個是此開盤價下的成交量。開盤價需要精確到小數(shù)點后恰好兩位。樣例輸入buy 9.25 100buy 8.88 175sell 9.00 1000buy 9.00 400sell 8.92 400cancel 1buy 100.00 50樣例輸出9.00 450評測用例規(guī)模與約定對于100%的數(shù)據，輸入的行數(shù)不超過5000。試題編號：201412-4試題名稱

28、：最優(yōu)灌溉時間限制：1.0s內存限制：256.0MB問題描述：問題描述雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個麥田挖了一口很深的水井，所有的麥田都從這口井來引水灌溉。為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉站”，利用水渠連接不同的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉。現(xiàn)在雷雷知道哪些麥田之間可以建設水渠和建設每個水渠所需要的費用（注意不是所有麥田之間都可以建立水渠）。請問灌溉所有麥田最少需要多少費用來修建水渠。輸入格式輸入的第一行包含兩個正整數(shù)n, m，分別表示麥田的片數(shù)和雷雷可以建立的水渠的數(shù)量。麥田使用1, 2,

29、3, 依次標號。接下來m行，每行包含三個整數(shù)ai, bi, ci，表示第ai片麥田與第bi片麥田之間可以建立一條水渠，所需要的費用為ci。輸出格式輸出一行，包含一個整數(shù)，表示灌溉所有麥田所需要的最小費用。樣例輸入4 41 2 12 3 42 4 23 4 3樣例輸出6樣例說明建立以下三條水渠：麥田1與麥田2、麥田2與麥田4、麥田4與麥田3。評測用例規(guī)模與約定前20%的評測用例滿足：n5。前40%的評測用例滿足：n20。前60%的評測用例滿足：n100。所有評測用例都滿足：1n1000，1m100,000，1ci10,000。試題編號：201412-5試題名稱：貨物調度時間限制：1.0s內存限制

30、：256.0MB問題描述：問題描述某公司要處理一個周期性的物流問題。有n個城市，第i個城市在每周的第j(1j7) 天會生產aij噸某種貨物，同時需要消耗bij噸該種貨物。已知每周的產量等于消耗量（即aij之和等于bij之和）。城市之間有m條道路，第k條道路連接了城市sk和tk。一條道路上運輸1噸貨物有一個固定的成本ck。道路都可以雙向使用。每天運輸?shù)呢浳锪繘]有限制。城市之間的距離并不遠，貨物可以從任意一個城市運輸?shù)饺我饬硪粋€城市并且在當天到達。貨物如果在當天沒有被消耗掉，就需要存放在倉庫里過夜。第i個城市的倉庫容量為vi，存放1 噸貨物過一夜所需的成本是wi。請你計算該公司如果每周循環(huán)性地按照

31、一個固定的流程調度貨物的話，該公司在最優(yōu)方案下每周需要為貨物的運輸和存儲消耗多少成本。輸入格式輸入的第一行有兩個正整數(shù)n和m，即城市的個數(shù)和道路的條數(shù)。接下來有n行，每行包含16個整數(shù)，用以描述第i個城市的相關數(shù)據。其中第i行包含的數(shù)為ai1, ai2, ai3, ai4, ai5, ai6, ai7, bi1, bi2, bi3, bi4, bi5, bi6, bi7, vi, wi。接下來有m行，每行包含3個整數(shù)，用以描述一條道路的相關數(shù)據。其中第k行包含的數(shù)為sk, tk和ck。輸入數(shù)據中城市的編號均為1到n之間。輸入數(shù)據的每行的行首行尾均保證沒有空格，兩個數(shù)之間恰好被一個空格隔開。輸出

32、格式你只需要輸出一個數(shù)，即最優(yōu)方案下每周的支出。樣例輸入3 30 0 0 0 5 0 0 0 0 0 0 0 0 0 2 40 0 0 0 0 0 0 2 0 0 0 0 0 0 2 10 0 0 0 0 0 0 0 0 3 0 0 0 0 2 51 2 11 3 52 3 1樣例輸出67樣例說明城市1 每周五生產5 噸貨物，把其中2 噸運到存儲費用低廉的城市2 存儲，把1 噸運到城市3 存儲，剩下的2 噸留在城市1。在次周一的時候城市2 會消耗掉存放在那里的2 噸貨物。為了節(jié)約存儲成本，將囤放在城市1 的貨物運到城市2 存放。周三再將所有貨物運到城市3 以滿足該城市的需求。在此方案下，每周的

33、運輸成本為8，每周的存儲成本為59，因此每周的總支出為67。評測用例規(guī)模與約定對于100%的數(shù)據，1n100，1m500，0aij,bij,vi100，1wi,ck100。試題編號：201409-1試題名稱：相鄰數(shù)對時間限制：1.0s內存限制：256.0MB問題描述：問題描述給定n個不同的整數(shù)，問這些數(shù)中有多少對整數(shù)，它們的值正好相差1。輸入格式輸入的第一行包含一個整數(shù)n，表示給定整數(shù)的個數(shù)。第二行包含所給定的n個整數(shù)。輸出格式輸出一個整數(shù)，表示值正好相差1的數(shù)對的個數(shù)。樣例輸入610 2 6 3 7 8樣例輸出3樣例說明值正好相差1的數(shù)對包括(2, 3), (6, 7), (7, 8)。評測

34、用例規(guī)模與約定1<=n<=1000，給定的整數(shù)為不超過10000的非負整數(shù)。試題編號：201409-2試題名稱：畫圖時間限制：1.0s內存限制：256.0MB問題描述：問題描述在一個定義了直角坐標系的紙上，畫一個(x1,y1)到(x2,y2)的矩形指將橫坐標范圍從x1到x2，縱坐標范圍從y1到y(tǒng)2之間的區(qū)域涂上顏色。下圖給出了一個畫了兩個矩形的例子。第一個矩形是(1,1) 到(4, 4)，用綠色和紫色表示。第二個矩形是(2, 3)到(6, 5)，用藍色和紫色表示。圖中，一共有15個單位的面積被涂上顏色，其中紫色部分被涂了兩次，但在計算面積時只計算一次。在實際的涂色過程中，所有的矩形

35、 都涂成統(tǒng)一的顏色，圖中顯示不同顏色僅為說明方便。給出所有要畫的矩形，請問總共有多少個單位的面積被涂上顏色。輸入格式輸入的第一行包含一個整數(shù)n，表示要畫的矩形的個數(shù)。接下來n行，每行4個非負整數(shù)，分別表示要畫的矩形的左下角的橫坐標與縱坐標，以及右上角的橫坐標與縱坐標。輸出格式輸出一個整數(shù)，表示有多少個單位的面積被涂上顏色。樣例輸入21 1 4 42 3 6 5樣例輸出15評測用例規(guī)模與約定1<=n<=100，0<=橫坐標、縱坐標<=100。試題編號：201409-3試題名稱：字符串匹配時間限制：1.0s內存限制：256.0MB問題描述：問題描述給出一個字符串和多行文字，

36、在這些文字中找到字符串出現(xiàn)的那些行。你的程序還需支持大小寫敏感選項：當選項打開時，表示同一個字母的大寫和小寫看作不同的字符；當選項關閉時，表示同一個字母的大寫和小寫看作相同的字符。輸入格式輸入的第一行包含一個字符串S，由大小寫英文字母組成。第二行包含一個數(shù)字，表示大小寫敏感的選項，當數(shù)字為0時表示大小寫不敏感，當數(shù)字為1時表示大小寫敏感。第三行包含一個整數(shù)n，表示給出的文字的行數(shù)。接下來n行，每行包含一個字符串，字符串由大小寫英文字母組成，不含空格和其他字符。輸出格式輸出多行，每行包含一個字符串，按出現(xiàn)的順序依次給出那些包含了字符串S的行。樣例輸入Hello15HelloWorldHiHiHe

37、lloHiHiGrepIsAGreatToolHELLOHELLOisNOTHello樣例輸出HelloWorldHiHiHelloHiHiHELLOisNOTHello樣例說明在上面的樣例中，第四個字符串雖然也是Hello，但是大小寫不正確。如果將輸入的第二行改為0，則第四個字符串應該輸出。評測用例規(guī)模與約定1<=n<=100，每個字符串的長度不超過100。試題編號：201409-4試題名稱：最優(yōu)配餐時間限制：1.0s內存限制：256.0MB問題描述：問題描述棟棟最近開了一家餐飲連鎖店，提供外賣服務。隨著連鎖店越來越多，怎么合理的給客戶送餐成為了一個急需解決的問題。棟棟的連鎖店所

38、在的區(qū)域可以看成是一個n×n的方格圖（如下圖所示），方格的格點上的位置上可能包含棟棟的分店（綠色標注）或者客戶（藍色標注），有一些格點是不能經過的（紅色標注）。方格圖中的線表示可以行走的道路，相鄰兩個格點的距離為1。棟棟要送餐必須走可以行走的道路，而且不能經過紅色標注的點。送餐的主要成本體現(xiàn)在路上所花的時間，每一份餐每走一個單位的距離需要花費1塊錢。每個客戶的需求都可以由棟棟的任意分店配送，每個分店沒有配送總量的限制?，F(xiàn)在你得到了棟棟的客戶的需求，請問在最優(yōu)的送餐方式下，送這些餐需要花費多大的成本。輸入格式輸入的第一行包含四個整數(shù)n, m, k, d，分別表示方格圖的大小、棟棟的分店

39、數(shù)量、客戶的數(shù)量，以及不能經過的點的數(shù)量。接下來m行，每行兩個整數(shù)xi, yi，表示棟棟的一個分店在方格圖中的橫坐標和縱坐標。接下來k行，每行三個整數(shù)xi, yi, ci，分別表示每個客戶在方格圖中的橫坐標、縱坐標和訂餐的量。（注意，可能有多個客戶在方格圖中的同一個位置）接下來d行，每行兩個整數(shù)，分別表示每個不能經過的點的橫坐標和縱坐標。輸出格式輸出一個整數(shù)，表示最優(yōu)送餐方式下所需要花費的成本。樣例輸入10 2 3 31 18 81 5 12 3 36 7 21 22 26 8樣例輸出29評測用例規(guī)模與約定前30%的評測用例滿足：1<=n <=20。前60%的評測用例滿足：1<

40、;=n<=100。所有評測用例都滿足：1<=n<=1000，1<=m, k, d<=n2?？赡苡卸鄠€客戶在同一個格點上。每個客戶的訂餐量不超過1000，每個客戶所需要的餐都能被送到。試題編號：201409-5試題名稱：拼圖時間限制：3.0s內存限制：256.0MB問題描述：問題描述給出一個n×m的方格圖，現(xiàn)在要用如下L型的積木拼到這個圖中，使得方格圖正好被拼滿，請問總共有多少種拼法。其中，方格圖的每一個方格正好能放積木中的一塊。積木可以任意旋轉。輸入格式輸入的第一行包含兩個整數(shù)n, m，表示方格圖的大小。輸出格式輸出一行，表示可以放的方案數(shù)，由于方案數(shù)可

41、能很多，所以請輸出方案數(shù)除以1,000,000,007的余數(shù)。樣例輸入6 2樣例輸出4樣例說明四種拼法如下圖所示：評測用例規(guī)模與約定在評測時將使用10個評測用例對你的程序進行評測。評測用例1和2滿足：1<=n<=30，m=2。評測用例3和4滿足：1<=n, m<=6。評測用例5滿足：1<=n<=100，1<=m<=6。評測用例6和7滿足：1<=n<=1000，1<=m<=6。評測用例8、9和10滿足：1<=n<=1015，1<=m<=7。試題編號：201403-1試題名稱：相反數(shù)時間限制：1.0s內

42、存限制：256.0MB問題描述：問題描述有 N 個非零且各不相同的整數(shù)。請你編一個程序求出它們中有多少對相反數(shù)(a 和 -a 為一對相反數(shù))。輸入格式第一行包含一個正整數(shù) N。(1 N 500)。第二行為 N 個用單個空格隔開的非零整數(shù),每個數(shù)的絕對值不超過1000,保證這些整數(shù)各不相同。輸出格式只輸出一個整數(shù),即這 N 個數(shù)中包含多少對相反數(shù)。樣例輸入51 2 3 -1 -2樣例輸出2試題編號：201403-2試題名稱：窗口時間限制：1.0s內存限制：256.0MB問題描述：問題描述在某圖形操作系統(tǒng)中,有 N 個窗口,每個窗口都是一個兩邊與坐標軸分別平行的矩形區(qū)域。窗口的邊界上的點也屬于該窗

43、口。窗口之間有層次的區(qū)別,在多于一個窗口重疊的區(qū)域里,只會顯示位于頂層的窗口里的內容。當你點擊屏幕上一個點的時候,你就選擇了處于被點擊位置的最頂層窗口,并且這個窗口就會被移到所有窗口的最頂層,而剩余的窗口的層次順序不變。如果你點擊的位置不屬于任何窗口,則系統(tǒng)會忽略你這次點擊?，F(xiàn)在我們希望你寫一個程序模擬點擊窗口的過程。輸入格式輸入的第一行有兩個正整數(shù),即 N 和 M。(1 N 10,1 M 10)接下來 N 行按照從最下層到最頂層的順序給出 N 個窗口的位置。 每行包含四個非負整數(shù) x1, y1, x2, y2,表示該窗口的一對頂點坐標分別為 (x1, y1) 和 (x2, y2)。保證 x1

44、 < x2,y1 2。接下來 M 行每行包含兩個非負整數(shù) x, y,表示一次鼠標點擊的坐標。題目中涉及到的所有點和矩形的頂點的 x, y 坐標分別不超過 2559 和1439。輸出格式輸出包括 M 行,每一行表示一次鼠標點擊的結果。如果該次鼠標點擊選擇了一個窗口,則輸出這個窗口的編號(窗口按照輸入中的順序從 1 編號到 N);如果沒有,則輸出"IGNORED"(不含雙引號)。樣例輸入3 40 0 4 41 1 5 52 2 6 61 10 04 40 5樣例輸出211IGNORED樣例說明第一次點擊的位置同時屬于第 1 和第 2 個窗口,但是由于第 2 個窗口在上面,

45、它被選擇并且被置于頂層。第二次點擊的位置只屬于第 1 個窗口,因此該次點擊選擇了此窗口并將其置于頂層?，F(xiàn)在的三個窗口的層次關系與初始狀態(tài)恰好相反了。第三次點擊的位置同時屬于三個窗口的范圍,但是由于現(xiàn)在第 1 個窗口處于頂層,它被選擇。最后點擊的 (0, 5) 不屬于任何窗口。試題編號：201403-3試題名稱：命令行選項時間限制：1.0s內存限制：256.0MB問題描述：問題描述 請你寫一個命令行分析程序,用以分析給定的命令行里包含哪些選項。每個命令行由若干個字符串組成,它們之間恰好由一個空格分隔。這些字符串中的第一個為 該命令行工具的名字,由小寫字母組成,你的程序不用對它進行處理。在工具名字

46、之后可能會包含若干選項,然后可能會包含一 些不是選項的參數(shù)。選項有兩類:帶參數(shù)的選項和不帶參數(shù)的選項。一個合法的無參數(shù)選項的形式是一個減號后面跟單個小寫字母,如"-a" 或"-b"。而帶參數(shù)選項則由兩個由空格分隔的字符串構成,前者的格式要求與無參數(shù)選項相同,后者則是該選項的參數(shù),是由小寫字母,數(shù)字和減號組成的非空 字符串。該命令行工具的作者提供給你一個格式字符串以指定他的命令行工具需要接受哪些選項。這個字符串由若干小寫字母和冒號組成,其中的每個小寫字母表示一個 該程序接受的選項。如果該小寫字母后面緊跟了一個冒號,它就表示一個帶參數(shù)的選項,否則則為不帶參數(shù)

47、的選項。例如, "ab:m:" 表示該程序接受三種選項,即"-a"(不帶參數(shù)),"-b"(帶參數(shù)), 以及"-m"(帶參數(shù))。命令行工具的作者準備了若干條命令行用以測試你的程序。對于每個命令行,你的工具應當一直向后分析。當你的工具遇到某個字符串既不是合法的選項,又不是某個合法選項的參數(shù)時,分析就停止。命令行剩余的未分析部分不構成該命令的選項,因此你的程序應當忽略它們。輸入格式輸入的第一行是一個格式字符串,它至少包含一個字符,且長度不超過 52。格式字符串只包含小寫字母和冒號,保證每個小寫字母至多出現(xiàn)一次,不會有兩個

48、相鄰的冒號,也不會以冒號開頭。輸入的第二行是一個正整數(shù) N(1 N 20),表示你需要處理的命令行的個數(shù)。接下來有 N 行,每行是一個待處理的命令行,它包括不超過 256 個字符。該命令行一定是若干個由單個空格分隔的字符串構成,每個字符串里只包含小寫字母,數(shù)字和減號。輸出格式 輸出有 N 行。其中第 i 行以"Case i:" 開始,然后應當有恰好一個空格,然后應當按照字母升序輸出該命令行中用到的所有選項的名稱,對于帶參數(shù)的選項,在輸出它的名稱之后還要輸出它的參數(shù)。如果 一個選項在命令行中出現(xiàn)了多次,只輸出一次。如果一個帶參數(shù)的選項在命令行中出 現(xiàn)了多次,只輸出最后一次出現(xiàn)

49、時所帶的參數(shù)。樣例輸入albw:x4ls -a -l -a documents -blsls -w 10 -x -w 15ls -a -b -c -d -e -l樣例輸出Case 1: -a -lCase 2:Case 3: -w 15 -xCase 4: -a -b試題編號：201403-4試題名稱：無線網絡時間限制：1.0s內存限制：256.0MB問題描述：問題描述目前在一個很大的平面房間里有 n 個無線路由器,每個無線路由器都固定在某個點上。任何兩個無線路由器只要距離不超過 r 就能互相建立網絡連接。除此以外,另有 m 個可以擺放無線路由器的位置。你可以在這些位置中選擇至多 k 個增設新

50、的路由器。你的目標是使得第 1 個路由器和第 2 個路由器之間的網絡連接經過盡量少的中轉路由器。請問在最優(yōu)方案下中轉路由器的最少個數(shù)是多少?輸入格式第一行包含四個正整數(shù) n,m,k,r。(2 n 100,1 k m 100, 1 r 108)。接下來 n 行,每行包含兩個整數(shù) xi 和 yi,表示一個已經放置好的無線 路由器在 (xi, yi) 點處。輸入數(shù)據保證第 1 和第 2 個路由器在僅有這 n 個路由器的情況下已經可以互相連接(經過一系列的中轉路由器)。接下來 m 行,每行包含兩個整數(shù) xi 和 yi,表示 (xi, yi) 點處可以增設 一個路由器。輸入中所有的坐標的絕對值不超過 1

51、08,保證輸入中的坐標各不相同。輸出格式輸出只有一個數(shù),即在指定的位置中增設 k 個路由器后,從第 1 個路 由器到第 2 個路由器最少經過的中轉路由器的個數(shù)。樣例輸入5 3 1 30 05 50 30 53 53 34 43 0樣例輸出2試題編號：201403-5試題名稱：任務調度時間限制：1.0s內存限制：256.0MB問題描述：問題描述有若干個任務需要在一臺機器上運行。它們之間沒有依賴關系,因此 可以被按照任意順序執(zhí)行。該機器有兩個 CPU 和一個 GPU。對于每個任務,你可以為它分配不 同的硬件資源:1. 在單個 CPU 上運行。2. 在兩個 CPU 上同時運行。3. 在單個 CPU

52、和 GPU 上同時運行。4. 在兩個 CPU 和 GPU 上同時運行。一個任務開始執(zhí)行以后,將會獨占它所用到的所有硬件資源,不得中 斷,直到執(zhí)行結束為止。第 i 個任務用單個 CPU,兩個 CPU,單個 CPU 加 GPU,兩個 CPU 加 GPU 運行所消耗的時間分別為 ai,bi,ci 和 di?，F(xiàn)在需要你計算出至少需要花多少時間可以把所有給定的任務完成。輸入格式輸入的第一行只有一個正整數(shù) n(1 n 40), 是總共需要執(zhí)行的任 務個數(shù)。接下來的 n 行每行有四個正整數(shù) ai, bi, ci, di(ai, bi, ci, di 均不超過 10), 以空格隔開。輸出格式輸出只有一個整數(shù),

53、即完成給定的所有任務所需的最少時間。樣例輸入34 4 2 27 4 7 43 3 3 3樣例輸出7樣例說明有很多種調度方案可以在 7 個時間單位里完成給定的三個任務,以下是其中的一種方案:同時運行第一個任務(單 CPU 加上 GPU)和第三個任務(單 CPU), 它們分別在時刻 2 和時刻 3 完成。在時刻 3 開始雙 CPU 運行任務 2,在 時刻 7 完成。試題編號：201312-1試題名稱：出現(xiàn)次數(shù)最多的數(shù)時間限制：1.0s內存限制：256.0MB問題描述：問題描述給定n個正整數(shù)，找出它們中出現(xiàn)次數(shù)最多的數(shù)。如果這樣的數(shù)有多個，請輸出其中最小的一個。輸入格式輸入的第一行只有一個正整數(shù)n(1 n 1000)，表示數(shù)字的個數(shù)。輸入的第二行有n個整數(shù)s1, s2,

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論