第一屆CCF真題+部分答案10版

1、目前CCF一共搞了4屆，這不是一個(gè)比賽，就是類(lèi)似于4/6級(jí)那種性質(zhì)，一共5題，每題滿(mǎn)分100分，據(jù)了解，基本上對(duì)了1題就能拿到證，證上會(huì)有你的分?jǐn)?shù)和排名，能考高分的盡量考高分，就像英語(yǔ)6級(jí)，430分和600多分，雖然都是發(fā)張紙給你，但還是有區(qū)別的， 第一題都比較簡(jiǎn)單，大家盡量把第一題拿下， 提交代碼不會(huì)返回對(duì)錯(cuò)給你，以你最后一次提交為你的答案，結(jié)束后再打分，也就是說(shuō)，你的代碼可能有點(diǎn)小錯(cuò)誤，但也許能得個(gè)60分，80分這樣，大概就是這樣=.=第一屆CCF第一題201403-1試題名稱(chēng)：相反數(shù)時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述有 N 個(gè)非零且各不相同的整數(shù)。請(qǐng)你編一個(gè)程序

2、求出它們中有多少對(duì)相反數(shù)(a 和 -a 為一對(duì)相反數(shù))。輸入格式第一行包含一個(gè)正整數(shù) N。(1 N 500)。第二行為 N 個(gè)用單個(gè)空格隔開(kāi)的非零整數(shù),每個(gè)數(shù)的絕對(duì)值不超過(guò)1000,保證這些整數(shù)各不相同。輸出格式只輸出一個(gè)整數(shù),即這 N 個(gè)數(shù)中包含多少對(duì)相反數(shù)。樣例輸入51 2 3 -1 -2樣例輸出2# include # include # include # include # include # define LL long longusing namespace std ;int main () /freopen(in.txt,r,stdin) ; int n ; int a520

3、; scanf(%d , &n) ; int i , j; int sum = 0 ; for (i = 0 ; i n ; i+) scanf(%d , &ai) ; for (i = 0 ; i n ; i+) for (j = 0 ; j n ; j+) if (i = j ) continue ; if (ai = -aj) sum+ ; printf(%dn , sum/2) ; return 0 ;第一屆CCF第二題試題名稱(chēng)：窗口時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述在某圖形操作系統(tǒng)中,有 N 個(gè)窗口,每個(gè)窗口都是一個(gè)兩邊與坐標(biāo)軸分別平行的矩形區(qū)域。窗口的邊界

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

5、2)。保證 x1 x2,y12。接下來(lái) M 行每行包含兩個(gè)非負(fù)整數(shù) x, y,表示一次鼠標(biāo)點(diǎn)擊的坐標(biāo)。題目中涉及到的所有點(diǎn)和矩形的頂點(diǎn)的 x, y 坐標(biāo)分別不超過(guò) 2559 和1439。輸出格式輸出包括 M 行,每一行表示一次鼠標(biāo)點(diǎn)擊的結(jié)果。如果該次鼠標(biāo)點(diǎn)擊選擇了一個(gè)窗口,則輸出這個(gè)窗口的編號(hào)(窗口按照輸入中的順序從 1 編號(hào)到 N);如果沒(méi)有,則輸出IGNORED(不含雙引號(hào))。樣例輸入3 40 0 4 41 1 5 52 2 6 61 10 04 40 5樣例輸出211IGNORED樣例說(shuō)明第一次點(diǎn)擊的位置同時(shí)屬于第 1 和第 2 個(gè)窗口,但是由于第 2 個(gè)窗口在上面,它被選擇并且被置于頂

6、層。第二次點(diǎn)擊的位置只屬于第 1 個(gè)窗口,因此該次點(diǎn)擊選擇了此窗口并將其置于頂層。現(xiàn)在的三個(gè)窗口的層次關(guān)系與初始狀態(tài)恰好相反了。第三次點(diǎn)擊的位置同時(shí)屬于三個(gè)窗口的范圍,但是由于現(xiàn)在第 1 個(gè)窗口處于頂層,它被選擇。最后點(diǎn)擊的 (0, 5) 不屬于任何窗口。# include # include # include # include # include # define LL long longusing namespace std ;struct window int x1 ; int y1 ; int x2 ; int y2 ; int id ;w12;int main () /freop

