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

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

2、有多少對(duì)相反數(shù)(a和-a為一對(duì)相反數(shù))。輸入格式第一行包含一個(gè)正整數(shù)No(1WNW500)。第二行為N個(gè)用單個(gè)空格隔開的非零整數(shù)，每個(gè)數(shù)的絕對(duì)值不超過1000,保證這些整數(shù)各不相同。輸出格式只輸出一個(gè)整數(shù)，即這N個(gè)數(shù)中包含多少對(duì)相反數(shù)。樣例輸入523-1-2樣例輸出2#include#include#include#include#include#defineLLlonglongusingnamespacestd;intmain()/freopen(in.txt,r,stdin)intn;inta520;scanf(%d,&n);inti,j;intsum=0;for(i=0;in;i+)sc

3、anf(%d,&ai);for(i=0;in;i+)for(j=0;jn;j+)if(i=j)continue;if(ai=-aj)sum+;printf(%dn,sum/2);return0;第一屆CCF第二題試題名稱：時(shí)間限制：內(nèi)存限制：?jiǎn)栴}描述：窗口1.0s256.0MB問題描述在某圖形操作系統(tǒng)中，有N個(gè)窗口，每個(gè)窗口都是一個(gè)兩邊與坐標(biāo)軸分別平行的矩形區(qū)域。窗口的邊界上的點(diǎn)也屬于該窗口。窗口之間有層次的區(qū)別，在多于一個(gè)窗口重疊的區(qū)域里，只會(huì)顯示位于頂層的窗口里的內(nèi)容。當(dāng)你點(diǎn)擊屏幕上一個(gè)點(diǎn)的時(shí)候，你就選擇了處于被點(diǎn)擊位置的最頂層窗口,并且這個(gè)窗口就會(huì)被移到所有窗口的最頂層，而剩余的窗口的層

4、次順序不變。如果你點(diǎn)擊的位置不屬于任何窗口,則系統(tǒng)會(huì)忽略你這次點(diǎn)擊。現(xiàn)在我們希望你寫一個(gè)程序模擬點(diǎn)擊窗口的過程。輸入格式輸入的第一行有兩個(gè)正整數(shù)，即N和M。(1WNW10,1WMW10)接下來N行按照從最下層到最頂層的順序給出N個(gè)窗口的位置。每行包含四個(gè)非負(fù)整數(shù)xi，yi，x2，y2,表示該窗口的一對(duì)頂點(diǎn)坐標(biāo)分別為(xi,yi)和(x2,y?)。保證xix2,yi2。1122121接下來M行每行包含兩個(gè)非負(fù)整數(shù)x,y,表示一次鼠標(biāo)點(diǎn)擊的坐標(biāo)。題目中涉及到的所有點(diǎn)和矩形的頂點(diǎn)的x,y坐標(biāo)分別不超過2559和1439。輸出格式輸出包括M行，每一行表示一次鼠標(biāo)點(diǎn)擊的結(jié)果。如果該次鼠標(biāo)點(diǎn)擊選擇了一個(gè)窗

