本文目录
- 谁给讲下2010noip的关押罪犯，最好详细点，带上程序，谢谢了
- NOIP 2010有保送是2010年考试得一等有保送，还是2010级有保送
- noip2010
- noip2010最新考试大纲
- CCF NOIP2010是干什么的
- NOIP2010
- NOIP2010普及组复赛广东二等奖分数线
- NOIP2010（Pascal提高组）复赛
- 关于NOIP2010
谁给讲下2010noip的关押罪犯，最好详细点，带上程序，谢谢了
【NOIP 2010--关押罪犯 个人题解】
【题目描述】
☆关押罪犯
描述 Description
S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式 Input Format
输入文件的每行中两个数之间用一个空格隔开。
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1《=aj《bj《N,0《cj《=1,000,000,000 且每对罪犯组合只出现一次。
输出格式 Output Format
输出共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
数据范围
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
【问题的分析】
一.首先，我们要从题目的要求出发，弄清题目所要求的值。
由于市长只会去看列表中的由大至小第一个事件的影响力，那么，我们所要求的就是这样的一个最大值。现在，题目要求这样的一个最大值要尽可能的“小”。什么意思？其实就是说，我们通过一定的分配罪犯监狱的方法分配完罪犯之后，那么对于分进两个不同的监狱中的罪犯将不存在怨气值，因而，不同的分法可能存在着不同的最大值。因而，现在我们要做的就是，找出这样的分配方法，使得其中最大的怨气值是所有可行分配方法中最小的一个值。
二.问题分析的逐步深入。
首先，我们会发现题目中有一个重要的大前提：就是S城只有两座监狱！这样的一句话，可以很明显的让我们看出本题所具有的二分图的性质，因为通过可行分配方法分配过后，所有的罪犯将会被分进两个不同的监狱，抽象起来就是二分图的模型。那么，本题是否用到了二分图的算法呢？答案是没有，因为我们真正需要的仅仅是对于二分图是否成立的一个定性的判断。
到以上，我们就有了一个粗略的想法：就是通过枚举的思想，枚举最大的边，将比它大的边删去，那么，对于剩下的图来说，如果我们能够将之划分成二分图，则当前所枚举的最大边就将是一个可行的解。并且，我们可以想到的一个判断二分图的可行方法就是宽度搜索：将图中的一个没选过的点标上1，与之相连的点标上2，然后再依次标上1,2......，当然，如果其中出现了矛盾，则说明这个图不可二分。
至此，我们得到了一个可行的算法：枚举最大的边，宽搜判断二分图。 时间的复杂度约为O（M*N）。朴素的30分。
进一步思考，发现在枚举最大边时，我们可以想到的一个很好的优化，那就是：二分枚举！因为，我们可以通过排序，使得边由小到大递增，那么边的顺序就具有了单调性，因而，我们可以采用二分的思想来枚举。效率就会立马提升一个档次。
完善后：时间复杂度约为O（N*logM）。从理论上将已经可以通过全部的点了。
然而细细的想后，会发现在我们判断二分图的时候，每次都是在一个新的图上判断二分图能否成立，因而，判断一遍二分图约是O（N）级别的效率，这样可以看出，效率被花在的二分图的判断上。那么，我们是否可以改善一下判断的方法呢？
再次回顾一下题目中的大前提，我们发现：罪犯被分在了两个监狱，也即是分成了两类！同类在一个监狱！我们可以将每一类之抽象成一个集合。
那么在动态维护每一类的对象，以及便于查找确定每个对象所在类别的数据结构是什么呢？很明显：并查集！
想到并查集之后，问题就简化了许多。现在我们可以采取的解决办法就是：将所有的边排序，然后由大到小将每条边一次删去，对于每一条删去的边来说，边上所连接的两个点需要被分在两个不同的集合之中（即将这两个罪犯分在不同的监狱）。当我们在删去边的时候，发现该边上所连接的两个点已经在同一类集合之中了，那么此时，这条边就是不可被删去的。也就是最终的解。时间复杂度约为O（5*M）（该常数是并查集的效率）
【算法的实现】
对于并查集，我们可以采用的办法由两种：一种是同类合并。另一种是关系合并。
以下以关系合并为例，讲解以下并查集实现的过程：
0-代表同一个监狱（朋友） 1-代表不同的监狱（敌对）
对于当前这条待删去的边来说，我们需要判断边上所连接的两个点是否曾经有过关系，如果不曾有过关系，则说明这两个点可以成为敌对的关系；反之，需要我们判断当前这两点的关系是否敌对，如果不敌对则说明当前这条边是不可删去的，否则是可以删去的。
路径压缩的时候，我们需要修改点的父亲，以及点与父亲的关系。合并的时候，我们也需要建立一个点与其父亲的关系。（在个人标程中有详细的说明。）
【个人标程】
以下是个人标程，供大家参考：
program prison;
const
maxn=20000; maxm=100000;
var
n,m:longint;
f,s:array[0..maxn+1] of longint;
a,b,c:array[0..maxm+1] of longint;
function findsets(k:longint):longint;
var
y:longint;
begin
if f[k]《》k then
begin
y:=f[k]; f[k]:=findsets(y); {路径的压缩}
s[k]:=(s[k]+s[y]) mod 2; {在路径压缩中正确的建立与新的父亲的新的关系}
end;
exit(f[k]);
end;
procedure combinesets(a,b:longint);
begin
s[f[a]]:=(s[a]+1) mod 2; {建立a的父亲与b的关系，1为敌人，0为朋友}
f[f[a]]:=b; {改变a的父亲的对象，为b}
end;
procedure work;
var
i,sa,sb:longint;
begin
for i:=m downto 1 do {枚举每条边，进行二分图的判断}
begin
sa:=findsets(a[i]); sb:=findsets(b[i]);
if sa=sb then
begin
if s[a[i]]=s[b[i]] then {当二者之前发生过关系，并且现在的关系和之前的关系相矛盾，则说明当前的为输出解}
begin
writeln(c[i]);
exit;
end;
end
else combinesets(a[i],b[i]); {否则将二者合并，建立关系}
end;
writeln(0);{删去所有的边后仍然符合条件，则说明此时应当输出0}
end;
procedure qsort(l,r:longint); {将读入的边按照大小排序}
var
i,j,x,y:longint;
begin
i:=l; j:=r; x:=c[(l+r) div 2];
repeat
while c[i]《x do inc(i);
while c[j]》x do dec(j);
if not (i》j) then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=b[i]; b[i]:=b[j]; b[j]:=y;
y:=c[i]; c[i]:=c[j]; c[j]:=y;
inc(i); dec(j);
end;
until i》j;
if j》l then qsort(l,j);
if i《r then qsort(i,r);
end;
procedure makesets; {建立一个新的并查集}
var
i:longint;
begin
for i:=1 to n do f[i]:=i;
end;
procedure reads; {读入数据}
var
i:longint;
begin
readln(n,m);
makesets;
for i:=1 to m do readln(a[i],b[i],c[i]);
end;
begin
assign(input,’prison.in’);
reset(input);
assign(output,’prison.out’);
rewrite(output);
reads;
qsort(1,m);
work;
close(input);
close(output);
end.
NOIP 2010有保送是2010年考试得一等有保送，还是2010级有保送
如果你刚中考完，你就和我一样杯具了
就是2011年秋季上高中的都没保送
除非你NOI金牌
你要是2010毕业的有保送
noip2010
不好意思啦，你没说清楚是提高还是普及，然后我也有点急，就随便拉了个解题报告。
三、导弹拦截
再次见到导弹拦截，颇感亲切，但是这次的导弹拦截，加入了立体环节，也从借用原题概念，让一个不存在的动态规划方法，影响解题思路。
其实，题目的核心解题思想还是贪心和枚举。只不过要枚举的有些策略而已。我也曾试过了，用单位长度去枚举两个点的半径，结果残酷的只过了两个点。还是经过学生的解释，明白了排序后的贪心策略。所以，向学生学习，也是老师的必修课程。我再次强调，我经常向学生学习，教学相长，不外乎如此。所以，希望更多的老师，能够时常放下自己的架子和身份，多多向学生请教，我们共同的成长。
按照到第一个点的距离平方排序之后，就可以不断让最远的点，不用离开第一点半径，进入第二点半径。在这个过程中，第一点半径逐渐缩小，第二点半径，可能发生增大。就需要一步步统计出，两个半径平方的最小值。最终达到题目要求。
因为考虑到点的数量是100000，所以，无比需要使用快速排序。题目如果想写的较为简洁，还是使用结构体比较方便。
首先定义一个结构体，包括x,y,jr1（距离第1点半径平方）,jr2（距离第2点半径平方）。
struct dian
{
int x;
int y;
int j1r;
int j2r;
}d;
这里面顺便定义了一个10万数量级的数组。
快速排序的函数：
void qsort(int s, int e)
{
dian t;
int l, r;
if (s 》= e) return ;
l = s;
r = e;
t = d[s];
while (l 《 r)
{
while (l 《 r && d[r].j1r 》= t.j1r) r--;
d[l] = d[r];
while (l 《 r && d[l].j1r 《= t.j1r) l++;
d[r] = d[l];
}
d[r] = t;
qsort(s, r - 1);
qsort(r + 1, e);
}
然后就是逐渐退出和更新半径的过程了：
r = d[n].j1r;
m2 = 0;
for (i = n ; i 》= 1 ; i--)
{
if (d[i].j2r 》 m2) m2 = d[i].j2r;
tr = d[i - 1].j1r + m2;
if ( r 》 tr ) r = tr;
}
最后r即为最小消耗。
以上是 王祺磊 的结题报告。
如您愿意给我（王祺磊）发邮件，欢迎发邮件至：fatship@163.com与我交流。
-noip2010
noip2010最新考试大纲
noip全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces简称NOIP)自1995年至今已举办13次。每年由中国计算机学会统一组织。 NOIP是在同一时间、不同地点以各省市为单位由特派员组织。每年的9月1—10日报名，初赛定于每年10月的最后第二个星期六下午，复赛定于每年11月的最后第二个星期六举行。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛以通用和实用的计算机知识为考试内容，重在考察基础与实用的知识，以笔试为主。复赛为程序设计。参加初赛者须达到一定分数线后才有资格参加复赛。各省市、自治区都应参加联赛，参加联赛是参加NOI的必要条件。联赛命题宗旨全国青少年信息学奥林匹克联赛（NOIP）是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。竞赛的目的是为了在更高层次上推动普及。本竞赛及其相关活动遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加。本活动不和现行的学校教学相冲突，也不列入教学计划，是课外性质的因材施教活动。参加者可为初高中学生或其他中等专业学校的青少年。普及的内容涉及．计算机的基本组成；．计算机工作的基本原理；．计算机程序设计的基本方法；．至少一门高级程序设计语言；．程序设计中常用的数据结构。普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些本质和核心的东西有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。对学生的能力培养注重．想象力与创造力；．对问题的理解和分析能力；．数学能力和逻辑思维能力；．对客观问题和主观思维的口头和书面表达能力；．人文精神。包括与人的沟通和理解能力，团队精神与合作能力，恒心和毅力，审美能力等。竞赛形式和成绩评定联赛分两个年龄组：初中组和高中组。每组竞赛分两轮：初试和复试。．初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Basic（2005年被取消）、C/C++或Pascal。各省市初试成绩在本赛区前百分之二十的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的最后第二个星期六下午 2:30 - 4:30举行。．复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用 Basic（2005年后被取消）、Pascal、C/C++或Java。各省市竞赛的等第奖在复试的优胜者中产生。时间为 3 小时。只进行一试，约在当年的11 月的第三个周六进行。试题形式每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。* 初试：初试全部为笔试，满分100分。试题由四部分组成：1、选择题：共20题，每题1．5分，共30分。每题有5个备选方案；前10个题为单选题且每题有且只有一个正确答案），后 10题为复选题（即每题有1至5个正确答案，只有全部选对才得分）。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。2、问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。4、程序完善题：共 2题，每题 14分，共 28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些
-程序
CCF NOIP2010是干什么的
CCF： 中国计算机学会,英文全称为China Computer Federation,简称CCF,成立于1962年，是中国计算机科学与技术领域群众性学术团体，属一级学会，独立法人单位，是中国科学技术协会的成员，是noip的举办方。
noip2010是2010年的信息学联赛。
全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，简称NOIP）自1995年至今已举办17次。每年由中国计算机学会统一组织。 NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。
noip一等奖原本是有保送和加分政策的。 2010年11月19日，教育部宣布取消了各项奥林匹克竞赛全国决赛一等奖以下的高校保送资格，改由所在地招生委员会决定是否给予20分及以下的加分。调整政策从2011年秋季进入高中阶段一年级的学生开始适用，2010年(含)以前已进入高中阶段学习的学生，仍可适用调整前的相关政策。 目前已经完全取消保送和加分政策（只有下一届高三学生仍有此政策）。
-noip2010
NOIP2010
NOIP复赛考生须知
本须知需在赛前发给考生本人，并由考场主监考人于开赛前15分钟向选手宣读。
除经允许的、必须的竞赛用品外，选手不得将书包、手机、U盘、书、纸等带入考场，一经发现，取消本次竞赛资格。
选手进人考场后按指定位置就座。如发现问题，向监考人示意协助解决。
选手入座后应仔细核对考桌上的参赛标签，看内容是否与本人的信息一致，如有错误须立刻上报监考人员，否则视为默认同意，赛后不得更改。选手须将身份证和准考证放在考桌上参赛标签旁，以便监考人员查验。
开始15分钟后不得进人考场，以旷考处理；开考60分钟内，选手不得退出考场，退场后不得返回考场。
监考人公布密码后，选手自行解密试题，并在已有的目录下(已由竞赛组织方事先建立，目录名为选手的参赛编号)，由选手为每道试题再单独建立一个子目录，子目录名与对应的试题英文名相同（英文小写，参见试题封面页）。选手提交的每道试题的源程序必须存放在相应的子目录下。未按规定建立子目录、建立的子目录名出现错误、或提交的源程序没有存放在相应的子目录下等都会导致选手成绩为0分，责任由选手承担。
考试期间须保持安静，不准相互交谈，如有疑问，选手可举手示意，询问监考人员。如有传递纸条、替他人代考等违纪作弊行为，该选手将被立刻取消参赛资格，并从次年算起被禁赛3年。
选手听到监考人员竞赛结束的指令后，须停止答卷，待监考人员检查无误后离开考场，不得在考场逗留。如竞赛结束的指令下达后继续答题，该选手成绩以零分记。
除CCF规定的名额外，任何一位选手均可申请由CCF NOI科学委员会进行复测，但需缴纳费用50元。申请复测属自愿，选手可直接想CCF提出申请。
选手如发现监考人员及相关人员在竞赛过程中有违纪行为或有影响公平竞赛的行为，可向主办单位署名投诉（邮件：noi@ict.ac.cn），主办单位将严格为投诉者保密。
-程序
NOIP2010普及组复赛广东二等奖分数线
CCF关于NOIP2010奖项评定的公告及获奖名单公示
CCF NOI科学委员会、竞赛委员会根据NOIP2010复赛全部选手成绩，划定了各奖项的分数线，现公告如下：
1．NOIP2010复赛提高组一等奖全国基准线为200分，每个省的分数线根据其应分配名额划定。对未达到基准线的省份的获奖分数线适当下调，但获奖名额相应减少。对达到或超过复赛提高组一等奖基准线、但由于所在省一等奖名额有限未能获得一等奖的选手，可向CCF申请颁发成绩证明。
2．复赛提高组二等奖全国最低分数线为120分。复赛提高组一等奖分数线在基准线（200分）以上的省，复赛提高组二等奖须满足120分的最低分数线，但获奖名额不得超过该省一等奖获奖人数（含往届获奖）的三倍；复赛提高组一等奖分数线在基准线（200分）以下的省，二等奖须满足120分的最低分数线，但获奖名额不得超过省一等奖获奖人数（含往届获奖）的两倍。边界同分时均可获奖。
3．普及组复赛一等奖全国最低分数线为200分。满足此条件的选手均可获奖。
以上奖项的证书均由主办单位CCF颁发，获奖选手可自愿向CCF申请证书。提高组复赛一等奖和成绩证明由CCF直接受理，其余证书或由CCF受理，或委托省组织单位受理（即将公布）。
现对全国NOIP2010复赛提高组一等奖名单进行公示。公示期内，如对名单有疑问，请发邮件至本学会反映（ noi@ict.ac.cn ），同时，签字后发传真至010-6252 7485。质疑者须署名并附现学习或工作单位。不符合上述要求者本学会不予受理。
公示期为：2010年12月8日至2010年12月15日12:00。
此公告。
中国计算机学会
2010年12月8日
-noip2010
NOIP2010（Pascal提高组）复赛
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 1 页 共 7 页
全国信息学奥林匹克联赛（NOIP2010）复赛
提高组（请选手务必仔细阅读本页内容）
一．题目概况
中文题目名称 机器翻译 乌龟棋 关押罪犯 引水入城
英文题目与子目录名 translate tortoise prison flow
可执行文件名 translate tortoise prison flow
输入文件名 translate.in tortoise.in prison.in flow.in
输出文件名 translate.out tortoise.out prison.out flow.out
每个测试点时限 1秒 1秒 1秒 1秒
测试点数目 10 10 10 10
每个测试点分值 10 10 10 10
附加样例文件 有 有 有 有
结果比较方式 全文比较（过滤行末空格及文末回车）
题目类型 传统 传统 传统 传统
二．提交源程序文件名
对于pascal语言 translate.pas tortoise.pas prison.pas flow.pas
对于C语言 translate.c tortoise.c prison.c flow.c
对于C++语言 translate.cpp tortoise.cpp prison.cpp flow.cpp
三．编译命令（不包含任何优化开关）
对于pascal语言 fpc translate.pasfpc tortoise.pasfpc prison.pas fpc flow.pas
对于C语言
gcc -o translate
translate.c -lm
gcc -o tortoise
tortoise.c -lm
gcc -o prison
prison.c -lm
gcc -o flow
flow.c -lm
对于C++语言 g++ -o translate
translate.cpp -lm
g++ -o tortoise
tortoise.cpp -lm
g++ -o prison
prison.cpp -lm
g++ -o flow
flow.cpp -lm
四．运行内存限制内存上限 128M 128M 128M 128M
注意事项：
1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内存1G，上述时限以此配置为准。
各省在自测时可根据具体配置调整时限。
换页
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 2 页 共 7 页
1．机器翻译
(translate.pas/c/cpp)
【问题描述】
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义
来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，
软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中
文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入
内存前，如果当前内存中已存入的单词数不超过M?1，软件会将新单词存入一个未使用的
内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，
存放新单词。
假设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多
少次词典？假设在翻译开始前，内存中没有任何单词。
【输入】
输入文件名为translate.in，输入文件共2行。每行中两个数之间用一个空格隔开。
第一行为两个正整数M和N，代表内存容量和文章的长度。
第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文
单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
【输出】输出文件translate.out共1行，包含一个整数，为软件需要查词典的次数。
【输入输出样例1】
translate.in translate.out
3 7
1 2 1 5 4 4 1
5
【输入输出样例1说明】
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
空：内存初始状态为空。
1． 1：查找单词1并调入内存。
2． 1 2：查找单词2并调入内存。
3． 1 2：在内存中找到单词1。
4． 1 2 5：查找单词5并调入内存。
5． 2 5 4：查找单词4并调入内存替代单词1。
6． 2 5 4：在内存中找到单词4。
7． 5 4 1：查找单词1并调入内存替代单词2。
共计查了5次词典。
换页
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 3 页 共 7 页
【输入输出样例2】
translate.in translate.out
2 10
8 824 11 78 11 78 11 78 8 264
6
【数据范围】
对于10%的数据有M=1，N≤5。
对于100%的数据有0≤100，0≤1000。
2．乌龟棋
(tortoise.pas/c/cpp)
【问题描述】
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一
的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
……
1 2 3 4 5 ……N
乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型
的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡
片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择
一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到
该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的
分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡
片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到
多少分吗？
【输入】
输入文件名tortoise.in。输入文件的每行中两个数之间用一个空格隔开。
第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数，a1a2
……aN
，其中ai表示棋盘第i个格子上的分数。第3行M个整数，b1b2
……bM
，表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片，即N?1=∑
M
ib
1
。
【输出】
输出文件名tortoise.out。
换页
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 4 页 共 7 页
输出只有1行，1个整数，表示小明最多能得到的分数。
【输入输出样例1】
tortoise.in tortoise.out
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
73
【输入输出样例1说明】
小明使用爬行卡片顺序为1，1，3，1，2，得到的分数为6+10+14+8+18+17=73。注意，
由于起点是1，所以自动获得第1格的分数6。
【输入输出样例2】
tortoise.in tortoise.out
13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1
455
【数据范围】
对于30%的数据有1
≤
N
≤
30，1
≤
M
≤
12。
对于50%的数据有1≤N≤120，1
≤
M
≤
50，且4种爬行卡片，每种卡片的张数不会超
过20。
对于100%的数据有1≤N≤350，1≤M≤120，且4种爬行卡片，每种卡片的张数不会
超过40；0≤ai≤100，1≤i≤N；1≤bi≤4，1≤i≤M。输入数据保证N?1=
∑
M
ib
1
。
3．关押罪犯
(prison.pas/c/cpp)
【问题描述】
S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极
不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨
气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之
间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并
造成影响力为c的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，
然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力，
如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在
两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只
要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那
么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多
换页
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 5 页 共 7 页
少？
【输入】
输入文件名为prison.in。输入文件的每行中两个数之间用一个空格隔开。
第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨
气值为cj。数据保证Nba
jj
≤1，0000000001
0≤
jc
，且每对罪犯组合只出现一
次。
【输出】
输出文件prison.out共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱
中未发生任何冲突事件，请输出0。
【输入输出样例】
prison.in prison.out
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
【输入输出样例说明】
罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件
影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。
【数据范围】
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
2 1
3 4
1805 6618
2534 3512
12884
28351 2 1
3 4
2534 3512
换页
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 6 页 共 7 页
4.引水入城
(flow.pas/c/cpp)
【问题描述】
湖泊
沙漠
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政
区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城
市，每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施
有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的
蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通
过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是
存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。
由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利
设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干
旱区中不可能建有水利设施的城市数目。
【输入】
输入文件名为flow.in。输入文件的每行中两个数之间用一个空格隔开。
输入的第一行是两个正整数N和M，表示矩形的规模。
接下来N行，每行M个正整数，依次代表每座城市的海拔高度。
【输出】
输出文件名为flow.out。
输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少
建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有
几座干旱区中的城市不可能建有水利设施。
【输入输出样例1】
flow.in flow.out
2 5
9 1 5 4 3
8 7 6 1 2
11
换页
全国信息学奥林匹克联赛（NOIP2010）复赛 提高组
第 7 页 共 7 页
【样例1说明】
只需要在海拔为9的那座城市中建造蓄水厂，即可满足要求。
【输入输出样例2】
flow.in flow.out
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
13
【样例2说明】
湖泊
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
沙漠
上图中，在3个粗线框出的城市中建造蓄水厂，可以满足要求。以这3个蓄水厂为源头
在干旱区中建造的输水站分别用3种颜色标出。当然，建造方法可能不唯一。
【数据范围】
本题共有10个测试数据，每个数据的范围如下表所示：
测试数据编号 能否满足要求 N M
1 不能 ≤ 10 ≤ 10
2 不能 ≤ 100 ≤ 100
3 不能 ≤ 500 ≤ 500
4 能 = 1 ≤ 10
5 能 ≤ 10 ≤ 10
6 能 ≤ 100 ≤ 20
7 能 ≤ 100 ≤ 50
8 能 ≤ 100 ≤ 100
9 能 ≤ 200 ≤ 200
10 能 ≤ 500 ≤ 500
对于所有的10个数据，每座城市的海拔高度都不超过10
6
。
换页
-程序
关于NOIP2010
一般在每年九月十日 以前通过学校向市科协报名，如果学校没有组织也没关系，一般只要跟科学老师讲一下，他们会替你报名的，但要记住，你要在九月十日前再向他们确认一下，因为老师可能会很忙，会忘记的，因为到教师节了。
如果你的学校没有组织，说明你们的老师不看好你们。还有，你已高三了还不知道如何报名，说明你以前还没考过。普及组是初中阶段比的。你只能参加提高组了。要想有保送资格，一定要获得提高组省赛一等奖，也就是复赛一等奖。如果是自学的，很难达到这个水平的。http://hi.baidu.com/wznoip
-noip2010
