下载文档原格式
第一题题库NOIP20071．统计数字(count.pas/c/cpp)【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。
已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
【输入】输入文件count.in包含n+1行：第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。
【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。
每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
【输入输出样例】【限制】40%的数据满足：1<=n <=100080%的数据满足：1<=n <=50000100%的数据满足：1<=n <=200000，每个数均不超过1 500 000 000（1.5*109）NOIP20081. 笨小猴(wird.pas/c/cpp)【问题描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。
但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn 是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn 是一个质数，那么笨小猴就认为这是个Lucky Word ，这样的单词很可能就是正确的答案。
【输入】输入文件word.in 只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
【输出】输出文件word.out 共两行，第一行是一个字符串，假设输入的的单词是Lucky Word ，那么输出“Lucky Word ”，否则输出“No Answer ”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn 的值，否则输出0。
第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。
每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。
因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如11月初津津手中还有83元，妈妈给了津津300元。
津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。
到了11月月末，津津手中会剩下3元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。
有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。
如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。
如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。
【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。
【输出文件】输出文件save.out包括一行，这一行只包含一个整数。
如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。
【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。
Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。
一共有n 张地毯，编号从1 到n。
现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。
注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】输入文件名为 carpet.in。
输入共 n+2 行。
第一行，一个整数 n，表示总共有n 张地毯。
接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。
第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。
【输出】输出文件名为 carpet.out。
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。
【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。
【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。
【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。
【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。
置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。
注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。
第九届分区联赛提高组初赛试题（提高组PASCAL 语言二小时完成）●●全部答案均要写在答案卷子上，写在试卷纸上一律无效●●一.单项选择题 （共10题，每题1.5分，共计15分。
每题有且仅有一个正确答案.）。
1. 图灵 (Alan Turing) 是 （ ）。
A） 美国人 B） 英国人 C） 德国人 D） 匈牙利人 E） 法国人2. 第一个给计算机写程序的人是（ ）。
A） Alan Mathison Turing B） Ada Lovelace C） John von Neumann D） John Mc-Carthy E） Edsger Wybe Dijkstra3. 十进制数2003等值于二进制数（ ）。
A） 010******* B） 10000011 C） 110000111 D） 11111010011 E） 11110100114. 假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A∧B∨C∧D的值是（ ）。
A） ture B） false C） 0 D） 1 E） NULL5. 一个高度为h 的二叉树最小元素数目是（ ）。
A） 2h+1 B） h C） 2h-1 D） 2h E） 2h-16. 已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（ ）。
A） 5 B） 41 C） 77 D） 13 E） 187. 下面一段程序是用（ ）语言书写的。
int func1(int n){int i,sum=0;for(i=1;i<=n;i++)sum+=i*i;return sum;}A) FORTRAN B) PASCAL C) C D) PROLOG E) BASIC8. 设全集E={1，2，3，4，5}，集合A={1，4}，B={1，2，5}，C={2，4}，则集合（A ∩B）∪～C 为（ ）。
第二十届全国青少年信息学奥林匹克竞赛NOI2003第二试有关附加文件的信息，请参看具体的题目说明。
数据生成器【题目背景】小明在做NOI2003练习赛的《幸福的老鼠》时觉得题目太简单了，于是对原题做了一些扩展：●将原题的N从20扩展到200000。
●将原题经过一条街道需要的时间改为Ti（1 £ Ti £ 1000000000）分钟（i为街道的编号）。
●增加了一个条件：小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。
即使这样，他仍然很快地做了出来。
于是，小明打算做一些输入文件来测试他的程序。
现在他已经生成了一些符合题意的图，不过为了增大测试数据的难度，他希望你能帮他选取一组X、Y、Z，使老鼠拿到礼物的时间尽可能地大。
【小明扩展的题目（注意，你并不需要解决此题）】幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。
现在Jerry打算从自己家X出发，先到小狗家Y（因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离），再到大狗家Z，将两份礼物取回。
卡通城由N（3 £ N £ 200000）个居住点和N-1条连接居住点的双向街道组成，经过第i 条街道需花费Ti（1 £ Ti £ 1000000000）分钟的时间。
可以保证，任两个居住点间都存在通路。
不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。
现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？【任务描述】定义：令|AB|表示卡通城中从A点走到B点需要的最少时间。
给出卡通城的地图，找到一组X、Y、Z，使得：|XY|≤|XZ||XY|+|YZ|最大。
并求出此时|XY|+|YZ|的值。
【输入文件】输入文件jerrygen.in第一行是两个整数N（3 £ N £ 200000）和M（M=N-1），分别表示居住点总数和街道总数。
从第2行开始到第N行，每行给出一条街道的信息。
第九届全国(quán ɡuó)青少年信息学奥林匹克联赛（NOIP2003）提高(tí gāo)组试题(2003年11月29日三小时(xiǎoshí)完成)一. 传染病控制(kòngzhì)问题(wèntí)背景近来，一种新的传染病肆虐全球，蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病蔓延。
不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。
于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法来控制疾病传播。
经过WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究清楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
问题描述：研究表明，这种传染病的传播具有两种很特殊的性质：第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X不会得病。
第二是，这种疾病的传播有同期性，在一疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力，并且也们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。
但是，麻烦还没有结束。
由于蓬莱国疾控中心人手不够，同时没有强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。
当不可能有健康人被感染时，疾病就中止传播。
所以，蓬莱国疾控中心要制定一个切断传播途径的顺序，以使尽量少的人被感染。
你的程序要针对给定的树，找出合适的切断顺序。
输入格式：输入格式的第一行是两个整数N（1<=n<=300）和p.接下来是p行，每一行有两个整数i和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。
历年NOIP(普及组)难度分析 by Climber.pINOIP提高组复赛考察点详细分析动态规划：12 模拟：10数学：5 图论：4搜索：4 构造：3贪心：2【动态规划】平均难度系数：0.55此项为历届NOIP考察次数最多的知识点。
主要有 1.区间模型 2.子序列模型 3.资源分配模型以及一些简单的多维状态设计技巧。
动态规划可以与图,树,高精度等知识点配合出题。
【模拟】平均难度系数：0.76平均每届NOIP都会出现1个模拟题。
这种题一般算法很简单，需要选手细心理解题目意思，注意细节。
考察选手的代码实现能力。
【数学】平均难度系数：0.46需要掌握质数及其性质，基础的实属操作，加法原理和乘法原理。
此类题需要选手对数学规律的灵感。
【图论】平均难度系数：0.50历届考察点基本上都是 1.最短路问题和 2.特殊图的性质。
特殊图包括树，拓扑图，二分图等。
历届NOIP在图论上的考察并不是很多。
【搜索】平均难度系数：0.38历届搜索题一般都比较难，搜索算法本身简单，于是题目会提高选手对其他方面的要求。
主要有搜索优化和模拟。
写搜索题时应该以尽量多得分为目标。
【构造】平均难度系数：0.27构造类题目一般没有明确的算法，需要选手仔细分析题目的实质，并得出解法。
这个解法通常不是唯一的。
有时一个好的贪心可以得相当多的分。
有时搜索剪枝可以很大的提高效率。
同样以多得分为目标。
【【贪心】平均难度系数：0.75此类题需要选手对算法的直觉，贪心正确性一旦被证明，通常题目就简单了。
第一题：神经网络【试题分析】一、题意分析1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。
输出输出层中信号大于零的节点编号和信号大小。
（节点编号由小到大）如果没有满足条件的编号则输出NULL。
信号传递公式：∑∈-=Ei jijjiiUCWC),(公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。
当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。
当神经元处于兴奋状态时，下一秒它会向其它神经元传递信号，信号的强度为Ci。
2、输入：两个整数n（1≤n≤20）和p。
n表示节点的个数；p表示有向边的条数。
下面n行表示1-n号节点的状态和阈值。
下面p行表示有向边及其权值。
3、输出：输出输出层状态大于零的神经元编号和状态，并且按照编号有小到大顺序输出！若输出层的神经元最后状态小于等于0，则输出NULL。
二、问题分析1、题目中给出每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。
所以不必进行拓扑排序，一层一层的向下传递信号即可。
输出最后一层中信号大于零的节点编号。
2、可以建立一个队列，将输入层节点入队。
3、取队首节点出队，寻找此节点有向边，如果有有向边：1）则记录此节点不是输出层；2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。
再出队再传递，直至全部出队。
注意：1）输入层可以是输出层。
2）信号传递公式中只减一次U[i]。
【程序清单】Program network;ConstInName='network.in';OutName='network.out';MM=100;VarInFile,OutFile:Text;C,U:Array[1..MM] Of LongInt;Map:Array[1..MM,1..MM] Of LongInt;Flag:Array[1..MM,1..MM] Of Boolean;IsOut:Array[1..MM] Of Boolean;Queue:Array[1..MM] Of LongInt;N,P,i,Int1,Int2,Head,Rear:LongInt;IsInQueue:Array[1..MM] Of Boolean;IsNull:Boolean;BeginAssign(InFile,InName);Reset(InFile);ReadLn(InFile,N,P);For i:=1 To N Do ReadLn(InFile,C[i],U[i]); FillChar(Flag,SizeOf(Flag),False);For i:=1 To P Do BeginRead(InFile,Int1,Int2);ReadLn(InFile,Map[Int1,Int2]);Flag[Int1,Int2]:=True;End;Close(InFile);FillChar(IsOut,SizeOf(IsOut),True);FillChar(IsInQueue,SizeOf(IsInQueue),False); Head:=1; Rear:=1;For i:=1 To N Do BeginIf C[i]>0 Then BeginQueue[Rear]:=i;Inc(Rear);IsInQueue[i]:=True;EndElse C[i]:=-U[i];End;While Head<Rear Do BeginFor i:=1 To N DoIf Flag[Queue[Head],i] Then BeginIf C[Queue[Head]]>0 Then BeginInc(C[i],Map[Queue[Head],i]*C[Queue[Head]]);If Not IsInQueue[i] Then BeginQueue[Rear]:=i;Inc(Rear);IsInQueue[i]:=True;End;End;IsOut[Queue[Head]]:=False;End;Inc(Head);End;Assign(OutFile,OutName);Rewrite(OutFile);IsNull:=True;For i:=1 To N DoIf IsOut[i] ThenIf C[i]>0 Then BeginWriteLn(OutFile,i,' ',C[i]);IsNull:=False;End;If IsNull Then WriteLn(OutFile,'NULL');Close(OutFile);End.第二题：侦探推理【试题分析】一、题意分析1、任务描述：M个人参加游戏，每人提供一句或多句证言，共P句证言。
其中N个人始终说假话，其余的人始终说真话。
请你通过证言判断出谁是罪犯。
证词中出现的其它话，都不列入逻辑推理的内容。
2、输入：第一行有三个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）：M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证人的综述。
接下来M行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。
往后有P行，每行开始是某个同学的名字，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式，证词每行不会好过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。
3、输出：如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出Impossible。
二、问题分析1、根据题意可知可以利用枚举法完成。
枚举罪犯和今天是星期几。
满足N 个人始终说谎话和M-N个人始终说真话的条件，就可以确定罪犯。
2、首先利用字符串操作将证言转化成计算机可表示的信息。
1）定义Guilty:Array[1..MM,1..MM] Of Integer;{-1..1}FillChar(Guilty,SizeOf(Guilty),0) 初值为0Guilty[i,j]=-1：表示第i个人说第j个人不是罪犯Guilty[i,j]= 1：表示第i个人说第j个人是罪犯其中包含Guilty[i,i]即第i个人说自己是不是罪犯注意：Guilty不可以自相矛盾。
2）定义WhatDay:Array[1..MM,1..7] Of Boolean;FillChar(WhatDay,SizeOf(WhatDay),False)WhatDay[i,j]:=True :表示第i个人说过j是星期几3、枚举罪犯和星期几，判断每句证言是真是假，统计说真假证言的人数。
注意：有可能某人又说过真话，又说过假话。
4、根据题目要求输出罪犯编号或Cannot Determine或Impossible。
【程序清单】Program logic;ConstInName='logic.in';OutName='logic.out';MM=20;DayState:Array[1..7] Of String=('is Monday. #','is Tuesday. #','is Wednesday. #','is Thursday. #','is Friday. #','is Saturday. #','is Sunday. #');cImpossible=-1;cCannotDetermine=-2;VarInFile,OutFile:Text;M,N,P:Integer;Name:Array[1..MM] Of String;Guilty:Array[1..MM,1..MM] Of Integer;{-1..1}WhatDay:Array[1..MM,1..7] Of Boolean;i,j:Integer;IsGuilty:Array[1..MM] Of Boolean;Ans,AnsC:Integer;Procedure Print(ID:Integer);BeginAssign(OutFile,OutName);Rewrite(OutFile);If ID=cImpossible ThenWriteLn(OutFile,'Impossible')Else If ID=cCannotDetermine ThenWriteLn(OutFile,'Cannot Determine')Else WriteLn(OutFile,Name[ID]);Close(OutFile);Halt;End;Procedure SetGuilty(CurID,NextID,NewValue:Integer); BeginIf Guilty[CurID,NextID]=0 ThenGuilty[CurID,NextID]:=NewValueElse If Guilty[CurID,NextID]<>NewValue ThenPrint(cImpossible);End;Procedure ReadStatement;Vari,j,CurID,NextID:Integer;CurStr,CurName:String;BeginFor i:=1 To P Do BeginReadLn(InFile,CurStr);CurStr:=CurStr+' #';CurName:=Copy(CurStr,1,Pos(':',CurStr)-1); CurStr:=Copy(CurStr,Pos(':',CurStr)+2,255); CurID:=0;For j:=1 To M DoIf CurName=Name[j] Then BeginCurID:=j;Break;End;If CurID=0 Then Continue;If CurStr='I am guilty. #' ThenSetGuilty(CurID,CurID,1)Else If CurStr='I am not guilty. #' ThenSetGuilty(CurID,CurID,-1)Else BeginCurName:=Copy(CurStr,1,Pos(' ',CurStr)-1); CurStr:=Copy(CurStr,Pos(' ',CurStr)+1,255); If CurName='Today' Then BeginFor j:=1 To 7 DoIf CurStr=DayState[j] Then BeginWhatDay[CurID,j]:=True;Break;End;EndElse BeginNextID:=0;For j:=1 To M DoIf CurName=Name[j] Then BeginNextID:=j;Break;End;If NextID=0 Then Continue;If CurStr='is guilty. #' ThenSetGuilty(CurID,NextID,1)Else If CurStr='is not guilty. #' Then SetGuilty(CurID,NextID,-1);End;End;End;End;Function Check(CurGuilty,CurDay:Integer):Boolean;VarSayT,SayF:Array[1..MM] Of Boolean;i,j,TCount,FCount:Integer;BeginFillChar(SayT,SizeOf(SayT),False);FillChar(SayF,SizeOf(SayF),False);For i:=1 To M Do BeginIf Guilty[i,CurGuilty]=1 ThenSayT[i]:=TrueElse If Guilty[i,CurGuilty]=-1 Then SayF[i]:=True;End;For i:=1 To M DoFor j:=1 To M DoIf j<>CurGuilty Then BeginIf Guilty[i,j]=1 ThenSayF[i]:=TrueElse If Guilty[i,j]=-1 ThenSayT[i]:=True;End;For i:=1 To M DoIf WhatDay[i,CurDay] Then SayT[i]:=True; For i:=1 To M DoFor j:=1 To 7 DoIf j<>CurDay ThenIf WhatDay[i,j] Then SayF[i]:=True; For i:=1 To M DoIf SayT[i] And SayF[i] Then BeginCheck:=False;Exit;End;TCount:=0; FCount:=0;For i:=1 To M Do BeginIf SayT[i] Then Inc(TCount);If SayF[i] Then Inc(FCount);End;If (FCount>N) Or (M-TCount<N) Then Begin Check:=False;Exit;End;Check:=True;End;BeginAssign(InFile,InName);Reset(InFile);ReadLn(InFile,M,N,P);For i:=1 To M Do ReadLn(InFile,Name[i]);FillChar(Guilty,SizeOf(Guilty),0);FillChar(WhatDay,SizeOf(WhatDay),False);ReadStatement;Close(InFile);FillChar(IsGuilty,SizeOf(IsGuilty),False);For i:=1 To M DoFor j:=1 To 7 DoIsGuilty[i]:=IsGuilty[i] Or Check(i,j);AnsC:=0;For i:=1 To M DoIf IsGuilty[i] Then BeginInc(AnsC);Ans:=i;End;If AnsC=0 ThenPrint(cImpossible)Else If AnsC>1 ThenPrint(cCannotDetermine)Else Print(Ans);End.第三题：加分二叉树【试题分析】一、题意分析1、任务描述：在中序遍历为（1,2,3,…,n）的各种二叉树中，选出加分最高的一棵二叉树，输出最高加分和对此二叉树的前序遍历。