5、口，則輸出這個(gè)窗口的編號(hào)(窗口按照輸入中的順序從1編號(hào)到N);如果沒有,則輸出IGN0RED(不含雙引號(hào))。樣例輸入400441552661100405樣例輸出211IGNORED樣例說明第一次點(diǎn)擊的位置同時(shí)屬于第1和第2個(gè)窗口，但是由于第2個(gè)窗口在上面,它被選擇并且被置于頂層。第二次點(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#

6、defineLLlonglongusingnamespacestd;structwindowintx1inty1intx2inty2intidw12;intmain()/freopen(in.txt,r,stdin);intn,m;scanf(%d%d,&n,&m);inti,j;for(i=1;i=1;i-)if(x=wi.x1&x=wi.y1&y=wi.y2)num=wi.id;windowtemp=wi;for(intk=i;k=n;k+)wk=wk+1;wn=temp;break;if(i!=0)printf(%dn,num);elseprintf(IGNOREDn)return0;第

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

8、母，數(shù)字和減號(hào)組成的非空字符串。該命令行工具的作者提供給你一個(gè)格式字符串以指定他的命令行工具需要接受哪些選項(xiàng)。這個(gè)字符串由若干小寫字母和冒號(hào)組成其中的每個(gè)小寫字母表示一個(gè)該程序接受的選項(xiàng)。如果該小寫字母后面緊跟了一個(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)，因此你的程序應(yīng)

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

10、如果一個(gè)選項(xiàng)在命令行中出現(xiàn)了多次，只輸出一次。如果一個(gè)帶參數(shù)的選項(xiàng)在命令行中出現(xiàn)了多次，只輸出最后一次出現(xiàn)時(shí)所帶的參數(shù)。樣例輸入albw:x4ls-a-l-adocuments-blsls-w10-x-w15ls-a-b-c-d-e-l樣例輸出Case1:-a-lCase2:Case3:-w15-xCase4:-a-b第一屆CCF第四題2014034試題名稱：無線網(wǎng)絡(luò)時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述目前在一個(gè)很大的平面房間里有n個(gè)無線路由器，每個(gè)無線路由器都問題描述：固定在某個(gè)點(diǎn)上。任何兩個(gè)無線路由器只要距離不超過r就能互相建立網(wǎng)絡(luò)連接。除此以外，另有m個(gè)可以擺放無線路由器的

11、位置。你可以在這些位置中選擇至多k個(gè)增設(shè)新的路由器。你的目標(biāo)是使得第1個(gè)路由器和第2個(gè)路由器之間的網(wǎng)絡(luò)連接經(jīng)過盡量少的中轉(zhuǎn)路由器。請(qǐng)問在最優(yōu)方案下中轉(zhuǎn)路由器的最少個(gè)數(shù)是多少？輸入格式第一行包含四個(gè)正整數(shù)n,m,k,r。(2WnW100,1WkWmW100,1WrW108)。接下來n行,每行包含兩個(gè)整數(shù)x和y,表示一個(gè)已經(jīng)放置好的無ii線路由器在(X,y)點(diǎn)處。輸入數(shù)據(jù)保證第1和第2個(gè)路由器在僅有ii這n個(gè)路由器的情況下已經(jīng)可以互相連接(經(jīng)過一系列的中轉(zhuǎn)路由器)。接下來m行，每行包含兩個(gè)整數(shù)x和y,表示(x,y)點(diǎn)處可以iiii增設(shè)一個(gè)路由器。輸入中所有的坐標(biāo)的絕對(duì)值不超過108,保證輸入中的坐

12、標(biāo)各不相同。輸出格式輸出只有一個(gè)數(shù)，即在指定的位置中增設(shè)k個(gè)路由器后，從第1個(gè)路由器到第2個(gè)路由器最少經(jīng)過的中轉(zhuǎn)路由器的個(gè)數(shù)。樣例輸入531300550305353430樣例輸出2有若干個(gè)任務(wù)需要在一臺(tái)機(jī)器上運(yùn)行。它們之間沒有依賴關(guān)系因此可以被按照任意順序執(zhí)行。該機(jī)器有兩個(gè)CPU和一個(gè)GPU。對(duì)于每個(gè)任務(wù)，你可以為它分配不同的硬件資源：在單個(gè)CPU上運(yùn)行。在兩個(gè)CPU上同時(shí)運(yùn)行。在單個(gè)CPU和GPU上同時(shí)運(yùn)行。在兩個(gè)CPU和GPU上同時(shí)運(yùn)行。一個(gè)任務(wù)開始執(zhí)行以后，將會(huì)獨(dú)占它所用到的所有硬件資源,不得中斷，直到執(zhí)行結(jié)束為止。第i個(gè)任務(wù)用單個(gè)CPU，兩個(gè)CPU，單個(gè)CPU加GPU,兩個(gè)CPU加GP

13、U運(yùn)行所消耗的時(shí)間分別為a,b,c和d。iiii現(xiàn)在需要你計(jì)算出至少需要花多少時(shí)間可以把所有給定的任務(wù)完成。輸入格式輸入的第一行只有一個(gè)正整數(shù)n（lWnW40）,是總共需要執(zhí)行的任務(wù)個(gè)數(shù)。接下來的n行每行有四個(gè)正整數(shù)a,b,c,d（a,b,c,d均iiiiiiii不超過10）,以空格隔開。輸出格式輸出只有一個(gè)整數(shù),即完成給定的所有任務(wù)所需的最少時(shí)間。樣例輸入342274743333樣例輸出7樣例說明有很多種調(diào)度方案可以在7個(gè)時(shí)間單位里完成給定的三個(gè)任務(wù),以下是其中的一種方案：同時(shí)運(yùn)行第一個(gè)任務(wù)（單CPU加上GPU）和第三個(gè)任務(wù)（單CPU）,它們分別在時(shí)刻2和時(shí)刻3完成。在時(shí)刻3開始雙CPU運(yùn)行

14、任務(wù)2,在時(shí)刻7完成。第二屆CCF第一題201409-1試題名稱：時(shí)間限制：相鄰數(shù)對(duì)1.0s內(nèi)存限制：?jiǎn)栴}描述：256.0MB問題描述給定n個(gè)不冋的整數(shù)，問這些數(shù)中有多少對(duì)整數(shù)，它們的值正好相差1。輸入格式輸入的第一行包含一個(gè)整數(shù)n,表示給定整數(shù)的個(gè)數(shù)。第二行包含所給定的n個(gè)整數(shù)。輸出格式輸出一個(gè)整數(shù)，表示值正好相差1的數(shù)對(duì)的個(gè)數(shù)。樣例輸入61026378樣例輸出3樣例說明值正好相差1的數(shù)對(duì)包括(2,3),(6,7),(7,8)。評(píng)測(cè)用例規(guī)模與約定1二n=1000,給定的整數(shù)為不超過10000的非負(fù)整數(shù)。#include#include#include#include#include#defi

