NOIP2010题解报告(普及组&&提高组)

解析1、数字统计【思路分析】这道题属于简单题，用一个FOR把数都检查一遍，里面再用while剥皮看看有多少个2。

【参考程序】VarI,n,l,r,s:integer;BeginAssign(input,’two.in’);Assign(output,’two.out’);Readln(l,r);S:=0;For i:=1 to r doBeginN:=I;While n>0 doBeginIf n mod 10=2 then s:=s+1;N:=n div 10;End;End;Writeln(s);Close(input);close(output;)End.2、接水问题【思路分析】方法一：用一个数组，存放每个水龙头当前还需要多少时间装完这桶水；然后一个一个人去轮，每次找最快装完的水龙头，接着把当前轮到的那个人所需要的时间加到格子里；最后轮完以后，还要把数组里的最大值输出。

【参考程序】Vara:=array[1..10000]of integer;b:=array[1..100]of longint;m,n,i,k,t,max,min:longint;beginassign(input,'water.in');assign(output,'water.out');reset(input);rewrite(output);readln(n,m);for i:=1 to n do read(a[i]);fillchar(b,sizeof(b),0);max:=0;k:=1;while(k<=n) dobeginmin:=maxlongint;t:=0;for i:=1 to m doif b[i]<min thenmin:=b[i];t:=i;end;b[t]:=b[t]+a[k];k:=k+1;if b[t]>max then max=b[t];end;writeln(max);close(input);close(output);end.方法二：用一个数组，存放每个水龙头当前还需要多少时间装完这桶水，并按照时间长短从大到小安排好；然后一个一个去轮，显然最快装完的水龙头总是最后一个，这样只要把当前轮到的那个人所需的时间加到最后那个元素里，再把数组排序好（很明显，这里要用插入排序效率最高）；最后只要输出数组第一个元素就可以了。

NOIP2010普及组复赛解题报告(pascal)---------By 锦云第一题：two.pas本题没有什么技术含量，主要有三种方法：1．用枚举（找范围再分别处理，很麻烦）2．用分解（一步步分解，较简便）3．用先转换成字符串再做（很简便）参考程序：（在此只提供第二种解法的分解部分和第三种解法）第二种：Function fjtwo(a:integer):integer;Var cnt,tmp:integer;BeginCnt:=0;While a>0 doBeginTmp:=a mod 10;If tmp=2 then inc(cnt);Tmp:=tmp div 10;End;Fjtwo:=cnt;End;第三种：Var s:string;L,r,i,j,cnt:integer;BeginAssign(input,’two.in’);reset(input);Assign(output,’two.out’);rewrite(output);Readln(l,r);Cnt:=0;For i:=l to r doBeginString(I,s);For j:=1 to length(s) doIf s[i]=’2’ then inc(cnt);End;Writeln(cnt);Close(input);Close(output);End.第二题：water.pas本题主要是考验考生们的细心程度，从而找到最佳方案。

想了一想，本题采用模拟法，于是有了加或者减的方法。

1．减法（纯粹模拟）2．加法（更优模拟）注：减法时最好不要时间一点一点的模拟，找最小得数减。

参考程序：（本题提供较简单的写法加法）Var a:array[1..10000] of integer;N,mI,j,k:longint;BeginAssign(input,’water.in’);reset(input);Assign(output,’water.out’);rewrite(output);Readln(n,m);For i:=1 to n doRead(a[i]);For i:=m+1 to n doBeginK:=1;For j:=1 to m doIf a[j]<a[k] then k:=j;Inc(a[k],a[i]);End;K:=1;For i:=1 to m doIf a[i]>a[k] then k:=I;Writeln(a[k]);Close(input);Close(output);End.第三题：missile.pas本题实在是很难解决，n最大可以达到100000，而最优解的算法可以用搜索，但是n太大时，时间肯定不行，只好退而求其次，用贪心算法（无法得最优解但有70分，很不错了）参考程序：（贪心）Var l,n,x1,y1,x2,y2,tmpx,tmpy,max1,max2,jg1,jg2:longint;beginassign(input,'missile.in');reset(input);assign(output,'missile.out');rewrite(output);readln(x1,y1,x2,y2);readln(n);max1:=0;max2:=0;for i:=1 to n dobeginreadln(tmpx,tmpy);jg1:=sqr(abs(tmpx-x1))+sqr(abs(tmpy-y1));jg2:=sqr(abs(tmpx-x2))+sqr(abs(tmpy-y2));if (jg1>max1)and(jg2>max2) then if jg1<jg2 then max1:=jg1else max2:=jg2;end;writeln(max1+max2);close(input);close(output);end.第三题：解答本题，必须看清题意，知道以下几点：一、只需要选两次，由于比胜负靠的是双方武将中默契值最大的一对，所以除了默契值最大的一对，其他的武将都是没用的。

