莞中-松山湖-长沙一中三校联考试题

1、莞中 - 松山湖 - 长沙一中三校联考试题莞中、松山湖学校、长沙一中三校联考试题提高组SubRaY 被布置了 n 道作业题 ,可是他一道也不会 .但他知道有 w 位高手 ,并知道每位高手会做哪些题 ,请问 SubRaY 至少请多少位高手 ,才能把所有的题都做出来 ?输入 solve.in第一行两个整数n,w 表示有 n 道作业题和 w 位高手 ,作业题以 1.n 编号 .接下来 w行,第 i+1 行第一个数 li 表示第 i 位高手会做的题目的数量 ,接下来 li 个数表示第 i 位高手会做哪些题目 .输出 solve.out一个数 ,SubRaY 至少要请多少位高手 .样例输入 41 242

2、 3 41 3样例输出 2数据范围 对于 40% 的数据 ,3=n,w=10,对于 100% 的数据 ,3=n,w=60,1=li=6解法：搜索题 , 本来打算 n 只开到 10 作为一道送分题的 ( 这也是为什么这道题是第一题的原因 ), 但是鉴于如果真这么做实在太水 ( 掉 RP), 所以改为设 4 个送分点 .搜索是基础算法 . 虽然近几年中 NOIP 搜索题占的比率并不大 , 但是在考试临近结束时 , 或者有题不会时 ,写一个简单的搜索程序往往会带来意想不到的结果 . 比如 2006 年的金明的预算方案 , 有很多大牛虽第2页共15页莞中、松山湖学校、长沙一中三校联考试题提高组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页莞中、松山湖学校、长沙一中三校联考试题提高组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.迷宫问题描述：小希非常喜欢玩迷宫游戏，现在她自己设计了一个迷宫游戏。在她设计的迷宫中，首先她认为所第6页共15页莞中、松山湖学校、长沙一中三校联考试题提高组有的通道都应该是双向连通的，就是说如果有一个通道连通了房间 A 和 B，那么既可以通过它从房间A 走到房间 B，也可以通过它从房间 B 走到房间 A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路） 。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，

6、前两个是符合条件的，但是最后一个却有两种方法从 5 到达 8。数据输入：输入包含多组数据，每组数据是一个以 0 0 结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为 1，且不超过 100000。每两组数据之间有一个空行。整个文件以两个 -1 结尾。数据输出：对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路， 那么输出 1 ，否则输出0 。输入输出样例：Migong.in68 53 52 6456 00第7页共15页莞中、松山湖学校、长沙一中三校联考试题提高组81 73 62 89 7574 78 76 003 86 86 45 35 65 20 0-1 -1

7、Migong.out110解法：这道题实际是一道数据结构题， NOIP的数据结构也是很重要的考察内容，比如线性表、哈希表、并查集、树状数组等。这道题很裸的要求判定图中任意两点是否存在唯一通路，对于具有唯一通路的图而言实际上就是树结构。根据树的特征可以知道 n 个节点的树，其必然有只有 n-1 条边相连，对数据进行初步判断将输第8页共15页莞中、松山湖学校、长沙一中三校联考试题提高组入边数不等于节点数 n-1 的图去掉，剩下来的就是判断图中是否存在回路，如果有回路则必然导致有节点不在一个连通图中，所以实际就是判断图的连通性。图的连通性判断由很多方法，比如深搜或广搜，比如种子填充算法 Blood

8、Fill ，比如最小生成树算法，当然更高效的还有并查集算法，下面就是使用并查集解决的参考代码，这道题特别要注意的地方是空集也是可行的！程序：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页莞中、松山湖学校、长沙一中三校联考试题提高组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); 边数 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); 根节点数目 , 节点都在一棵树上inc(tx); 点的个数 end;if (tx-1=tt)and(tr=1) or (max=-1)and(min=100001) then writeln(1) 利用树的特性 树为空时 , 结果为 1 else writeln(0);read(a,b);end;end.牛棚安排【问题描述】Farmer John的N(1=N=1000) 头奶牛分别居住在农场所拥有的 B(1=B=20)个牛棚的某一个里。第10页共15页莞中、松山湖学校、长沙一中三校联考试题提高组有些奶牛很喜欢她们当前住的牛棚，而另

12、一些则讨厌再在它们现在所在的牛棚呆下去。FJ在忍受了若干次奶牛的抱怨后，决定为所有奶牛重新安排牛棚，使最不满的那头奶牛与最高兴的奶牛的心情差异最小，即使这会让所有奶牛都更加郁闷。每头奶牛都把她对各个牛棚的好感度从高到低排序后告诉了 FJ。当然，如果一头奶牛被安排到的牛棚在她给出的列表中越靠后，她就会越郁闷。你可以认为奶牛的郁闷指数是她被分配到的牛棚在列表中的位置。奶牛们是斤斤计较的，她们无法容忍别的奶牛在自己喜欢的牛棚里快乐地生活，而自己却呆在一个自己不喜欢的牛棚里。每个牛棚都只能容纳一定数量的奶牛。 FJ希望在每个牛棚都没有超出容量限制的前提下，使最郁闷和最高兴的奶牛的郁闷指数的跨度最小。F

13、J请你帮他写个程序，来计算这个最小的郁闷指数跨度到底是多少。【输入】第1行: 包含 2个用空格隔开的整数 N和B，分别表示牛和牛棚的数量第2.N+1行: 每行包含 B个用空格隔开的整数，第11页共15页莞中、松山湖学校、长沙一中三校联考试题提高组刚好完全包含 1.B的整数。第 i+1行的第一个整数，表示奶牛 i最喜欢的牛棚编号。 第二个整数表示奶牛 i 的列表中排在第二位，也就是她第二喜欢的牛棚。依此类推。第N+2行: 包含 B个用空格隔开的整数， 第i个整数表示牛棚 i最多能容纳的奶牛的数目。所有牛棚能容纳奶牛头数的和至少是 N。【输出】第1行: 输出一个整数，表示所有奶牛中最高兴与最郁闷的

14、牛的郁闷指数跨度【输入输出样例】stead.instead.out6 421234231442313124134214232132【样例说明】每头奶牛都能被安排进她的第一或第二喜欢的第12页共15页莞中、松山湖学校、长沙一中三校联考试题提高组牛棚。下面给出一种合理的分配方案：奶牛1和奶牛5住入牛棚 1，牛棚2由奶牛 2独占，奶牛 4住进牛棚 3，剩下的奶牛 3和奶牛 6安排到牛棚 4。解法：原题模型是二分图匹配的，当然也可以用网络流来解，这里考察的是 noip 的算法用的是动态规划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