15、neLLlonglongusingnamespacestd;inta1010;intmain()/freopen(in.txt,r,stdin)intn;scanf(%d,&n);inti,j;intsum=0;for(i=0;in;i+)scanf(%d,&ai)sort(a,a+n)for(i=0;in;i+)if(ai+1-ai!=1)continue;elsesum+;printf(%dn,sum);return0;第二屆CCF第二題2014092試題名稱：畫圖時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述在一個(gè)定義了直角坐標(biāo)系的紙上，畫一個(gè)(x1,y1)到(x2,y2)的矩形指將

16、橫坐標(biāo)范圍從x1到x2,縱坐標(biāo)范圍從y1到y(tǒng)2之間的區(qū)域涂上顏色。問題描述：下圖給出了一個(gè)畫了兩個(gè)矩形的例子。第一個(gè)矩形是(1,1)到(4,4)，用綠色和紫色表示。第二個(gè)矩形是(2,3)到(6,5)，用藍(lán)色和紫色表示。圖中，一共有15個(gè)單位的面積被涂上顏色，其中紫色部分被涂了兩次，但在計(jì)算面積時(shí)只計(jì)算一次。在實(shí)際的涂色過程中，所有的矩形都涂成統(tǒng)一的顏色，圖中顯示不冋顏色僅為說明方便。y4_0 x給出所有要畫的矩形，請(qǐng)問總共有多少個(gè)單位的面積被涂上顏色。輸入格式輸入的第一行包含一個(gè)整數(shù)n,表示要畫的矩形的個(gè)數(shù)。接下來n行，每行4個(gè)非負(fù)整數(shù)，分別表示要畫的矩形的左下角的橫坐標(biāo)與縱坐標(biāo)，以及右上角的

17、橫坐標(biāo)與縱坐標(biāo)。輸出格式輸出一個(gè)整數(shù)，表示有多少個(gè)單位的面積被涂上顏色。樣例輸入2144365樣例輸出15評(píng)測(cè)用例規(guī)模與約定1二n=100,0=橫坐標(biāo)、縱坐標(biāo)=100。#include#include#include#include#include#defineLLlonglongusingnamespacestd;inta110110intmain()/freopen(in.txt,r,stdin);intn;scanf(%d,&n);inti,j;intx1,y1,x2,y2;intsum=0;while(n-)scanf(%d%d%d%d,&x1,&y1,&x2,&y2)for(i=x1

18、+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);return0第二屆CCF第三題（KMP）201409-3試題名稱：字符串匹配時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述：?jiǎn)栴}描述給出一個(gè)字符串和多行文字，在這些文字中找到字符串出現(xiàn)的那些行。你的程序還需支持大小寫敏感選項(xiàng)：當(dāng)選項(xiàng)打開時(shí)，表示冋一個(gè)字母的大寫和小寫看作不冋的字符；當(dāng)選項(xiàng)關(guān)閉時(shí)，表示冋一個(gè)字母的大寫和小寫看作相同的字符。輸入格式輸入的第一行包含一個(gè)字符串S,由大小寫英文字母組成。第一行

19、包含一個(gè)數(shù)字，表示大小與敏感的選項(xiàng)，當(dāng)數(shù)字為0時(shí)表示大小與不敏感，當(dāng)數(shù)字為1時(shí)表示大小與敏感。第三行包含一個(gè)整數(shù)n,表示給出的文字的行數(shù)。接下來n行，每行包含一個(gè)字符串，字符串由大小與央文字母組成，不含空格和其他字符。輸出格式輸出多行，每行包含一個(gè)字符串，按出現(xiàn)的順序依次給出那些包含了字符串S的行。樣例輸入Hello15HelloWorldHiHiHelloHiHiGrepIsAGreatToolHELLOHELLOisNOTHello樣例輸出HelloWorldHiHiHelloHiHiHELLOisNOTHello樣例說明在上面的樣例中，第四個(gè)字符串雖然也是Hello,但是大小寫不正確。如

