莞中-松山湖-長沙一中三校聯(lián)考試題

1、莞中 - 松山湖 - 長沙一中三校聯(lián)考試題莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組SubRaY 被布置了 n 道作業(yè)題 ,可是他一道也不會 .但他知道有 w 位高手 ,并知道每位高手會做哪些題 ,請問 SubRaY 至少請多少位高手 ,才能把所有的題都做出來 ?輸入 solve.in第一行兩個(gè)整數(shù)n,w 表示有 n 道作業(yè)題和 w 位高手 ,作業(yè)題以 1.n 編號 .接下來 w行,第 i+1 行第一個(gè)數(shù) li 表示第 i 位高手會做的題目的數(shù)量 ,接下來 li 個(gè)數(shù)表示第 i 位高手會做哪些題目 .輸出 solve.out一個(gè)數(shù) ,SubRaY 至少要請多少位高手 .樣例輸入 41 242

2、 3 41 3樣例輸出 2數(shù)據(jù)范圍 對于 40% 的數(shù)據(jù) ,3=n,w=10,對于 100% 的數(shù)據(jù) ,3=n,w=60,1=li=6解法：搜索題 , 本來打算 n 只開到 10 作為一道送分題的 ( 這也是為什么這道題是第一題的原因 ), 但是鑒于如果真這么做實(shí)在太水 ( 掉 RP), 所以改為設(shè) 4 個(gè)送分點(diǎn) .搜索是基礎(chǔ)算法 . 雖然近幾年中 NOIP 搜索題占的比率并不大 , 但是在考試臨近結(jié)束時(shí) , 或者有題不會時(shí) ,寫一個(gè)簡單的搜索程序往往會帶來意想不到的結(jié)果 . 比如 2006 年的金明的預(yù)算方案 , 有很多大牛雖第2頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組begi

3、nassign(input,solve.in); reset(input); assign(output,solve.out); rewrite(output); readln(n,m);for i:=1 to m do beginread(li);for j:=1 to li do begin read(ai,j); bi,ai,j:=true;end;readln;end;for i:=1 to m dofor j:=1 to m doif (ij) and (li0) and (lj0) then begin can:=true;for k:=1 to li do if not bj,a

4、i,k then begin can:=false; break;end;if can then beginli:=0; break;end;end;第5頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組ans:=0;for i:=1 to n do beginfor j:=1 to m do if bj,i then begin inc(si,0); si,si,0:=j;end;if si,0=1 then if lsi,10 then begin x:=si,1; ans:=ans+1;for j:=1 to lx do inc(dax,j); lx:=0;end;end;max:=

5、9999;dfs(ans,1);writeln(max);close(input); close(output); end.2.迷宮問題描述：小希非常喜歡玩迷宮游戲，現(xiàn)在她自己設(shè)計(jì)了一個(gè)迷宮游戲。在她設(shè)計(jì)的迷宮中，首先她認(rèn)為所第6頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組有的通道都應(yīng)該是雙向連通的，就是說如果有一個(gè)通道連通了房間 A 和 B，那么既可以通過它從房間A 走到房間 B，也可以通過它從房間 B 走到房間 A，為了提高難度，小希希望任意兩個(gè)房間有且僅有一條路徑可以相通（除非走了回頭路） 。小?，F(xiàn)在把她的設(shè)計(jì)圖給你，讓你幫忙判斷她的設(shè)計(jì)圖是否符合她的設(shè)計(jì)思路。比如下面的例子，

6、前兩個(gè)是符合條件的，但是最后一個(gè)卻有兩種方法從 5 到達(dá) 8。數(shù)據(jù)輸入：輸入包含多組數(shù)據(jù)，每組數(shù)據(jù)是一個(gè)以 0 0 結(jié)尾的整數(shù)對列表，表示了一條通道連接的兩個(gè)房間的編號。房間的編號至少為 1，且不超過 100000。每兩組數(shù)據(jù)之間有一個(gè)空行。整個(gè)文件以兩個(gè) -1 結(jié)尾。數(shù)據(jù)輸出：對于輸入的每一組數(shù)據(jù)，輸出僅包括一行。如果該迷宮符合小希的思路， 那么輸出 1 ，否則輸出0 。輸入輸出樣例：Migong.in68 53 52 6456 00第7頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組81 73 62 89 7574 78 76 003 86 86 45 35 65 20 0-1 -1

7、Migong.out110解法：這道題實(shí)際是一道數(shù)據(jù)結(jié)構(gòu)題， NOIP的數(shù)據(jù)結(jié)構(gòu)也是很重要的考察內(nèi)容，比如線性表、哈希表、并查集、樹狀數(shù)組等。這道題很裸的要求判定圖中任意兩點(diǎn)是否存在唯一通路，對于具有唯一通路的圖而言實(shí)際上就是樹結(jié)構(gòu)。根據(jù)樹的特征可以知道 n 個(gè)節(jié)點(diǎn)的樹，其必然有只有 n-1 條邊相連，對數(shù)據(jù)進(jìn)行初步判斷將輸?shù)?頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組入邊數(shù)不等于節(jié)點(diǎn)數(shù) n-1 的圖去掉，剩下來的就是判斷圖中是否存在回路，如果有回路則必然導(dǎo)致有節(jié)點(diǎn)不在一個(gè)連通圖中，所以實(shí)際就是判斷圖的連通性。圖的連通性判斷由很多方法，比如深搜或廣搜，比如種子填充算法 Blood