CSP-J (NOIP提高组) 复赛2010-2020考查内容NOIP2017提高组T4奶酪深搜、广搜、并查集T5宝藏状压DPT6列队线段树NOIP2016提高组T1玩具谜题模拟T2天天爱跑步倍增LCAT3换教室动态规划(高级)T4组合数问题前缀和、杨辉三角T5蚯蚓队列、单调性T6愤怒的小鸟状压DPNOIP2015提高组T1神奇的幻方模拟T2信息传递并查集T3斗地主动态规划(高级)、深搜T4跳石头二分T5子串滚动数组、动态规划(高级) T6运输计划二分、LCA、非递归NOIP2014提高组T1生活大爆炸版石头剪刀布模拟T2联合权值动态规划(高级)、前缀和T3飞扬的小鸟动态规划(高级)T4无线网络发射器选址枚举T5寻找道路最短路T6解方程数论、枚举NOIP2013提高组T1转圈游戏快速幂T2火柴排队归并排序、逆序对T3货车运输最小生成树、LCA、倍增T4积木大赛贪心T5花匠贪心T6华容道广搜、剪枝NOIP2012提高组T1Vigenere密码枚举、模拟T2国王游戏贪心、高精度T3开车旅行平衡树、倍增T4同余方程扩展欧几里得T5借教室线段树T6疫情控制二分、倍增NOIP2011提高组T1铺地毯模拟T2选择客栈动态规划(高级)、RMQ T3Mayan游戏T4计算系数组合数学T5聪明的质监员二分T6观光公交贪心NOIP2010提高组T1机器翻译队列T2乌龟棋动态规划T3关押罪犯二分、并查集T4引水入城广搜、动态规划T3摆渡车动态规划(高级) T4对称二叉树二叉树NOIP2017普及组序号题名考查内容T1成绩顺序结构T2图书管理员结构体排序T3棋盘深搜、剪枝T4跳*房*子二分、动态规划NOIP2016普及组序号题名考查内容T1买铅笔一重循环T2回文日期回文T3海港大模拟、队列T4魔*法*阵枚举、前缀和NOIP2015普及组序号题名考查内容T1金*币一重循环T2扫*雷*游*戏二维数组T3求和组合数学T4推销员贪心、优先队列NOIP2014普及组序号题名考查内容T1珠心算测验模拟T2比例简化枚举、gcdT3螺旋矩阵模拟、找规律T4子矩阵动态规划(高级)NOIP2013普及组序号题名考查内容T1记数问题二重循环T2表达式求值栈T3小朋友的数字动态规划(高级) T4车站分级拓扑排序NOIP2012普及组序号题名考查内容T1质因数分解一重循环、质数T2寻*宝模拟、取模T3摆花背包、动态规划T4文化之旅最短路NOIP2011普及组序号题名考查内容T1数字反转进制转换T2统计单词数字符串T3瑞士轮归并排序T4表达式的值动态规划(高级)、栈NOIP2010普及组序号题名考查内容T1数字统计二维数组T2接水问题模拟T3导*弹*拦*截贪心T4三*国*游*戏贪心、博弈。

NOIP2010初赛模拟试题（六）（普及 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●●一．单项选择题（共20题,每题1.5分,共计30分。

每题有且仅有一个正确答案。

）1、.在所有由两个1和六个0组成的8位二进制整数（补码）中，最小的数是：（）A．-127B．-64 C．-128 D．-652、.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同3、下面有效的IP地址是：（）A．202.280.130.45 B．130.192.33.45C．192.256.130.45 D．280.192.33.4564、一台具有1024*768分辨率、可显示65 536种颜色的显示器，其显示适配器（显示卡）上显示存储器容量的配置为：（）A．512K B．1MB C．大于1.6MB，小于2MB D．2MB5、进行二分法查找，则线性表（）A．必须顺序方式存储B．必须以链接方式存储，且数据元素已按值排好序C．必须以链接方式存储D．必须以顺序方式存储，且数据元素已按值排好序6、机器语言是用（）编写的。

A．二进制码B．ASCII码C．十六进制码D．国标码7、一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若 A[k]是叶子结点,则k的最小值是：（）A．51 B．50 C．49 D．488、不同的计算机，其指令系统也不相同，这主要取决于（）A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言9、计算机主机是由CPU 与（）构成的。

A．控制器B。

输入、输出设备C．运算器D．内存储器10、计算机系统总线上传送的信号有（）。

A．地址信号与控制信号B．数据信号、控制信号与地址信号C．控制信号与数据信号D．数据信号与地址信号11、计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。

全国信息学奥林匹克联赛（NOIP2010）复赛普及组（请选手务必仔细阅读本页内容）一.题目概览中文题目名称数字统计接水问题导弹拦截三国游戏英文题目名称two water missile sanguo可执行文件名two water missile sanguo 输入文件名two.in water.in missile.in sanguo.in 输出文件名two.out water.out missile.out sanguo.out每个测试点时限1秒1秒1秒1秒测试点数目10 10 10 10每个测试点分值10 10 10 10 比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统二.提交源程序文件名对于pascal语言two.pas water.pas missile.pas sanguo.pas 对于C语言two.c water.c missilel.c sanguo.c 对于C++语言two.cpp water.cpp missile.cpp sanguo.cpp三.编译命令（不包含任何优化开关）对于pascal语言fpc two.pas fpc water.pas fpc missile.pas fpc sanguo.pas对于C语言gcc –o twoTwo.c -lm gcc –o waterwater.c -lmgcc –o missileball.c -lmgcc –o sanguosanguo.c -lm对于C++语言g++ –o twotwo.cpp -lmg++ –o seatwater.cpp -lmg++ –o missilemissile.cpp -lmg++ –o sanguosanguo.cpp -lm四.运行内存限制运行内存上限128M 128M 128M 128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。