7、en(in.txt,r,stdin) ; int n , m ; scanf(%d %d , &n , &m) ; int i , j; for (i = 1 ; i = 1 ; i-) if (x = wi.x1 & x = wi.y1 & y = wi.y2) num = wi.id ; window temp = wi ; for (int k = i ; k = n ; k+) wk = wk+1 ; wn = temp ; break ; if (i != 0 ) printf(%dn , num) ; else printf(IGNOREDn) ; return 0 ;第一屆CCF

8、第三題201403-3試題名稱(chēng)：命令行選項(xiàng)時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述請(qǐng)你寫(xiě)一個(gè)命令行分析程序,用以分析給定的命令行里包含哪些選項(xiàng)。每個(gè)命令行由若干個(gè)字符串組成,它們之間恰好由一個(gè)空格分隔。這些字符串中的第一個(gè)為該命令行工具的名字,由小寫(xiě)字母組成,你的程序不用對(duì)它進(jìn)行處理。在工具名字之后可能會(huì)包含若干選項(xiàng),然后可能會(huì)包含一 些不是選項(xiàng)的參數(shù)。選項(xiàng)有兩類(lèi):帶參數(shù)的選項(xiàng)和不帶參數(shù)的選項(xiàng)。一個(gè)合法的無(wú)參數(shù)選項(xiàng)的形式是一個(gè)減號(hào)后面跟單個(gè)小寫(xiě)字母,如-a 或-b。而帶參數(shù)選項(xiàng)則由兩個(gè)由空格分隔的字符串構(gòu)成,前者的格式要求與無(wú)參數(shù)選項(xiàng)相同,后者則是該選項(xiàng)的參數(shù),是由小寫(xiě)字母

9、,數(shù)字和減號(hào)組成的非空字符串。該命令行工具的作者提供給你一個(gè)格式字符串以指定他的命令行工具需要接受哪些選項(xiàng)。這個(gè)字符串由若干小寫(xiě)字母和冒號(hào)組成,其中的每個(gè)小寫(xiě)字母表示一個(gè)該程序接受的選項(xiàng)。如果該小寫(xiě)字母后面緊跟了一個(gè)冒號(hào),它就表示一個(gè)帶參數(shù)的選項(xiàng),否則則為不帶參數(shù)的選項(xiàng)。例如, ab:m: 表示該程序接受三種選項(xiàng),即-a(不帶參數(shù)),-b(帶參數(shù)), 以及-m(帶參數(shù))。命令行工具的作者準(zhǔn)備了若干條命令行用以測(cè)試你的程序。對(duì)于每個(gè)命令行,你的工具應(yīng)當(dāng)一直向后分析。當(dāng)你的工具遇到某個(gè)字符串既不是合法的選項(xiàng),又不是某個(gè)合法選項(xiàng)的參數(shù)時(shí),分析就停止。命令行剩余的未分析部分不構(gòu)成該命令的選項(xiàng),因此你的

10、程序應(yīng)當(dāng)忽略它們。輸入格式輸入的第一行是一個(gè)格式字符串,它至少包含一個(gè)字符,且長(zhǎng)度不超過(guò) 52。格式字符串只包含小寫(xiě)字母和冒號(hào),保證每個(gè)小寫(xiě)字母至多出現(xiàn)一次,不會(huì)有兩個(gè)相鄰的冒號(hào),也不會(huì)以冒號(hào)開(kāi)頭。輸入的第二行是一個(gè)正整數(shù) N(1 N 20),表示你需要處理的命令行的個(gè)數(shù)。接下來(lái)有 N 行,每行是一個(gè)待處理的命令行,它包括不超過(guò) 256 個(gè)字符。該命令行一定是若干個(gè)由單個(gè)空格分隔的字符串構(gòu)成,每個(gè)字符串里只包含小寫(xiě)字母,數(shù)字和減號(hào)。輸出格式輸出有 N 行。其中第 i 行以Case i: 開(kāi)始,然后應(yīng)當(dāng)有恰好一個(gè)空格,然后應(yīng)當(dāng)按照字母升序輸出該命令行中用到的所有選項(xiàng)的名稱(chēng),對(duì)于帶參數(shù)的選項(xiàng),在輸