20、果將輸入的第二行改為0，則第四個(gè)字符串應(yīng)該輸出。評(píng)測(cè)用例規(guī)模與約定1=n=100,每個(gè)字符串的長(zhǎng)度不超過100。#include#include#include#include#include#defineLLlonglongusingnamespacestd;constintN=110;intnextN;charSN,TN,S1N;intslen,tlen;voidgetNext()intj,k;j=0;k=-1;next0=-1;while(jtlen)if(k=-1|Tj=Tk)next+j=+k;elsek=nextk;intKMP_Count()intans=0;inti,j=0;i

21、f(slen=1&tlen=1)if(S0=T0)return1;elsereturn0;getNext();for(i=0;i0&Si!=Tj)j=nextj;if(Si=Tj)j+;if(j=tlen)ans+;j=nextj;returnans;intmain()/freopen(in.txt,r,stdin);intn,sum,tag;inti;cinT;tlen=strlen(T);cintagn;if(tag=1)while(n-)cinS;slen=strlen(S);sum=KMP_Count();if(sum=1)coutSendl;elsefor(i=0;iS1;slen=

22、strlen(S1);for(i=0;i=1)coutS1endl;return0;第二屆CCF第四題(bfs)內(nèi)存限制:256.0MB問題描述棟棟最近開了一家餐飲連鎖店，提供外賣服務(wù)。隨著連鎖店越來越多，怎么合理的給客戶送餐成為了一個(gè)急需解決的問題。棟棟的連鎖店所在的區(qū)域可以看成是一個(gè)nXn的方格圖（如下圖所示），方格的格點(diǎn)上的位置上可能包含棟棟的分店（綠色標(biāo)注）或者客戶（藍(lán)色標(biāo)注），有一些格點(diǎn)是不能經(jīng)過的（紅色標(biāo)注）。方格圖中的線表示可以行走的道路，相鄰兩個(gè)格點(diǎn)的距離為1。棟棟要送餐必須走可以行走的道路，而且不能經(jīng)過紅色標(biāo)注的點(diǎn)。問題描述:送餐的主要成本體現(xiàn)在路上所花的時(shí)間，每一份餐每走一

23、個(gè)單位的距離需要花費(fèi)1塊錢。每個(gè)客戶的需求都可以由棟棟的任意分店配送，每個(gè)分店沒有配送總量的限制?，F(xiàn)在你得到了棟棟的客戶的需求，請(qǐng)問在最優(yōu)的送餐方式下，送這些餐需要花費(fèi)多大的成本。輸入格式輸入的第一行包含四個(gè)整數(shù)n,m,k,d,分別表示方格圖的大小、棟棟的分店數(shù)量、客戶的數(shù)量，以及不能經(jīng)過的點(diǎn)的數(shù)量。接下來m行，每行兩個(gè)整數(shù)xi,yi,表示棟棟的一個(gè)分店在方格圖中的橫坐標(biāo)和縱坐標(biāo)。接下來k行，每行三個(gè)整數(shù)xi,yi,ci，分別表示每個(gè)客戶在方格圖中的橫坐標(biāo)、縱坐標(biāo)和訂餐的量。（注意，可能有多個(gè)客戶在方格圖中的同一個(gè)位置）接下來d行，每行兩個(gè)整數(shù)，分別表示每個(gè)不能經(jīng)過的點(diǎn)的橫坐標(biāo)和縱坐標(biāo)。輸出格

24、式輸出一個(gè)整數(shù)，表示最優(yōu)送餐方式下所需要花費(fèi)的成本。樣例輸入1023311885133672122268樣例輸出29評(píng)測(cè)用例規(guī)模與約定前30%的評(píng)測(cè)用例滿足：l=n=20o前60%的評(píng)測(cè)用例滿足：l=n=100。所有評(píng)測(cè)用例都滿足：1二n=1000,l二m,k,d=n2?？赡苡卸鄠€(gè)客戶在同一個(gè)格點(diǎn)上。每個(gè)客戶的訂餐量不超過1000，每個(gè)客戶所需要的餐都能被送到。#include#include#include#include#include#include#defineLLlonglongusingnamespacestd;intmap110110;boolv110110;intn,m,k,d

25、;structkehuintx;inty;intnum;s10010;structnodeintx,y,step;intdx=1,-1,0,0;intdy=0,0,1,-1;intbfs(intsx,intsy)queueq;inti,fx,fy;nodenow,t;now.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;i4;i+)fx=now.x+dxi;fy=now.y+dyi;|mapfxfy=1|if(fx1|

26、fyn|fynvfxfy=1)continue;if(mapfxfy=2)returnnow.step+1;t.x=fx;t.y=fy;t.step=now.step+1;q.push(t);vfxfy=1;intmain()/freopen(in.txt,r,stdin);-(UInu!Is*q-s)H+urns-(ALUsx!s)SJqHFs一(+!I-上I-0HDR04-In石戶二Iideul-3總、p手p%、)4ueos一(+二P二0丄：04Imu-!ISEA-!Is曲XHS曲,、p手p手p%、)4ueos(+!I-上!I-0HDR04-ZH石戶二Iideul-3總、p手p%、)4ue

