冲刺NOIP2010模拟试题与解析(十三)

第十六届全国青少年信息学奥林匹克联赛初赛试题（ 提高组 C++ 语言 两小时完成 ）• • 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ••、单项选择题 （共 10 题，每题 1.5 分，共计 15 分。

每题有且仅有一个正确选项。

）1．与十六进制数 A1.2 等值的十进制数是（ )A ． 101.2B ． 111.4C ． 161.125D ． 177.25&主存储器的存取速度比中央处理器 （CPU ）的工作速度慢的多，从而使得后者的效率受到影响。

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

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

A ．寄存器B ．高速缓存C ．闪存D ．外存9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序 结构的数组中。

假定根结点存放在数组的 1 号位置上，则第 k 号结点的父结点如果存在的话，应当 存放在数组中的（ ）号位置。

A ．2kB ．2k+1C ．k/2 下取整D ．（k+1）/22．一个字节（ byte ）由（ ）个二进制组成。

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

A . P V （n P A Q ）V （n P 心 Q ）BC . P V Q V （ P A n Q ）V （n P A Q ）D 4 ． Linux 下可执行文件的默认扩展名是 （ ） 。

A.exe B. com都不是C ．32 D .以Q V( n P A Q )V (P A n Q )P V n Q V( P A n Q V (n P A n Q)C. dllD.以上5 ．如果在某个进制下等式 7*7=41 成立，那么在该进制下等式 12*12= （ A. 100B. 144C. 164 ）也成立。

D. 1966 ．提出“存储程序”的计算机工作原理的是（A. 克劳德 ?香农B. 戈登?摩尔）。

NOIP2010 模拟试题故事背景：话说小FF在经历了上次“寻找古代王族遗产”的探险后，成为了世界上最伟大的探险家并拥有了一大笔财富。

当然他不能坐吃山空，必须创造财富！！于是他买下了传说中的Greed Island并优先发展那里的采矿业……他还将其称为Greed Island的“NewBe_One”计划。

试题一：新的开始【题目描述】发展采矿业当然首先得有矿井，小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井，但他似乎忘记考虑的矿井供电问题……为了保证电力的供应，小FF想到了两种办法：1、在这一口矿井上建立一个发电站，费用为v（发电站的输出功率可以供给任意多个矿井）。

2、将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为p。

小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。

【输入格式】第一行一个整数n，表示矿井总数。

第2～n+1行，每行一个整数，第i个数v[i]表示在第i口矿井上建立发电站的费用。

接下来为一个n*n的矩阵P，其中p[ i , j ]表示在第i口矿井和第j口矿井之间建立电网的费用（数据保证有p[ i, j ] = p[ j, i ], 且p[ i, i ]=0）。

【输出格式】仅一个整数，表示让所有矿井获得充足电能的最小花费。

【输入样例】454430 2 2 22 03 32 3 0 42 3 4 0【输出样例】9输出样例说明：小FF可以选择在4号矿井建立发电站然后把所有矿井都与其建立电网，总花费是3+2+2+2 = 9。

【数据范围】对于30%的数据：1<=n<=50;对于100%的数据：1<=n<=300; 0<=v[i], p[i,j] <=10^5.试题二工业时代【试题描述】小FF的第一片矿区已经开始运作了，他着手开展第二片矿区……小FF的第二片矿区，也是”NewBe_One“计划的核心部分，因为在这片矿区里面有全宇宙最稀有的两种矿物，科学家称其为NEW矿和BE矿。

NOIP2010 模拟试题故事背景：话说小FF在经历了上次“寻找古代王族遗产”的探险后，成为了世界上最伟大的探险家并拥有了一大笔财富。

当然他不能坐吃山空，必须创造财富！！于是他买下了传说中的Greed Island并优先发展那里的采矿业……他还将其称为Greed Island的“NewBe_One”计划。

试题一：新的开始【题目描述】发展采矿业当然首先得有矿井，小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井，但他似乎忘记考虑的矿井供电问题……为了保证电力的供应，小FF想到了两种办法：1、在这一口矿井上建立一个发电站，费用为v（发电站的输出功率可以供给任意多个矿井）。

2、将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为p。

小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。

【输入格式】第一行一个整数n，表示矿井总数。

第2～n+1行，每行一个整数，第i个数v[i]表示在第i口矿井上建立发电站的费用。

接下来为一个n*n的矩阵P，其中p[ i , j ]表示在第i口矿井和第j口矿井之间建立电网的费用（数据保证有p[ i, j ] = p[ j, i ], 且p[ i, i ]=0）。

【输出格式】仅一个整数，表示让所有矿井获得充足电能的最小花费。

【输入样例】454430 2 2 22 03 32 3 0 42 3 4 0【输出样例】9输出样例说明：小FF可以选择在4号矿井建立发电站然后把所有矿井都与其建立电网，总花费是3+2+2+2 = 9。

【数据范围】对于30%的数据：1<=n<=50;对于100%的数据：1<=n<=300; 0<=v[i], p[i,j] <=10^5.试题二工业时代【试题描述】小FF的第一片矿区已经开始运作了，他着手开展第二片矿区……小FF的第二片矿区，也是”NewBe_One“计划的核心部分，因为在这片矿区里面有全宇宙最稀有的两种矿物，科学家称其为NEW矿和BE矿。

首先，第一题是四道题中最简单的，直接写代码，注意一些细节就可以了， 一百分也是一定要拿到手的，因为后面的分都不是很好拿。 然后是第二题，第二题就要用动态规划了，可以用最朴素的BFS来过那30% 的比较弱的数据，用最朴素的动态规划只能拿到50%左右的分，需要对动态规 划的状态进行优化，方可拿到一百分。 对于第三题，用搜索很快可拿30，代码复杂度也极低，看到规律的枚举 +BFS（floodfill）拿80分，会优化的二分（二分枚举）+BFS拿满分，只是代 码稍微麻烦些，或者有思路的用贪心+并查集也可拿满分，代码也要比二分 +BFS简单一点。 然后关于本题，数据的反复查找与读取很耗时，想不超时的一些同学需要考 虑图论中无向联通图的存储方式，邻接矩阵和完善的静态邻接表直接爆内存零 分，所以只能用动态邻接表或者双链表，笔者偷懒，用的不完善静态链表+直 接查找数据……所以，学学动态邻接表和双链表存储图看来迫在眉睫…… 最后是第四题，思路比较难，搜索的可以稳拿拿到30分，没有思路就搜索 吧。分析过后可以发现最后一题就是一个搜索+“线段覆盖”问题，对于搜索， 本体其实用DFS会比BFS快很多，对于“线段覆盖”，用动规解决就好了。
总分
400 380 340 330 320 310 300 300 290 280 280 270 270 260 260 260 260 250 250 250 240 240 240
姓名
徐明昭 张硕基 徐子尧 崔灏 田博 李光谱 吕诚 魏鑫鼎 马龙 李昭 吴文彬 李金培 李栋 李昂 杨帅 李怡君 杨东 王子晗 谢志聪 周梦溪 苏畅 许可 常泽昊
240 240 240 240 240 240 230 230 230 230 230 230 220 210 210 210 210 210 200 200

NOIP2010 初赛 提高组 C++ 1
NOIP2010 年普及组（C++语言）参考答案与评分标准
一、单项选择题：（每题 1.5 分） 1 D 11 D 2 A 12 B 3 A 13 B 4 D 14 B 5 A 15 B 619 C 10 B 20 D
二、问题求解：（共 2 题，每空 5 分，共计 10 分） 2．49
1．2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或 22123113431213536）
三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分） 1．2 20 77 91 2．99 101 111 3．120 112 4．（1）1 （2）4 四、完善程序（前 4 空，每空 2.5 分，后 6 空，每空 3 分，共计 28 分） （说明： 以下各程序填空可能还有一些等价的写法， 各省可请本省专家审定和上机验证， 不一定上报科学委员会审查） 1． ① tmp=true ② p[j] ③ p[r]=i ④ p[j]+p[k] ⑤ 1004 本小题中，LEFT 可用 true 代替，LEFT_TO_RIGHT 可用 true 代替，RIGHT_TO_LEFT 可用 false 代替。 2． ① num <= 2（或 num < 3 或 num = 2） ② go(LEFT_TO_RIGHT) ③ pos[i] = =LEFT（或 LEFT = pos[i]） ④ hour[i] + go(RIGHT_TO_LEFT)（或 go(RIGHT_TO_LEFT) +hour[i]） ⑤ pos[i] = LEFT 本小题中，LEFT 可用 true 代替，LEFT_TO_RIGHT 可用 true 代替，RIGHT_TO_LEFT 可用 false 代替。

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

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

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

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

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

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

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

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

报数【题目描述】CG同学又弄到一批新牛，新牛到了农场后，首先学习汉语，数的朗读成为新牛的难题。

朗读绝对值小于10亿的数。

新牛们知道汉语中有如下的朗读规则：1.首先读符号位，然后读整数部分。

整数部分之后可能出现小数点，如果有小数部分则小数点一定出现，并且读出小数点之后读小数部分。

2.符号位的读法是：（1）正数，不论正号“+”是否出现，都不必读出符号位；（2）负数最左边的符号是“-”读成“负”(以“F”来表示“负”)。

3.整数部分的读法是：(1)如果整数部分不存在或整数部分全为零则直接读成“零”（以“0”来表示“零”）；(2)否则从整数部分中最左边的非零数字开始读起，然后以十，百，千，万，亿（分别以“S”,“B”,“Q”“W”,“Y”来表示）等数量单位来拼读整数部分。

4.整数部分中：（1）每一个非零数字都必须结合各个相应的数量单位读出来。

（2）每一段连续的“零”只能读成一个“零”，但是某一段连续的“零”的左侧或者右侧不存在非零数字（这里只考虑整数部分）则这一段“零”不应该读出来。

5.如果有小数部分，则首先读“点”（以“D”来表示“点”），然后从左至右有顺序的读出各个小数位。

在读小数部分的时候不可以使用十，百，千，万，亿等数量单位；但是小数部分的每一个数字都要读出来，连续的零不可以读成一个零，而应该分别读出。

6.如果数中有小数点而没有小数部分，则不应该把小数点读出来。

例如，—0020030004.567应该读成“F2Q03W04D567”，000.89应该读成“0D89”。

请你编写程序帮助新牛把给定的数正确地读出来。

【输入格式】输入文件仅一行，存放了一个数（不超过50个字符），其绝对值小于10亿。

【输出格式】输出文件仅一行，输出这个数的正确读法。

【样例输入】-0020030004.567【样例输出】F2Q03W04D567弄了好几个小时，两个版本，把精简的奉上，详见代码注释。

期间使用了一个单位数组flag，数字数组a，标志数组b。

冲刺NOIP2010模拟试题与解析（一）题目（提高组时间：3个小时）难易指数：★★★1、淘汰赛制(elimination.pas/c/cpp)【问题描述】淘汰赛制是一种极其残酷的比赛制度。

2n名选手分别标号1，2，3，…，2n-1，2n，他们将要参加n轮的激烈角逐。

每一轮中，将所有参加该轮的选手按标号从小到大排序后，第1位与第2位比赛，第3位与第4位比赛，第5位与第6位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛（不会有平局）。

这样，每轮将淘汰一半的选手。

n轮过后，只剩下一名选手，该选手即为最终的冠军。

现在已知每位选手分别与其他选手比赛获胜的概率，请你预测一下谁夺冠的概率最大。

【输入文件】输入文件elimination.in。

第一行是一个整数n(l≤n≤l0)，表示总轮数。

接下来2n行，每行2n个整数，第i行第j个是p ij(0≤p ij≤100，p ii=0，p ij+p ji=100)，表示第i号选手与第j 号选手比赛获胜的概率。

【输出文件】输出文件elimination.out。

只有一个整数c，表示夺冠概率最大的选手编号（若有多位选手，输出编号最小者）。

【样例输入】20 90 50 5010 0 10 1050 90 0 5050 90 50 0【样例输出】1【数据规模】30%的数据满足n≤3；100%的数据满足n≤10。

2、种树（trees.pas/c/cpp）【问题描述】一条街的一边有几座房子。

因为环保原因居民想要在路边种些树。

路边的地区被分割成块，并被编号为l…n。

每个块的大小为一个单位尺寸并最多可种一棵树。

每个居民想在门前种些树并指定了三个号码b，e，t。

这三个数表示该居民想在b和e之间最少种t棵树。

当然，b≤e，居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t≤e-b+1，允许居民想种树的各自区域可以交叉。

出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。

冲刺NOIP 2010模拟试题与解析（十三）一、防护伞【题目描述】据说2012的灾难和太阳黑子的爆发有关。

于是地球防卫小队决定制造一个特殊防护伞，挡住太阳黑子爆发的区域，减少其对地球的影响。

由于太阳相对于地球来说实在是太大了，我们可以把太阳表面看作一个平面，中心定为(0,0)。

根据科学家的情报，在2012年时，太阳表面上产生N个黑子区域，每一个黑子视为一个点。

特殊防护伞可以看作一个巨大的圆面，现在地球防卫小队决定将它的中心定位于某一个黑子，然后用伞面挡住其他黑子。

因为制造防护伞的材料成本特别高，所以我们希望伞面尽可能的小。

【输入格式】第1行：一个整数N，表示黑子个数。

第2..N-1行：每行两个整数，表示黑子的坐标(X,y)。

【输出格式】第1行：一个实数，表示伞的面积。

【输入样例】30 1-8 -4-1 4【输出样例】279.6017【数据范围】对于50%的数据：2≤N≤100。

对于100%的数据：2≤N≤1,000。

-10,000≤x,y≤10,000。

【注意】精确到小数点后4位。

Pi=3.1415926535二、外星密码【题目描述】有了防护伞，并不能完全避免2012的灾难。

地球防卫小队决定去求助外星种族的帮助。

经过很长时间的努力，小队终于收到了外星生命的回信。

但是外星人发过来的却是一串密码。

只有解开密码，才能知道外星人给的准确回复。

解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串“x”会压缩为“[DX]”的形式（D是一个整数且1≤D ≤99），比如说字符串“CBCBCBCB”就压缩为“[4CB]”或者“[2[2CB]]”，类似于后面这种压缩之后再压缩的我们称之为二重压缩。

如果是“[2[2[2CB]]]"，则是三重。

现在我们给你外星人发送的密码，请你对其进行解压缩。

【输入格式】第1行：一个字符串【输出格式】第1行：一个字符串【输入样例】AC[3FUN]【输出样例】ACFUNFUNFUN【数据范围】对于50%的数据：解压后的字符串长度在1,000以内，最多只有三重压缩。

越野跑【描述】为了能在下一次跑步比赛中有好的发挥，贝茜在一条山路上开始了她的训练。

贝茜希望能在每次训练中跑得尽可能远，不过她也知道农场中的一条规定：奶牛独自进山的时间不得超过M秒(1 <=M<=10,000,000)。

整条山路被贝茜划分成T个长度相同的小段(1 <= T <= 100,000)，并且，贝茜用S_i表示第i个小段的路况。

S_i为u，f，d这3个字母之一，它们分别表示第i个小段是上坡、平地，或是下坡。

贝茜要花U秒(1<=U<=100)才能跑完一段上坡路，跑完一段平地的耗时是F 秒(1<=F<=100)，跑完一段下坡路要花D秒(1<=D<=100)。

注意，沿山路原路返回的时候，原本是上坡路的路段变成了下坡路，原本是下坡路的路段变成了上坡路。

贝茜想知道，在能按时返回农场的前提下，她最多能在这条山路上跑多远。

【输入格式】* 第1行: 5个用空格隔开的整数：M，T，U，F，以及D*第2..T+1行:第i+1行为1个字母S_i，描述了第i段山路的路况【输出格式】*第1行:输出1个整数，为贝茜在按时回到农场的前提下，最多能跑到多远【样例输入】13 5 3 2 1ufudf【样例输出】3【题解】模拟一下跑步的过程。

用s记录跑到第i段路并返回的时间若s=m则输出i并退出，若s>m则输出I-1并退出。

【参考程序】program dfjk;var i,s,m,t,u,f,d:longint;a:array[1..100000]of char;beginreadln(m,t,u,f,d);for i:=1 to t doreadln(a[i]);s:=0;for i:=1 to t dobegincase a[i] of'u':s:=s+u+d;'f':s:=s+2*f;'d':s:=s+u+d;end;if s>=m then break;end;if s=m then writeln(i);if s>m then writeln(i-1);end.输入85 6 23 12 31ufdfdu 输出2输入985 10 430 325 314ufdfdufuud输出1数字反转（reverse.pas）【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。

冲刺NOIP2010模拟试题与解析（普及组复赛）湖南省长沙市第一中学周祖松一、数数(count.pas/c/cpp)【问题描述】小可可正在学习怎么用手指数数。

当爸爸问她“n(1 ≤ n ≤ 10)是多少”，小可可的回答就是竖起n个手指头。

为了让问题简单一些，爸爸告诉她正确的手指表示方式：(1)这个数可以用一只手或两只手表示；(2)如果这个数用两只手表示，大的数会先给出。

比如爸爸问她“4是多少”，小可可有3种表示方法：(1)一只手竖起出4个手指头；（可以是左手也可是右手，只算一种）(2)一只手竖起出3个手指头，另一只手竖起出1个手指头；(3)一只手竖起出2个手指头，另一只手竖起出2个手指头；你的任务是，对于爸爸的提问，确认小可可有几种正确的回答方法。

【输入】输入文件count.in共一行为一个1到10之间的整数。

【输出】输出文件count.out共一行为一个整数，表示方法总数。

【样例输入】4【样例输出】3二、分数树(fraction.pas/c/cpp)【问题描述】十九世纪的时候，Moriz Stern (1858)与Achille Brocot (1860)发明了“一棵树”。

据说，经由一些简单的规则而产生的这一棵树上，可以包含零以上所有的有理数。

这棵树看起来大致这样：你观察出规则了吗？首先,他们在第一列放两个“分数”，第一个是0 / 1，代表0；第二个是1 / 0，代表无穷大。

接着他们一列一列地产生这棵树,当他们要产生第k+1列的时候,就先把前k列所有的分数按照大小排成一列（假设有n个），在这些数之间会有n - 1个间隔，那么第k + 1列就准备产生n - 1个数，其值的分子恰好是左右两个数的分子的和、分母是左右两个数的分母的和。

例如，2 / 3，而它的2就是左边1 / 2的1和右边1 / 1的分子1相加的结果；而2 / 3的3，则是1 / 2的2加上1 / 1的分母1而得。

从这棵树中，我们可以看出，每个正的最简分数在这棵树中恰好出现一次，我们用字母“L”和“R”分别表示从树根(1 / 1)开始的一步“往左走”和“往右走”，则每一个数都可以由L和R 组成的序列表示。

NOIP2010提高组初赛（答案+选择题题目+个人分析)一、单项选择题1.与16进制数A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.25C A1.2=10*16^1+1*16^0+1*16^(-1) 公式A=10B=11C=12D=13E=14F=15A=10*16^1=160 1=1*16^0=1 0.2=1*16^(-1)=1/8=0.125Y*X^Z+y*x^z+y*x^z+.......... Y题中式子每一位数X进制数Z第几位数例如上式A是第2位数所以2次方必考的进制运算没什么可说的=。