11、出它的名稱(chēng)之后還要輸出它的參數(shù)。如果一個(gè)選項(xiàng)在命令行中出現(xiàn)了多次,只輸出一次。如果一個(gè)帶參數(shù)的選項(xiàng)在命令行中出 現(xiàn)了多次,只輸出最后一次出現(xiàn)時(shí)所帶的參數(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第一屆CCF第四題201403-4試題名稱(chēng)：無(wú)線(xiàn)網(wǎng)絡(luò)時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述目前在一個(gè)很大的平面房間里有 n 個(gè)無(wú)線(xiàn)路由器,每個(gè)無(wú)線(xiàn)路由器都固定在某個(gè)點(diǎn)上

12、。任何兩個(gè)無(wú)線(xiàn)路由器只要距離不超過(guò) r 就能互相建立網(wǎng)絡(luò)連接。除此以外,另有 m 個(gè)可以擺放無(wú)線(xiàn)路由器的位置。你可以在這些位置中選擇至多 k 個(gè)增設(shè)新的路由器。你的目標(biāo)是使得第 1 個(gè)路由器和第 2 個(gè)路由器之間的網(wǎng)絡(luò)連接經(jīng)過(guò)盡量少的中轉(zhuǎn)路由器。請(qǐng)問(wèn)在最優(yōu)方案下中轉(zhuǎn)路由器的最少個(gè)數(shù)是多少?輸入格式第一行包含四個(gè)正整數(shù) n,m,k,r。(2 n 100,1 k m 100, 1 r 108)。接下來(lái) n 行,每行包含兩個(gè)整數(shù) xi和 yi,表示一個(gè)已經(jīng)放置好的無(wú)線(xiàn) 路由器在 (xi, yi) 點(diǎn)處。輸入數(shù)據(jù)保證第 1 和第 2 個(gè)路由器在僅有這 n 個(gè)路由器的情況下已經(jīng)可以互相連接(經(jīng)過(guò)一系列的

13、中轉(zhuǎn)路由器)。接下來(lái) m 行,每行包含兩個(gè)整數(shù) xi和 yi,表示 (xi, yi) 點(diǎn)處可以增設(shè) 一個(gè)路由器。輸入中所有的坐標(biāo)的絕對(duì)值不超過(guò) 108,保證輸入中的坐標(biāo)各不相同。輸出格式輸出只有一個(gè)數(shù),即在指定的位置中增設(shè) k 個(gè)路由器后,從第 1 個(gè)路 由器到第 2 個(gè)路由器最少經(jīng)過(guò)的中轉(zhuǎn)路由器的個(gè)數(shù)。樣例輸入5 3 1 30 05 50 30 53 53 34 43 0樣例輸出2第一屆CCF第五題201403-5試題名稱(chēng)：任務(wù)調(diào)度時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述有若干個(gè)任務(wù)需要在一臺(tái)機(jī)器上運(yùn)行。它們之間沒(méi)有依賴(lài)關(guān)系,因此 可以被按照任意順序執(zhí)行。該機(jī)器有兩個(gè) C

14、PU 和一個(gè) GPU。對(duì)于每個(gè)任務(wù),你可以為它分配不 同的硬件資源:1. 在單個(gè) CPU 上運(yùn)行。2. 在兩個(gè) CPU 上同時(shí)運(yùn)行。3. 在單個(gè) CPU 和 GPU 上同時(shí)運(yùn)行。4. 在兩個(gè) CPU 和 GPU 上同時(shí)運(yùn)行。一個(gè)任務(wù)開(kāi)始執(zhí)行以后,將會(huì)獨(dú)占它所用到的所有硬件資源,不得中 斷,直到執(zhí)行結(jié)束為止。第 i 個(gè)任務(wù)用單個(gè) CPU,兩個(gè) CPU,單個(gè) CPU 加 GPU,兩個(gè) CPU 加 GPU 運(yùn)行所消耗的時(shí)間分別為 ai,bi,ci和 di?，F(xiàn)在需要你計(jì)算出至少需要花多少時(shí)間可以把所有給定的任務(wù)完成。輸入格式輸入的第一行只有一個(gè)正整數(shù) n(1 n 40), 是總共需要執(zhí)行的任 務(wù)個(gè)數(shù)。

15、接下來(lái)的 n 行每行有四個(gè)正整數(shù) ai, bi, ci, di(ai, bi, ci, di均不超過(guò) 10), 以空格隔開(kāi)。輸出格式輸出只有一個(gè)整數(shù),即完成給定的所有任務(wù)所需的最少時(shí)間。樣例輸入34 4 2 27 4 7 43 3 3 3樣例輸出7樣例說(shuō)明有很多種調(diào)度方案可以在 7 個(gè)時(shí)間單位里完成給定的三個(gè)任務(wù),以下是其中的一種方案:同時(shí)運(yùn)行第一個(gè)任務(wù)(單 CPU 加上 GPU)和第三個(gè)任務(wù)(單 CPU), 它們分別在時(shí)刻 2 和時(shí)刻 3 完成。在時(shí)刻 3 開(kāi)始雙 CPU 運(yùn)行任務(wù) 2,在 時(shí)刻 7 完成。第二屆CCF第一題201409-1試題名稱(chēng)：相鄰數(shù)對(duì)時(shí)間限制：1.0s內(nèi)存限制：256

16、.0MB問(wèn)題描述：?jiǎn)栴}描述給定n個(gè)不同的整數(shù)，問(wèn)這些數(shù)中有多少對(duì)整數(shù)，它們的值正好相差1。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示給定整數(shù)的個(gè)數(shù)。第二行包含所給定的n個(gè)整數(shù)。輸出格式輸出一個(gè)整數(shù)，表示值正好相差1的數(shù)對(duì)的個(gè)數(shù)。樣例輸入610 2 6 3 7 8樣例輸出3樣例說(shuō)明值正好相差1的數(shù)對(duì)包括(2, 3), (6, 7), (7, 8)。評(píng)測(cè)用例規(guī)模與約定1=n=1000，給定的整數(shù)為不超過(guò)10000的非負(fù)整數(shù)。# include # include # include # include # include # define LL long longusing namespace st