27、os一(+二曰二0丄：04-(P曲龕畠u曲,、p手p手p手p%、)4ueos-0Hurnsq-u-!I-0HPSFU-!I-睪IFFU-!I給出一個(gè)nXm的方格圖，現(xiàn)在要用如下L型的積木拼到這個(gè)圖中，使得方格圖正好被拼滿，請(qǐng)問總共有多少種拼法。其中，方格圖的每一個(gè)方格正好能放積木中的一塊。積木可以任意旋轉(zhuǎn)。輸入格式輸入的第一行包含兩個(gè)整數(shù)n,m,表示方格圖的大小。輸出格式輸出一行，表示可以放的方案數(shù)，由于方案數(shù)可能很多，所以請(qǐng)輸出方案數(shù)除以1,000,000,007的余數(shù)。樣例輸入62樣例輸出4樣例說明四種拼法如下圖所示:評(píng)測(cè)用例規(guī)模與約定在評(píng)測(cè)時(shí)將使用10個(gè)評(píng)測(cè)用例對(duì)你的程序進(jìn)行評(píng)測(cè)。評(píng)測(cè)用

28、例1和2滿足：1二n=30,m=2。評(píng)測(cè)用例3和4滿足：1二n,m=6。評(píng)測(cè)用例5滿足：1=n=100,1=m=6。評(píng)測(cè)用例6和7滿足：1=n=1000,1=m=6。評(píng)測(cè)用例8、9和10滿足：1=n=1015,1=m=7。第三屆CCF第一題201412-1試題名稱：時(shí)間限制：內(nèi)存限制：?jiǎn)栴}描述：門禁系統(tǒng)1.0s256.0MB問題描述濤濤最近要負(fù)責(zé)圖書館的管理工作，需要記錄下每天讀者的到訪情況。每位讀者有一個(gè)編號(hào)，每條記錄用讀者的編號(hào)來表示。給出讀者的來訪記錄，請(qǐng)問每一條記錄中的讀者是第幾次出現(xiàn)。輸入格式輸入的第一行包含一個(gè)整數(shù)n,表示濤濤的記錄條數(shù)。第二行包含n個(gè)整數(shù)，依次表示濤濤的記錄中每位

29、讀者的編號(hào)。輸出格式輸出一行，包含n個(gè)整數(shù)，由空格分隔，依次表示母條記錄中的讀者編號(hào)是第幾次出現(xiàn)。樣例輸入512113樣例輸出11231評(píng)測(cè)用例規(guī)模與約定1WnW1,000,讀者的編號(hào)為不超過n的正整數(shù)。#include#include#include#include#include#defineLLlonglongusingnamespacestd;inta1010;intmain()/freopen(in.txt,r,stdin)intn;scanf(%d,&n);inti,x;for(i=1;i=n-1;i+)scanf(%d,&x);ax+;printf(%d,ax);scanf(%d

30、,&x);ax+;printf(%dn,ax);return0;第三屆CCF第二題問題描述問題描述:對(duì)于下面的4X4的矩陣，1397574335619643在圖像編碼的算法中，需要將一個(gè)給定的方形矩陣進(jìn)行Z字形掃描Z字形掃描的過程如下圖所示:對(duì)其進(jìn)行Z字形掃描后得到長(zhǎng)度為16的序列：1539739547366413請(qǐng)實(shí)現(xiàn)一個(gè)Z字形掃描的程序，給定一個(gè)nXn的矩陣，輸出對(duì)這個(gè)矩陣進(jìn)行Z字形掃描的結(jié)果。輸入格式輸入的第一行包含一個(gè)整數(shù)n,表示矩陣的大小。輸入的第二行到第n+1行每行包含n個(gè)正整數(shù)，由空格分隔，表示給定的矩陣。輸出格式輸出一行，包含nXn個(gè)整數(shù)，由空格分隔，表示輸入的矩陣經(jīng)過Z字形掃