作者：钟野梓序今年Noip2010初赛刚结束，网上便铺天盖地地响起了“今年初赛好容易”“分数线一定很高，怎么办……”之类的声音。

确实，自2008年起，Noip初赛难度确有逐年下降的趋势，然而这并不是出题水平降低的缘故，相反，我认为这是中国计算机协会（下称CCF）对于N oip考核目的的审视和改变所导致的必然结果。

因此，我试图通过深入解析本届Noip初赛试囗题，来探寻这种变化下面深层的规律，从而令信息学竞赛选手能更好地备战往后数届的Noip初赛，让初赛不再成为一个问题。

由于条件所限，本文仅以Pascal语言的提高组试囗题作为对象进行分析，相对于普及组而言提高组试囗题一向具有较高的难度和较好的区分度，作为研究对象是个很好的选择；至于说语言的选择，仅是因为笔者个人选择原因。

一、概况本届题目在设置方面与往年相似，由选择题（普及组仅有单项选择题，提高组则有单项选择题与不定项选择题）、问题求解、阅读程序写结果及完善程序四大部分组成；但值得注意的是，今年提高组试囗题的分值设计与往年出现了较大的不同，除了选择题仍然是30分（15分单项+15分不定项），其余部分分值均发生了变化，其中问题求解由10分上升到15分，阅读程序由32分下降到28分，完善程序由28分下降到27分。

由于是第一年实行这种分值，目前暂时无法定言背后的含义，然而或许CCF在初赛更加重视选手的数学素质，而弱化了对于阅读程序能力的考察。

众所周知，阅读程序的能力并不能非常真实地反映选手的程序能力，并且纵观近几年的阅读程序题已没有了什么新意，这也可看做是一个“求新求变”的信号。

至于试囗题整体难度方面较上年有了明显下降，其中问题求解第一题可以看做是考察选手的语文水平，而阅读程序更是没有了以往的“死算”题（即给定若干常数，在程序中设置一系列运算过程，让选手进行阅读计算类型的题目），完善程序给定的源代码风格良好，第二题竟然还加上了注释，这不能不说就是一种降低难度的举动。

全国信息学奥林匹克联赛（NOIP2010）复赛_普及组_解题报告（pascal）全国信息学奥林匹克联赛（NOIP2010）复赛普及组解题报告1．数字统计(two.pas/c/cpp)【问题描述】请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。

比如给定范围[2, 22]，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次。

【算法思路】枚举法，依次将L至R转化为字符串，查找当中有多少个”2”.【程序代码】program two;varl,r:1..10000;i,j,h,c:longint;s:string;beginassign(input,'two.in');assign(output,'two.out');reset(input);rewrite(output);readln(l,r);c:=0;for i:=l to r dobeginstr(i,s);h:=length(s);for j:=1 to h doif s[j]='2'then c:=c+1;end;writeln(c);close(input);close(output);end.2．接水问题(water.pas/c/cpp)【问题描述】学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。

现在有n 名同学准备接水，他们的初始接水顺序已经确定。

将这些同学按接水顺序从1到n 编号，i号同学的接水量为w i。

接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。

当其中某名同学j 完成其接水量要求w j 后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。

这个换人的过程是瞬间完成的，且没有任何水的浪费。

NOIP2010第十六届初赛试题及答案(普及组Pascal)NOIP2010第十六届初赛试题及答案(普及组Pascal) PDF格式第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一. 单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1.2E＋03表示（）。

A.2.03B.5C.8D.20002.一个字节（byte）由（）个二进制位组成。

A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。

A.P∨(﹁P∧Q) ∨(﹁P∧﹁Q)B.Q∨(﹁P∧Q) ∨(P∧﹁Q)C. P∨Q∨(P∧﹁Q) ∨(﹁P∧Q)D.P∨﹁Q∨(P∧﹁Q) ∨(﹁P∧﹁Q)4.Linux下可执行文件的默认扩展名为（）。

A.exeC.dllD.以是都不是5.如果树根算是第1层，那么一棵n层的二叉树最多有（）结点。

A.2n-1B.2nC.2n+1D.2n+16.提出“存储程序”的计算机工作原理的是（）。

A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.设X、Y、Z分别代表三进制下的一位数字，若等式XY＋ZX＝XYX在三进制下成立，那么同样在三进制下，等式XY×ZX＝（）也成立。

A.YXZB.ZXYC.XYZD.XZY9.前缀表达式“＋3×2＋5 12”的值是（）。

A.23B.25C.37D.6510.主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。

于是，为了提高系统整体的执行效率，在CPU中引入了（）。

A.寄存器B.高速缓存C.闪存D.外存11.一个字长为8位的整数的补码是11111001,则它的原码是（）。