=2.一个字节（byte）由（）个二进制组成。

A.8B.16C.32D.以上都有可能A字节8个字16个双字32个常识问题：数据存储是以“字节”（Byte）为单位，数据传输是以“位”（bit）为单位，一个位就代表一个0或1（即二进制），每8个位（bit）组成一个字节（Byte）。

8bit=1Byte3.以下逻辑表达式的值恒为真的是（）。

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)A不太懂表示方法："∨"表示"或"，"∧"表示"与"."┐"表示"非"."= =" 表示＂等价＂.１和０表示＂真＂和＂假＂(还有一种表示,"+"表示"或", "·"表示"与")4.Linux下可执行文件的默认扩展名是( )。

A. exe windows执行程序B. Com windows可执行文件C. Dll动态链接库D. 以上都不是DLinux和Windows不同，Linux一般可执行文件都没有扩展名；Linux不根据拓展名判断文件类型而是根据文件内容判断；因此Linux下扩展名的作用只是帮助以识别文件的，对Linux本身并没有什么用=。

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

每题有且仅有一个正确选项。

）1．2E+03表示（）。

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

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

A．PV(¬PΛQ)V(¬PΛQ) B．QV(¬PΛQ)V(PΛ¬Q)C．PVQV(PΛ¬Q)V(¬PΛQ) D．P V¬QV(PΛ¬Q)V(¬PΛ¬Q)4．Linux下可执行文件的扩展名为（）。