31、描后的結(jié)果。樣例輸入41539375694647313樣例輸出1539739547366413評(píng)測(cè)用例規(guī)模與約定lWnW500,矩陣元素為不超過1000的正整數(shù)。#include#include#include#include#include#defineLLlonglongusingnamespacestd;intmap500500intmain()/freopen(in.txt,r,stdin);intn;scanf(%d,&n);inti,j;for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&mapij)i=j=1;inttag1=1;inttag2=0;w

32、hile(i!=n|j!=n)while(tag1)if(i!=1&j!=n)printf(%di-;j+;elseif(j=n)printf(%di+;tag1=0;tag2=1;elseif(i=1)printf(%dj+;tag1=0;tag2=1;while(tag2)if(i!=n&jprintf(%di+;j-;elseif(i=n)printf(%dj+;tag2=0;tag1=1;elseif(j=1)printf(%di+;,mapij),mapij),mapij)=1),mapij),mapij),mapij)tag2=0;tag1=1;printf(%dn,mapij)r

33、eturn0;第三屆CCF第三題201412-3試題名稱：時(shí)間限制：內(nèi)存限制：?jiǎn)栴}描述：集合競(jìng)價(jià)1.0s256.0MB問題描述某股票交易所請(qǐng)你編寫一個(gè)程序，根據(jù)開盤前客戶提交的訂單來確定某特定股票的開盤價(jià)和開盤成交量。該程序的輸入由很多行構(gòu)成，每一行為一條記錄，記錄可能有以下幾種：buyps表示一個(gè)購(gòu)買股票的買單，每手出價(jià)為p,購(gòu)買股數(shù)為S。sellps表示一個(gè)出售股票的賣單，每手出價(jià)為p，出售股數(shù)為Socanceli表示撤銷第i行的記錄。如果開盤價(jià)為p0,則系統(tǒng)可以將所有出價(jià)至少為p0的買單和所有出價(jià)至多為p的賣單進(jìn)行匹配。因此，此時(shí)的開盤成交量為出價(jià)至少為p的買單的總股數(shù)和所有出價(jià)至多為p

34、的賣單的總股數(shù)之間的較小值。你的程序需要確定一個(gè)開盤價(jià)，使得開盤成交量盡可能地大。如果有多個(gè)符合條件的開盤價(jià)，你的程序應(yīng)當(dāng)輸出最高的那一個(gè)。輸入格式輸入數(shù)據(jù)有任意多行，每一行是一條記錄。保證輸入合法。股數(shù)為不超過108的正整數(shù)，出價(jià)為精確到恰好小數(shù)點(diǎn)后兩位的正實(shí)數(shù)，且不超過10000.00。輸出格式你需要輸出一行，包含兩個(gè)數(shù)，以一個(gè)空格分隔。第一個(gè)數(shù)是開盤價(jià)，第二個(gè)是此開盤價(jià)下的成交量。開盤價(jià)需要精確到小數(shù)點(diǎn)后恰好兩位。樣例輸入buy9.25100buy8.88175sell9.001000buy9.00400sell8.92400cancel1buy100.0050樣例輸出9.00450評(píng)測(cè)

35、用例規(guī)模與約定對(duì)于100%的數(shù)據(jù)，輸入的行數(shù)不超過5000。第三屆CCF第四題（最小生成樹）201412-4試題名稱：最優(yōu)灌溉時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個(gè)麥田挖了一口很深的水井，所有的麥田都從這口井來引水灌溉。為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉(zhuǎn)站”，利用水渠連接不冋的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉。現(xiàn)在雷雷知道哪些麥田之間可以建設(shè)水渠和建設(shè)每個(gè)水渠所需要的費(fèi)用（注意不是所有麥田之間都可以建立水渠）。請(qǐng)問灌溉所有麥田最少需要多少費(fèi)用來修建水渠。問題

36、描述：輸入格式輸入的第一行包含兩個(gè)正整數(shù)n,m,分別表示麥田的片數(shù)和雷雷可以建立的水渠的數(shù)量。麥田使用1,2,3,依次標(biāo)號(hào)。接下來m行，每行包含三個(gè)整數(shù)a,b,c,表示第a片麥田與第biiiii片麥田之間可以建立一條水渠，所需要的費(fèi)用為c。i輸出格式輸出一行，包含一個(gè)整數(shù)，表示灌溉所有麥田所需要的最小費(fèi)用。樣例輸入441212344243樣例輸出6樣例說明建立以下二條水渠：麥田1與麥田2、麥田2與麥田4、麥田4與麥田3。評(píng)測(cè)用例規(guī)模與約定前20%的評(píng)測(cè)用例滿足：nW5。前40%的評(píng)測(cè)用例滿足：nW20。前60%的評(píng)測(cè)用例滿足：nW100。所有評(píng)測(cè)用例都滿足：1WnW1000,1WmW100,0