8、Fill ，比如最小生成樹算法，當(dāng)然更高效的還有并查集算法，下面就是使用并查集解決的參考代碼，這道題特別要注意的地方是空集也是可行的！程序：program migong;var i,j,a,b,max,min,tt,tr,tx,x,y:longint;fa,rank:array1.100001of longint;map:array1.100000of boolean;function maxx(x,y:longint):longint;beginif xy then exit(x);exit(y);end;function minn(x,y:longint):longint;beginif

9、xy then exit(y);exit(x);end;function find(x:longint):longint;beginif xfax then fax:=find(fax);find:=fax;end;procedure union(x,y:longint);beginx:=find(x);第9頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組y:=find(y);if rankxranky then fax:=yelse beginif rankx=ranky then inc(rankx);fay:=x;end;end;beginread(a,b);while (a-1)

10、 do beginfor i:=1 to 100 do fai:=i;fillchar(rank,sizeof(rank),0);fillchar(map,sizeof(map),false);tr:=0; tt:=0; tx:=0;min:=100001; max:=-1;while (a0) do begininc(tt); 邊數(shù) mapa:=true; mapb:=true;max:=maxx(max,maxx(a,b);min:=minn(min,minn(a,b);union(a,b);read(a,b);end;for i:=min to max do if mapi=true t

11、hen beginif fai=i then inc(tr); 根節(jié)點(diǎn)數(shù)目 , 節(jié)點(diǎn)都在一棵樹上inc(tx); 點(diǎn)的個(gè)數(shù) end;if (tx-1=tt)and(tr=1) or (max=-1)and(min=100001) then writeln(1) 利用樹的特性 樹為空時(shí) , 結(jié)果為 1 else writeln(0);read(a,b);end;end.牛棚安排【問題描述】Farmer John的N(1=N=1000) 頭奶牛分別居住在農(nóng)場所擁有的 B(1=B=20)個(gè)牛棚的某一個(gè)里。第10頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組有些奶牛很喜歡她們當(dāng)前住的牛棚，而另

12、一些則討厭再在它們現(xiàn)在所在的牛棚呆下去。FJ在忍受了若干次奶牛的抱怨后，決定為所有奶牛重新安排牛棚，使最不滿的那頭奶牛與最高興的奶牛的心情差異最小，即使這會讓所有奶牛都更加郁悶。每頭奶牛都把她對各個(gè)牛棚的好感度從高到低排序后告訴了 FJ。當(dāng)然，如果一頭奶牛被安排到的牛棚在她給出的列表中越靠后，她就會越郁悶。你可以認(rèn)為奶牛的郁悶指數(shù)是她被分配到的牛棚在列表中的位置。奶牛們是斤斤計(jì)較的，她們無法容忍別的奶牛在自己喜歡的牛棚里快樂地生活，而自己卻呆在一個(gè)自己不喜歡的牛棚里。每個(gè)牛棚都只能容納一定數(shù)量的奶牛。 FJ希望在每個(gè)牛棚都沒有超出容量限制的前提下，使最郁悶和最高興的奶牛的郁悶指數(shù)的跨度最小。F

13、J請你幫他寫個(gè)程序，來計(jì)算這個(gè)最小的郁悶指數(shù)跨度到底是多少?！据斎搿康?行: 包含 2個(gè)用空格隔開的整數(shù) N和B，分別表示牛和牛棚的數(shù)量第2.N+1行: 每行包含 B個(gè)用空格隔開的整數(shù)，第11頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組剛好完全包含 1.B的整數(shù)。第 i+1行的第一個(gè)整數(shù)，表示奶牛 i最喜歡的牛棚編號。 第二個(gè)整數(shù)表示奶牛 i 的列表中排在第二位，也就是她第二喜歡的牛棚。依此類推。第N+2行: 包含 B個(gè)用空格隔開的整數(shù)， 第i個(gè)整數(shù)表示牛棚 i最多能容納的奶牛的數(shù)目。所有牛棚能容納奶牛頭數(shù)的和至少是 N?！据敵觥康?行: 輸出一個(gè)整數(shù)，表示所有奶牛中最高興與最郁悶的

14、牛的郁悶指數(shù)跨度【輸入輸出樣例】stead.instead.out6 421234231442313124134214232132【樣例說明】每頭奶牛都能被安排進(jìn)她的第一或第二喜歡的第12頁共15頁莞中、松山湖學(xué)校、長沙一中三校聯(lián)考試題提高組牛棚。下面給出一種合理的分配方案：奶牛1和奶牛5住入牛棚 1，牛棚2由奶牛 2獨(dú)占，奶牛 4住進(jìn)牛棚 3，剩下的奶牛 3和奶牛 6安排到牛棚 4。解法：原題模型是二分圖匹配的，當(dāng)然也可以用網(wǎng)絡(luò)流來解，這里考察的是 noip 的算法用的是動(dòng)態(tài)規(guī)劃var n,m,l,r,ans,i,j:longint; a:array0.1100,0.30of longint; p:array0.30,0.1100of longint; tot:array0.30of longint; u:array0.30of boolean;function pd(k:longint):boolean; 多重二分匹配圖 var i,jm,j:longint;b