17、d ;int a1010 ;int main () /freopen(in.txt,r,stdin) ; int n ; scanf(%d , &n) ; int i , j ; int sum = 0 ; for (i = 0 ; i n ; i+) scanf(%d , &ai) ; sort(a , a+n) ; for (i = 0 ; i n ; i+) if (ai+1 - ai != 1) continue; else sum+ ; printf(%dn , sum) ; return 0 ;第二屆CCF第二題201409-2試題名稱(chēng)：畫(huà)圖時(shí)間限制：1.0s內(nèi)存限制：256.0M

18、B問(wèn)題描述：?jiǎn)栴}描述在一個(gè)定義了直角坐標(biāo)系的紙上，畫(huà)一個(gè)(x1,y1)到(x2,y2)的矩形指將橫坐標(biāo)范圍從x1到x2，縱坐標(biāo)范圍從y1到y(tǒng)2之間的區(qū)域涂上顏色。下圖給出了一個(gè)畫(huà)了兩個(gè)矩形的例子。第一個(gè)矩形是(1,1) 到(4, 4)，用綠色和紫色表示。第二個(gè)矩形是(2, 3)到(6, 5)，用藍(lán)色和紫色表示。圖中，一共有15個(gè)單位的面積被涂上顏色，其中紫色部分被涂了兩次，但在計(jì)算面積時(shí)只計(jì)算一次。在實(shí)際的涂色過(guò)程中，所有的矩形都涂成統(tǒng)一的顏色，圖中顯示不同顏色僅為說(shuō)明方便。給出所有要畫(huà)的矩形，請(qǐng)問(wèn)總共有多少個(gè)單位的面積被涂上顏色。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示要畫(huà)的矩形的個(gè)數(shù)。接下

19、來(lái)n行，每行4個(gè)非負(fù)整數(shù)，分別表示要畫(huà)的矩形的左下角的橫坐標(biāo)與縱坐標(biāo)，以及右上角的橫坐標(biāo)與縱坐標(biāo)。輸出格式輸出一個(gè)整數(shù)，表示有多少個(gè)單位的面積被涂上顏色。樣例輸入21 1 4 42 3 6 5樣例輸出15評(píng)測(cè)用例規(guī)模與約定1=n=100，0=橫坐標(biāo)、縱坐標(biāo)=100。# include # include # include # include # include # define LL long longusing namespace std ;int a110110 ;int main () /freopen(in.txt,r,stdin) ; int n ; scanf(%d , &n)

