冲刺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矿。

作者：钟野梓序今年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）【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。