37、00,lW*10,000。#include#include#include#include#include#defineLLlonglongusingnamespacestd;intn;constintMAXN=1010;constintMAXM=100010;intFMAXN;structEdgeintu,v,w;edgeMAXM;inttol;voidaddedge(intu,intv,intw)edgetol.u=u;edgetol.v=v;edgetol+.w=w;boolcmp(Edgea,Edgeb)returna.wb.w;intfind(intx)if(Fx=-1)return

38、x;elsereturnFx=find(Fx);intKruskal()memset(F,-1,sizeof(F);sort(edge,edge+tol,cmp);intcnt=0;intans=0;for(inti=0;itol;i+)intu=edgei.u;intv=edgei.v;intw=edgei.w;intt1=find(u);intt2=find(v);if(t1!=t2)ans+=w;Ft1=t2;cnt+;if(cnt=n-1)break;if(cntn-1)return-1;elsereturnans;intmain()/freopen(in.txt,r,stdin);i

39、ntm;scanf(%d%d,&n,&m);inti;intu,v,w;tol=0;while(m-)scanf(%d%d%d,&u,&v,&w)addedge(u,v,w);addedge(v,u,w);intk=Kruskal();printf(%dn,k)return0;第三屆CCF第五題201412-5試題名稱：貨物調(diào)度時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述某公司要處理一個(gè)周期性的物流問題。有n個(gè)城市，第i個(gè)城市在每周的第j(1WjW7)天會(huì)生產(chǎn)a噸某種ij貨物，同時(shí)需要消耗b噸該種貨物。已知每周的產(chǎn)量等于消耗量(即aijij之和等于b之和)。ij城市之間有m條道路，第k條

40、道路連接了城市s和t。一條道路上運(yùn)kk輸1噸貨物有一個(gè)固定的成本C。道路都可以雙向使用。每天運(yùn)輸?shù)呢浳飇量沒有限制。城市之間的距離并不遠(yuǎn)，貨物可以從任意一個(gè)城市運(yùn)輸?shù)饺我饬硪粋€(gè)城市并且在當(dāng)天到達(dá)。貨物如果在當(dāng)天沒有被消耗掉，就需要存放在倉(cāng)庫(kù)里過夜。第i個(gè)城市的倉(cāng)庫(kù)容量為V,存放1噸貨物過一夜所需的成本是W。ii請(qǐng)你計(jì)算該公司如果每周循環(huán)性地按照一個(gè)固定的流程調(diào)度貨物的問題描述：話，該公司在最優(yōu)方案下每周需要為貨物的運(yùn)輸和存儲(chǔ)消耗多少成本。輸入格式輸入的第一行有兩個(gè)正整數(shù)n和m,即城市的個(gè)數(shù)和道路的條數(shù)。接下來有n行，每行包含16個(gè)整數(shù)，用以描述第i個(gè)城市的相關(guān)數(shù)據(jù)。其中第i行包含的數(shù)為aix，

41、ai2，ai3，ai4，ai5，a,ai7，b,b,b,bi4,bi5,bi6,bi7,vi,wi。接下來有m行，每行包含3個(gè)整數(shù)，用以描述一條道路的相關(guān)數(shù)據(jù)。其中第k行包含的數(shù)為sk,匚和ck。kkk輸入數(shù)據(jù)中城市的編號(hào)均為1到n之間。輸入數(shù)據(jù)的每行的行首行尾均保證沒有空格，兩個(gè)數(shù)之間恰好被一個(gè)空格隔開。輸出格式你只需要輸出一個(gè)數(shù)，即最優(yōu)方案下每周的支出。樣例輸入330000500000000024000000020000002100000000030000251213531樣例輸出67樣例說明城市1每周五生產(chǎn)5噸貨物，把其中2噸運(yùn)到存儲(chǔ)費(fèi)用低廉的城市2存儲(chǔ)，把1噸運(yùn)到城市3存儲(chǔ)，剩下的2噸

42、留在城市1。在次周一的時(shí)候城市2會(huì)消耗掉存放在那里的2噸貨物。為了節(jié)約存儲(chǔ)成本，將囤放在城市1的貨物運(yùn)到城市2存放。周三再將所有貨物運(yùn)到城市3以滿足該城市的需求。在此方案下，每周的運(yùn)輸成本為8,每周的存儲(chǔ)成本為59,因此每周的總支出為67。評(píng)測(cè)用例規(guī)模與約定對(duì)于100%的數(shù)據(jù)，1WnW100,1WmW500,0Wa,b,vW100,1WijijiW100。第四屆CCF第一題2015031試題名稱：時(shí)間限制：內(nèi)存限制：?jiǎn)栴}描述：圖像旋轉(zhuǎn)5.0s256.0MB問題描述旋轉(zhuǎn)是圖像處理的基本操作，在這個(gè)問題中，你需要將一個(gè)圖像逆時(shí)針旋轉(zhuǎn)90度。計(jì)算機(jī)中的圖像表示可以用一個(gè)矩陣來表示，為了旋轉(zhuǎn)一個(gè)圖像，