20、; int i , j ; int x1 , y1 , x2 , y2 ; int sum = 0 ; while(n-) scanf(%d%d%d%d , &x1,&y1,&x2,&y2) ; for (i = x1+1 ; i = x2 ; i+) for (j = y1+1 ; j = y2 ; j+) aij = 1 ; for (i = 1 ; i = 105 ; i+) for (j = 1 ; j = 105 ; j+) sum += aij ; printf(%dn , sum) ; return 0 ;第二屆CCF第三題（KMP）201409-3試題名稱(chēng)：字符串匹配時(shí)間限制：

21、1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述給出一個(gè)字符串和多行文字，在這些文字中找到字符串出現(xiàn)的那些行。你的程序還需支持大小寫(xiě)敏感選項(xiàng)：當(dāng)選項(xiàng)打開(kāi)時(shí)，表示同一個(gè)字母的大寫(xiě)和小寫(xiě)看作不同的字符；當(dāng)選項(xiàng)關(guān)閉時(shí)，表示同一個(gè)字母的大寫(xiě)和小寫(xiě)看作相同的字符。輸入格式輸入的第一行包含一個(gè)字符串S，由大小寫(xiě)英文字母組成。第二行包含一個(gè)數(shù)字，表示大小寫(xiě)敏感的選項(xiàng)，當(dāng)數(shù)字為0時(shí)表示大小寫(xiě)不敏感，當(dāng)數(shù)字為1時(shí)表示大小寫(xiě)敏感。第三行包含一個(gè)整數(shù)n，表示給出的文字的行數(shù)。接下來(lái)n行，每行包含一個(gè)字符串，字符串由大小寫(xiě)英文字母組成，不含空格和其他字符。輸出格式輸出多行，每行包含一個(gè)字符串，按出現(xiàn)的順序依次給出那

22、些包含了字符串S的行。樣例輸入Hello15HelloWorldHiHiHelloHiHiGrepIsAGreatToolHELLOHELLOisNOTHello樣例輸出HelloWorldHiHiHelloHiHiHELLOisNOTHello樣例說(shuō)明在上面的樣例中，第四個(gè)字符串雖然也是Hello，但是大小寫(xiě)不正確。如果將輸入的第二行改為0，則第四個(gè)字符串應(yīng)該輸出。評(píng)測(cè)用例規(guī)模與約定1=n=100，每個(gè)字符串的長(zhǎng)度不超過(guò)100。# include # include # include # include # include # define LL long longusing namesp

23、ace std ;const int N = 110;int nextN;char SN, TN , S1N;int slen, tlen;void getNext() int j, k; j = 0; k = -1; next0 = -1; while(j tlen) if(k = -1 | Tj = Tk) next+j = +k; else k = nextk;int KMP_Count() int ans = 0; int i, j = 0; if(slen = 1 & tlen = 1) if(S0 = T0) return 1; else return 0; getNext();

