1、第十六届全国青少年信息学奥林匹克联赛复赛试题第十六届全国青少年信息学奥林匹克联赛复赛试题（NOIP2010提高组）NOIP2010提高组复赛第一题机器翻译(Trasnlate)小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。假设内存中有 M 个单元，每单元能存放一个单词和译义。每
2、当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。假设一篇英语文章的长度为 N个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。【输入】 输入文件名为 translate.in，输入文件共 2 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数 M和 N，代表内存容量和文章的长度。 第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。文章中两个单词是同一个
3、单词，当且仅当它们对应的非负整数相同。【输出】 输出文件 translate.out 共1行，包含一个整数，为软件需要查词典的次数。【数据范围】 对于 10%的数据有 M=1，N5。00%的数据有 0M100，0m then bah-m:=false;end;/forwriteln(sum);end./mainNOIP2010提高组复赛第二题乌龟棋(Tortoise)小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行 N个格子，每个格子上一个分数（非负整数）。棋盘第 1 格是唯一的起点，第 N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中 M 张爬行卡片，
4、分成 4 种不同的类型（M 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。现在，告诉
5、你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗【输入】 输入文件名 tortoise.in。输入文件的每行中两个数之间用一个空格隔开。第 1 行2 个正整数 N和 M，分别表示棋盘格子数和爬行卡片数；第 2 行 N个非负整数，a1, a2, aN，其中 ai 表示棋盘第 i 个格子上的分数；第 3 行M 个整数，b1,b2, , bM，表示 M 张爬行卡片上的数字。输入数据保证到达终点时刚好用光 M 张爬行卡片，即 N-1=。【输出】 输出文件名 tortoise.out。 输出只有 1行，1 个整数，表示小明最多能得到的分数。【数据范围】对于 30%的数据有 1N
6、30，1M12；对于 50%的数据有 1N120，1M50，且 4 种爬行卡片，每种卡片的张数不会超过 20；对于 100%的数据有 1N350，1M120，且 4 种爬行卡片，每种卡片的张数不会超过 40；0ai100，1iN；1bi4，1iM。输入数据保证 N-1=bi 。解题报告思路&算法：基本算法：四维动态规划。思路：用 fi,j,k,l 表示分别取数字 1,2,3,4 的卡片 i,j,k,l 张，可以取得最大分数。写起来很好写，四个for四个if就搞定了。状态转移方程为fi,j,k,l:=max(fi,j,k,l,fi-1,j,k,l+ai+2*j+3*k+4*l+1);代码：pro
7、gram tortoise;varn,m:longint;a:array1.400 of longint;/b:array1.120 of longint;p:array1.4 of longint;f:array0.40,0.40,0.40,0.40 of longint;i,j,k,l,t:longint;function max(t1,t2:longint):longint;beginif t10 then fi,j,k,l:=max(fi,j,k,l,fi-1,j,k,l+ai+2*j+3*k+4*l+1);if j0 then fi,j,k,l:=max(fi,j,k,l,fi,j-
8、1,k,l+ai+2*j+3*k+4*l+1);if k0 then fi,j,k,l:=max(fi,j,k,l,fi,j,k-1,l+ai+2*j+3*k+4*l+1);if l0 then fi,j,k,l:=max(fi,j,k,l,fi,j,k,l-1+ai+2*j+3*k+4*l+1);end;/4for/outputwriteln(fp1,p2,p3,p4);end./mainNOIP2010提高组复赛第三题关押罪犯(Prison)S城现有两座监狱，一共关押着 N名罪犯，编号分别为 1N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。
9、我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。每年年末，*局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换*局长。在详细考察了 N 名罪犯间的矛盾关系后，*局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那
10、么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？【输入】 输入文件名为 prison.in。输入文件的每行中两个数之间用一个空格隔开。第一行为两个正整数 N和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 M行每行为三个正整数 aj，bj，cj，表示 aj号和 bj号罪犯之间存在仇恨，其怨气值为 cj。数据保证1aj bj N ，01.v;repeatwhile ai.vx do dec(j);if ij;/repeatif hej then qsort(he,j);if i0 dobeginif find
11、(ai.l)=find(ai.r) then begin ans:=ai.v;break;end;if (duiai.l=0) and(duiai.r=0)thenbeginduiai.l:=ai.r;duiai.r:=ai.l;end/then beginelsebeginif duiai.l0 thenbeginunion(duiai.l,ai.r);if duiai.r=0 then duiai.r:=ai.l;end;/ifif duiai.r0 thenbeginunion(duiai.r,ai.l);if duiai.l=0 then duiai.l:=ai.r;end;/ifen
12、d;/else begindec(i);end;/whilewriteln(ans);end./mainNOIP2010提高组复赛第四题引水入城(Fill)在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 N行 M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用
13、高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 N 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。【输入】 输入文件名为 flow.in。输入文件的每行中两个数之间用一个空格隔开。输入的第一行是两个正整数 N和 M，表示矩形的规模。接下来 N行，每行 M 个正整数，依次代表每座城市的海拔高度。【输出】 输出文件名为 flow.out。 输出有两行。如果能满足要求，输出的第一行是
14、整数 1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数 0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。解题报告思路&算法：基本算法：染色(FloodFill)+1次或2次BFS+动态规划思路：第一遍BFS+FloodFill处理方案：第一遍处理，要分出有解及无解情况。具体方案是：从第一行全部点开始向四个方向染色，判断最后一行是否全染。若全染（有解），则进入第二遍BFS+FloodFill处理。若不全染（无解），直接计数+输出，结束。第二遍BFS+FloodFill处理方案：第一遍BFS完成后，Ci,1表示点(1,i)所能覆盖的最后一行区间的
15、左端点，同理Ci,2表示右端点。此处比较朴素的方法是：对于每个点(1,i)，我们对全图还原+染色再循环一遍处理即可。但时间会受影响。所以应该在此处避免对染色图的还原。方法就是：从下往上染。正确的染色方案：从左至右处理点(n,i)，即向上染色，染完后第一行点的颜色即为其覆盖区间左端点。相对的，从右至左处理点(n,i)，右端点也就出来了。接下来进入DP。DP方案：线段覆盖直接进行复杂度为O(n2)的DP。最后输出，AC。注意事项：1、不要图省事地用DFS代替BFS。2、第4个点考验你的BFS。3、注意输出要求。代码：program fill;consth:array1.4,1.2 of longi
16、nt=(1,0),(-1,0),(0,-1),(0,1);varcol,a:array0.501,0.501 of longint;f:array0.500 of longint;c:array0.500,1.2 of longint;d:array0.500000 of recordx,y:longint;end;/recordn,m,i,j,color:longint;function min(a,b:longint):longint;begin if ab then exit(a) else exit(b); end;/minprocedure judge;var/judgei,j:lo
17、ngint;procedure bfs(x,y:integer);var/bfsi,t,f:longint;begin/bfst:=1;f:=1;dt.x:=x;dt.y:=y;colx,y:=color;repeatfor i:=1 to 4 doif coldf.x+hi,1,df.y+hi,2=0 thenif adf.x+hi,1,df.y+hi,2t;/repeatend;/bfsbegin/judgefor i:=0 to n+1 dobeginai,0:=maxlongint; ai,m+1:=maxlongint;end;/forfor i:=0 to m+1 dobegina
18、0,i:=maxlongint;an+1,i:=maxlongint;end;for color:=1 to m do bfs(1,color);j:=0;for i:=1 to m do if coln,i=0 then inc(j);if j0 then begin writeln(0); writeln(j); halt; end;end;/judge/if no solution then output and haltprocedure floodfill;procedure bfs(x,y:integer);var/bfsi,t,f:longint;begin/bfst:=1;f:
19、=1;dt.x:=x;dt.y:=y;colx,y:=color;repeatfor i:=1 to 4 doif coldf.x+hi,1,df.y+hi,2=0 thenif adf.x+hi,1,df.y+hi,2adf.x,df.y thenbegin/ifinc(t);dt.x:=df.x+hi,1; dt.y:=df.y+hi,2;coldt.x,dt.y:=color;end;/ifinc(f);until ft;/repeatend;/bfsvar/floodfilli,j:longint;begin/floodfillfor i:=0 to n+1 do begin ai,0
20、:=0; ai,m+1:=0; end;for i:=0 to m+1 do begin a0,i:=0; an+1,i:=0; end;fillchar(col,sizeof(col),0);for color:=1 to m do if coln,color=0 then bfs(n,color);for i:=1 to m do ci,1:=col1,i;fillchar(col,sizeof(col),0);for color:=m downto 1 do if coln,color=0 then bfs(n,color);for i:=1 to m do ci,2:=col1,i;end;/floodfill/floodfill all of this graphprocedure dp;var/dpi,j:longint;begin/dpf0:=0;for i:=1 to m dobeginfi:=maxint;for j:=1 to m doif (cj,2=i) and (cj,1=i) then fi:=min(fi,fcj,1-1+1);end;/for