A．exe B．com C．dll D．以上都不是5．如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。

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

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

A．YXZ B．ZXY C．XYZ D．XZY8．Pascal语言、C语言和C++语言都属于（）。

A．面向对象语言B．脚本语言C．解释性语言D．编译性语言9．前缀表达式“+3*2+5 12”的值是（)。

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

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

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

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

二、问题求解。 1．2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6（或22123113431213536） 2.队列快照是指在某一时刻队列中的元素组成的有序序列。例如 ，当元素1、2、3入队，元素1出队后，此刻的队列快照是“2 3”。 当元素2、3也出队后，队列快照是“”，即为空。现有3个正整数 元素依次入队、出队。已知它们的和为8，则共有______种可能 的不同的队列快照（不同队列的相同快照只计一次）。例如， “5 1”、“4 2 2”、“”都是可能的队列快照；而“7”不是可能的 队列 快照，因为剩下的2个正整数的和不可能是1。 解：49。 根据题意，3个可能的元素序列是(1,1,6),(1,2,5),(1,3,4),(2,2,4), (2,3,3)。快照中元素个数可能是0,1,2,3个。 当元素个数为0时，有1中情况，即为空； 当元素个数为1时，有6种情况，即为(1),(2),(3),(4),(5),(6)； 当元素个数为2时，有3+6+6+3+3=21种，即为3个元素中任取2个 的排列数； 当元素个数为3时，有3+6+6+3+3=21中，所以共49种。
log2(n!) nlog2n 所以，基于“比较关键字”进行排序的排序方法，可能达到的最 快的时间复杂度为O(nlogn)。 13、选B。 归纳10进制数位数与二进制位数关系：
十进制数位数
1 2 3 4 5 ……
二进制位数
1~4 4~7 7~10 10~14 14~17 ……
14、选B。 题目给定的是4个超文本标记语言。而B是符合题意的选项。
三、阅读程序写结果（共4题，每题8分，其中第4题（1）、（2） 各4分，共计32分） 1．2 20 77 91 2．99 101 111 3．120 112 4．（1）1 （2）4 四、完善程序（前4空，每空2.5分，后6空，每空3分，共计28分） （说明：以下各程序填空可能还有一些等价的写法，各省可请本 省专家审定和上机验证，不一定上报科学委员会审查） 1．① tmp := true ② p[j] ③ p[r] := i ④ p[j] + p[k]（或p[k] + p[j]） ⑤ 1004 2．① num <= 2（或num < 3 或num = 2） ② go(LEFT_TO_RIGHT) ③ pos[i] = LEFT（或LEFT = pos[i]）