24、for(i = 0; i 0 & Si != Tj) j = nextj; if(Si = Tj) j+; if(j = tlen) ans+; j = nextj; return ans;int main () /freopen(in.txt,r,stdin) ; int n , sum , tag ; int i ; cinT ; tlen = strlen(T); cintagn ; if(tag = 1) while(n-) cinS ; slen = strlen(S); sum = KMP_Count() ; if (sum = 1) coutSendl ; else for (i

25、 = 0 ; i S1 ; slen = strlen(S1); for (i = 0 ; i = 1) coutS1endl ; return 0 ;第二屆CCF第四題(bfs)201409-4試題名稱(chēng)：最優(yōu)配餐時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述棟棟最近開(kāi)了一家餐飲連鎖店，提供外賣(mài)服務(wù)。隨著連鎖店越來(lái)越多，怎么合理的給客戶(hù)送餐成為了一個(gè)急需解決的問(wèn)題。棟棟的連鎖店所在的區(qū)域可以看成是一個(gè)nn的方格圖（如下圖所示），方格的格點(diǎn)上的位置上可能包含棟棟的分店（綠色標(biāo)注）或者客戶(hù)（藍(lán)色標(biāo)注），有一些格點(diǎn)是不能經(jīng)過(guò)的（紅色標(biāo)注）。方格圖中的線(xiàn)表示可以行走的道路，相鄰兩個(gè)格點(diǎn)的

26、距離為1。棟棟要送餐必須走可以行走的道路，而且不能經(jīng)過(guò)紅色標(biāo)注的點(diǎn)。送餐的主要成本體現(xiàn)在路上所花的時(shí)間，每一份餐每走一個(gè)單位的距離需要花費(fèi)1塊錢(qián)。每個(gè)客戶(hù)的需求都可以由棟棟的任意分店配送，每個(gè)分店沒(méi)有配送總量的限制?，F(xiàn)在你得到了棟棟的客戶(hù)的需求，請(qǐng)問(wèn)在最優(yōu)的送餐方式下，送這些餐需要花費(fèi)多大的成本。輸入格式輸入的第一行包含四個(gè)整數(shù)n, m, k, d，分別表示方格圖的大小、棟棟的分店數(shù)量、客戶(hù)的數(shù)量，以及不能經(jīng)過(guò)的點(diǎn)的數(shù)量。接下來(lái)m行，每行兩個(gè)整數(shù)xi, yi，表示棟棟的一個(gè)分店在方格圖中的橫坐標(biāo)和縱坐標(biāo)。接下來(lái)k行，每行三個(gè)整數(shù)xi, yi, ci，分別表示每個(gè)客戶(hù)在方格圖中的橫坐標(biāo)、縱坐標(biāo)和

27、訂餐的量。（注意，可能有多個(gè)客戶(hù)在方格圖中的同一個(gè)位置）接下來(lái)d行，每行兩個(gè)整數(shù)，分別表示每個(gè)不能經(jīng)過(guò)的點(diǎn)的橫坐標(biāo)和縱坐標(biāo)。輸出格式輸出一個(gè)整數(shù)，表示最優(yōu)送餐方式下所需要花費(fèi)的成本。樣例輸入10 2 3 31 18 81 5 12 3 36 7 21 22 26 8樣例輸出29評(píng)測(cè)用例規(guī)模與約定前30%的評(píng)測(cè)用例滿(mǎn)足：1=n =20。前60%的評(píng)測(cè)用例滿(mǎn)足：1=n=100。所有評(píng)測(cè)用例都滿(mǎn)足：1=n=1000，1=m, k, d=n2?？赡苡卸鄠€(gè)客戶(hù)在同一個(gè)格點(diǎn)上。每個(gè)客戶(hù)的訂餐量不超過(guò)1000，每個(gè)客戶(hù)所需要的餐都能被送到。# include # include # include # in

28、clude # include # include # define LL long longusing namespace std ;int map110110 ;bool v110110 ;int n , m , k , d ;struct kehu int x ; int y ; int num ;s10010;struct node int x , y , step ;int dx = 1,-1,0,0 ;int dy = 0,0,1,-1 ;int bfs(int sx , int sy ) queue q ; int i , fx ,fy ; node now , t ; now.

29、x = sx ; now.y = sy ; now.step = 0 ; q.push(now) ; memset(v , 0 , sizeof(v) ; vsxsy = 1 ; while(!q.empty() now = q.front() ; q.pop() ; for (i = 0 ; i 4 ; i+) fx = now.x + dxi ; fy = now.y + dyi ; if (fx1 | fy n | fy n | mapfxfy = 1 | vfxfy = 1) continue ; if (mapfxfy = 2) return now.step+1 ; t.x = f

30、x ; t.y = fy ; t.step = now.step+1 ; q.push(t) ; vfxfy = 1 ; int main() /freopen(in.txt,r,stdin) ; int i , j ; int t1 , t2 ; int st = 0 ; int sum = 0 ; scanf(%d%d%d%d , &n , &m , &k , &d) ; for (i = 0 ; i m ; i+) scanf(%d%d , &t1 , &t2) ; mapt1t2 = 2 ; for (i = 0 ; i k ; i+) scanf(%d%d%d , &si.x , &

31、si.y ,&si.num) ; for (i = 0 ; i d ; i+) scanf(%d%d , &t1 , &t2) ; mapt1t2 = 1 ; for (i = 0 ; i k ; i+) st = bfs(si.x , si.y ) ; sum += (st * si.num) ; printf(%dn , sum) ; return 0 ;第二屆CCF第五題201409-5試題名稱(chēng)：拼圖時(shí)間限制：3.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述給出一個(gè)nm的方格圖，現(xiàn)在要用如下L型的積木拼到這個(gè)圖中，使得方格圖正好被拼滿(mǎn)，請(qǐng)問(wèn)總共有多少種拼法。其中，方格圖的每一個(gè)方格正好

32、能放積木中的一塊。積木可以任意旋轉(zhuǎn)。輸入格式輸入的第一行包含兩個(gè)整數(shù)n, m，表示方格圖的大小。輸出格式輸出一行，表示可以放的方案數(shù)，由于方案數(shù)可能很多，所以請(qǐng)輸出方案數(shù)除以1,000,000,007的余數(shù)。樣例輸入6 2樣例輸出4樣例說(shuō)明四種拼法如下圖所示：評(píng)測(cè)用例規(guī)模與約定在評(píng)測(cè)時(shí)將使用10個(gè)評(píng)測(cè)用例對(duì)你的程序進(jìn)行評(píng)測(cè)。評(píng)測(cè)用例1和2滿(mǎn)足：1=n=30，m=2。評(píng)測(cè)用例3和4滿(mǎn)足：1=n, m=6。評(píng)測(cè)用例5滿(mǎn)足：1=n=100，1=m=6。評(píng)測(cè)用例6和7滿(mǎn)足：1=n=1000，1=m=6。評(píng)測(cè)用例8、9和10滿(mǎn)足：1=n=1015，1=m=7。第三屆CCF第一題201412-1試題名稱(chēng)：

33、門(mén)禁系統(tǒng)時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述濤濤最近要負(fù)責(zé)圖書(shū)館的管理工作，需要記錄下每天讀者的到訪(fǎng)情況。每位讀者有一個(gè)編號(hào)，每條記錄用讀者的編號(hào)來(lái)表示。給出讀者的來(lái)訪(fǎng)記錄，請(qǐng)問(wèn)每一條記錄中的讀者是第幾次出現(xiàn)。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示濤濤的記錄條數(shù)。第二行包含n個(gè)整數(shù)，依次表示濤濤的記錄中每位讀者的編號(hào)。輸出格式輸出一行，包含n個(gè)整數(shù)，由空格分隔，依次表示每條記錄中的讀者編號(hào)是第幾次出現(xiàn)。樣例輸入51 2 1 1 3樣例輸出1 1 2 3 1評(píng)測(cè)用例規(guī)模與約定1n1,000，讀者的編號(hào)為不超過(guò)n的正整數(shù)。# include # include # inc

34、lude # include # include # define LL long longusing namespace std ;int a1010 ;int main () /freopen(in.txt,r,stdin) ; int n ; scanf(%d , &n) ; int i , x ; for (i = 1 ; i = n-1 ; i+) scanf(%d , &x) ; ax+ ; printf(%d , ax) ; scanf(%d , &x) ; ax+ ; printf(%dn , ax) ; return 0 ;第三屆CCF第二題問(wèn)題描述：?jiǎn)栴}描述在圖像編碼的算法

35、中，需要將一個(gè)給定的方形矩陣進(jìn)行Z字形掃描(Zigzag Scan)。給定一個(gè)nn的矩陣，Z字形掃描的過(guò)程如下圖所示：對(duì)于下面的44的矩陣，1 5 3 93 7 5 69 4 6 47 3 1 3對(duì)其進(jìn)行Z字形掃描后得到長(zhǎng)度為16的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3請(qǐng)實(shí)現(xiàn)一個(gè)Z字形掃描的程序，給定一個(gè)nn的矩陣，輸出對(duì)這個(gè)矩陣進(jìn)行Z字形掃描的結(jié)果。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示矩陣的大小。輸入的第二行到第n+1行每行包含n個(gè)正整數(shù)，由空格分隔，表示給定的矩陣。輸出格式輸出一行，包含nn個(gè)整數(shù)，由空格分隔，表示輸入的矩陣經(jīng)過(guò)Z字形掃描后的結(jié)果。樣例輸入

36、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評(píng)測(cè)用例規(guī)模與約定1n500，矩陣元素為不超過(guò)1000的正整數(shù)。# include # include # include # include # include # define LL long longusing namespace std ;int map500500 ;int main () /freopen(in.txt,r,stdin) ; int n ; scanf(%d , &n) ; int i , j ; for (i = 1 ; i = n ;

37、i+) for (j = 1 ; j = n ; j+) scanf(%d , &mapij) ; i = j = 1 ; int tag1 = 1 ; int tag2 = 0 ; while(i != n | j != n) while (tag1) if (i != 1 & j != n) printf(%d , mapij) ; i- ; j+ ; else if (j = n) printf(%d , mapij) ; i+ ; tag1 = 0 ; tag2 = 1 ; else if (i = 1) printf(%d , mapij) ; j+ ; tag1 = 0 ; tag

38、2 = 1 ; while(tag2) if (i != n & j != 1) printf(%d , mapij) ; i+ ; j- ; else if (i = n) printf(%d , mapij) ; j+ ; tag2 = 0 ; tag1 = 1 ; else if (j = 1) printf(%d , mapij) ; i+ ; tag2 = 0 ; tag1 = 1 ; printf(%dn , mapij) ; return 0 ;第三屆CCF第三題201412-3試題名稱(chēng)：集合競(jìng)價(jià)時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述某股票交易所請(qǐng)你編寫(xiě)一個(gè)

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

40、的程序應(yīng)當(dāng)輸出最高的那一個(gè)。輸入格式輸入數(shù)據(jù)有任意多行，每一行是一條記錄。保證輸入合法。股數(shù)為不超過(guò)108的正整數(shù)，出價(jià)為精確到恰好小數(shù)點(diǎn)后兩位的正實(shí)數(shù)，且不超過(guò)10000.00。輸出格式你需要輸出一行，包含兩個(gè)數(shù)，以一個(gè)空格分隔。第一個(gè)數(shù)是開(kāi)盤(pán)價(jià)，第二個(gè)是此開(kāi)盤(pán)價(jià)下的成交量。開(kāi)盤(pán)價(jià)需要精確到小數(shù)點(diǎn)后恰好兩位。樣例輸入buy 9.25 100buy 8.88 175sell 9.00 1000buy 9.00 400sell 8.92 400cancel 1buy 100.00 50樣例輸出9.00 450評(píng)測(cè)用例規(guī)模與約定對(duì)于100%的數(shù)據(jù)，輸入的行數(shù)不超過(guò)5000。第三屆CCF第四題(最小

41、生成樹(shù))201412-4試題名稱(chēng)：最優(yōu)灌溉時(shí)間限制：1.0s內(nèi)存限制：256.0MB問(wèn)題描述：?jiǎn)栴}描述雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個(gè)麥田挖了一口很深的水井，所有的麥田都從這口井來(lái)引水灌溉。為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉(zhuǎn)站”，利用水渠連接不同的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉?，F(xiàn)在雷雷知道哪些麥田之間可以建設(shè)水渠和建設(shè)每個(gè)水渠所需要的費(fèi)用（注意不是所有麥田之間都可以建立水渠）。請(qǐng)問(wèn)灌溉所有麥田最少需要多少費(fèi)用來(lái)修建水渠。輸入格式輸入的第一行包含兩個(gè)正整數(shù)n, m，分別表示麥田的片數(shù)和雷雷可以建立的

42、水渠的數(shù)量。麥田使用1, 2, 3, 依次標(biāo)號(hào)。接下來(lái)m行，每行包含三個(gè)整數(shù)ai, bi, ci，表示第ai片麥田與第bi片麥田之間可以建立一條水渠，所需要的費(fèi)用為ci。輸出格式輸出一行，包含一個(gè)整數(shù)，表示灌溉所有麥田所需要的最小費(fèi)用。樣例輸入4 41 2 12 3 42 4 23 4 3樣例輸出6樣例說(shuō)明建立以下三條水渠：麥田1與麥田2、麥田2與麥田4、麥田4與麥田3。評(píng)測(cè)用例規(guī)模與約定前20%的評(píng)測(cè)用例滿(mǎn)足：n5。前40%的評(píng)測(cè)用例滿(mǎn)足：n20。前60%的評(píng)測(cè)用例滿(mǎn)足：n100。所有評(píng)測(cè)用例都滿(mǎn)足：1n1000，1m100,000，1ci10,000。# include # include # include # include # include # define LL long longusing namespace