43、只需要將對(duì)應(yīng)的矩陣旋轉(zhuǎn)即可。輸入格式輸入的第一行包含兩個(gè)整數(shù)n,m,分別表示圖像矩陣的行數(shù)和列數(shù)。接下來n行每行包含m個(gè)整數(shù)，表示輸入的圖像。輸出格式輸出m行，每行包含n個(gè)整數(shù)，表示原始矩陣逆時(shí)針旋轉(zhuǎn)90度后的矩陣。樣例輸入315324樣例輸出345213評(píng)測(cè)用例規(guī)模與約定1Wn,mW1,000,矩陣中的數(shù)都是不超過1000的非負(fù)整數(shù)。#include#include#include#include#include#defineLLlonglongusingnamespacestd;inta10101010;intmain()/freopen(in.txt,r,stdin);intn,m;sc

44、anf(%d%d,&n,&m);inti,j;for(i=0;in;i+)for(j=0;j=0;i-)for(j=0;jn;j+)printf(%d,aji)printf(n);return0第四屆CCF第二題201503-2數(shù)字排序試題名稱：時(shí)間限制：1.0s內(nèi)存限制：256.0MB問題描述：?jiǎn)栴}描述給定n個(gè)整數(shù)，請(qǐng)統(tǒng)計(jì)出每個(gè)整數(shù)出現(xiàn)的次數(shù)，按出現(xiàn)次數(shù)從多到少的順序輸出。輸入格式輸入的第一行包含一個(gè)整數(shù)n,表示給定數(shù)字的個(gè)數(shù)。第二行包含n個(gè)整數(shù)，相鄰的整數(shù)之間用一個(gè)空格分隔，表示所給定的整數(shù)。輸出格式輸出多行，每行包含兩個(gè)整數(shù)，分別表示一個(gè)給定的整數(shù)和它出現(xiàn)的次數(shù)。按出現(xiàn)次數(shù)遞減的順序輸出

45、。如果兩個(gè)整數(shù)出現(xiàn)的次數(shù)一樣多，則先輸出值較小的，然后輸出值較大的。樣例輸入12523313425235樣例輸出42353111評(píng)測(cè)用例規(guī)模與約定1WnW1000，給出的數(shù)都是不超過1000的非負(fù)整數(shù)。#include#include#include#include#include#defineLLlonglongusingnamespacestd;structshuintnum;intid;a1010;boolcmp(shux,shuy)if(x.num=y.num)returnx.idy.num;intmain()/freopen(in.txt,r,stdin)intn;scanf(%d,

46、&n);inti,x;for(i=1;i=1005;i+)ai.id=i;ai.num=0;while(n-)scanf(%d,&x);ax.num+;sort(a+1,a+1005,cmp);for(i=1;i=1005;i+)if(ai.num=0)break;printf(%d%dn,ai.id,ai.num)return0第四屆CCF第三題2015033試題名稱：時(shí)間限制：內(nèi)存限制：?jiǎn)栴}描述：節(jié)日1.0s256.0MB問題描述有一類節(jié)日的日期并不是固定的，而是以“a月的第b個(gè)星期c”的形式定下來的，比如說母親節(jié)就定為每年的五月的第二個(gè)星期日?，F(xiàn)在，給你a,b,c和丫,y2(1850WyW2050)，希望你輸出從公元y年到公元y年間的每年的a月的第b個(gè)星期c的日期。提示:關(guān)于閏年的規(guī)則：年份是400的整數(shù)倍時(shí)是閏年，否則年份是4的倍數(shù)并且不是100的倍數(shù)時(shí)是閏年，其他年份都不是閏年。例如1900年就不是閏年，而2000年是閏年。為了方便你推算，已知1850年1月1日是星期二。輸入格式輸入包含恰好一彳丁，有五個(gè)整數(shù)a,b,c,丫,y2。其中c=1,2,6,7分別表示星期一、二、八、日。輸出格式對(duì)于丫和y2之間的母一個(gè)年份，包括丫和y2，按照年份從小到大的順序輸出一行。如果該年的a月第b個(gè)星期c確實(shí)存在，則以yyyy/mm/dd的