冲刺NOIP 2010 模拟试题（十）（普及组）一、手机（mobile.pas）【问题描述】一般的手机的键盘是这样的：X就得按9两下，第一下会出w，而第二下会把w变成x。

0键按一下会出一个空格。

你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。

【问题输入】一行一个句子，只包含英文小写字母和空格，且不超过200个字符。

【问题输出】一行一个整数，表示按键盘的总次数。

【样例输入】I have a dream【样例输出】23【数据范围】如题目所示二、数字积木（brick.pas）【问题描述】小明有一款新式积木，每个积木上都有一个数，一天小明突发奇想，要是把所有积木排成一排，所形成的数目最大是多少呢？你的任务就是读入n个数字积木，求出所能形成的最大数。

【问题输入】第一行是一个整数n（n<=1000），接下来n行每行是一个正整数。

【问题输出】所能形成的最大整数。

【样例输入】313131343【样例输出】34313131【数据范围】30%的数据，n<=10，每个数<10^3。

50%的数据，n<=100。

100%的数据，n<=1000，每个数<10^200。

三、家族（family.pas）【问题描述】在一个与世隔绝的岛屿上，有一个有趣的现象：同一个家族的人家总是相邻的（这里的相邻是指东南西北四个方向），不同的家族之间总会有河流或是山丘隔绝，但同一个家族的人不一定有相同的姓氏。

现在给你的岛上的地图有n行，每行有若干列，每个格子中要么是“”，表示大海，要么是“*”，表示河流或山丘，要么是小写字母，表示一户人家的姓氏。

【问题输入】第一行是个数字N，表示下面信息的行数。

接下来是N行字符，每行由小写字母和*号组成，有些行的最前面也可能包含若干连续的空格，表示这些区域是大海，每一行最多不超过200个字符。

【问题输出】一个数字，表示家族数。

至此，NOIP2010已经过去将近2个月了，随着保送的取消，我相信会有更多的人不会再参加了。

也不会有人对我8题的题解感兴趣了……但是，兴趣终归是兴趣，不会因为取消保送而放弃他的执着追求，下面，我做一下8题的总结。

普及组：一二两题很简单，直接模拟即可AC。

（但是第二题我只过了9个点，奇怪）。

程序如下：数字统计：#include"stdio.h"long l,r;long dfs(long x){long s=0;while(x!=0){if(x%10==2)s++;x/=10;}return s;}int main(){long s=0;scanf("%ld%ld",&l,&r);for(long i=l;i<=r;i++)s+=dfs(i);printf("%ld",s);getchar(),getchar();return 0;}接水问题：#include"stdio.h"long w[200]={0};long n,m;int main(){long x,ans=0,N;scanf("%ld%ld",&n,&m);for(long j=1;j<=m;j++){scanf("%ld",&x);w[j]=x;}N=n-m;while(N){long k=100000;for(long j=1;j<=m;j++){for(j=1;j<=m;j++)if(w[j]>0&&k>w[j])k=w[j];for(j=1;j<=m;j++){w[j]-=k;if(w[j]==0){if(N!=0){scanf("%ld",&x);N--;w[j]=x;}}}if(k!=100000)ans+=k;}}long k=0;for(long i=1;i<=m;i++)if(k<w[i])k=w[i];ans+=k;printf("%ld",ans);getchar(),getchar();return 0;}第三题，需要枚举加优化。

- 13 -
数据结构
var a:array[1..500,1..500]of longint；
a 为 默契值表，a[i,i] = 0 0 5 28 16 29 27 5 0 23 32 20 1 28 23 0 8 32 26 16 3 8 0 33 11 29 20 32 33 0 12 27 1 26 11 12 0
-9-
确定解题思路
数据量 n ：105，想通过n=105的数据，要有O(n)或 O(n*log(n))的算法。 枚举只能得部分分 贪心策略是首选的。 贪心的衡量标准是什么？ 最简单的是导弹靠哪个近就选哪一个。很简单，可 以得70分。 能得100分的贪心要麻烦一些： 假设只用一套拦截系统，计算出各个导弹的使用代 价，从大到小排序，当然，最大值能拦截所有导弹 然后，从大到小，一个一个地把导弹分给另一套系 统，寻找最小的代价和
- 10 -
例程 pascal
var n,x1,x2,y1,y2,ans : longint; bj1,bj2 : array[0..100000] of longint; procedure init; // 读入数据，预处理 var i,x,y:longint; begin readln(x1,y1,x2,y2); readln(n); for i:=1 to n do begin readln(x,y); bj1[i]:=(x-x1)*(x-x1)+(y-y1)*(y-y1); bj2[i]:=(x-x2)*(x-x2)+(y-y2)*(y-y2); end; end; procedure qsort(a,b:longint); begin…快排………end; procedure doit; begin …处理…end;