NOIP 2009提高组试题

历年NOIP(普及组)难度分析by Climber.pI
数学： 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、潜伏者program spy;varv: array['A'..'Z'] of boolean; p, q: array['A'..'Z'] of char; a, b: string;j: char;i: integer;procedure stop;beginwriteln('Failed');close(input);close(output);halt;end;beginassign(input, 'spy.in');reset(input);assign(output, 'spy.out'); rewrite(output);readln(a);readln(b);fillchar(v, sizeof(v), 0);for i := 1 to length(a) do beginv[a[i]] := true;p[a[i]] := b[i];q[b[i]] := a[i];end;for j := 'A' to 'Z' doif not v[j] then stop;for i := 1 to length(a) do beginif p[a[i]] <> b[i] then stop; if q[b[i]] <> a[i] then stop; end;readln(a);for i := 1 to length(a) do write(p[a[i]]);writeln;close(input);close(output);end.2、Hankson的趣味题思路1：根据最大公约数的定义，X必定为最大公约数的倍数，那么我们可以去枚举a1的倍数，然后去验证最大公约数和最小公倍数是否符合条件。

期待分数：50。

程序1：vara0,a1,b0,b1,i,j,n,k,x,tot:longint;function gcd(a,b:longint):longint;beginif b=0 then exit(a) else exit(gcd(b,a mod b));end;beginreadln(n);for k:=1 to n dobegintot:=0;readln(a0,a1,b0,b1);for i:=1 to (b1 div a1) dobeginx:=i*a1;if b1 mod x=0 thenif gcd(a0,x)=a1 thenif (b0*x) div (gcd(b0,x))=b1 then begin inc(tot); end;end;writeln(tot);end;end.思路2：根据最小公倍数和最大公约数分解质因数指数的特殊关系进行优化。

提高组（Pascal语言）参考答案与评分标准一、单项选择题：（每题1.5分）1. C2. A3. D4. B5. D6. B7. B8. A9. A 10. C二、不定项选择题（共10题，每题1.5分，共计15分。

每题正确答案的个数大于或等于1。

多选或少选均不得分）。

1. AB2. BD3. BC4. C5. BD6. ABD7. AC8. ABC9. ABCD 10. ACD三、问题求解：（共2题，每空5分，共计10分）1．4322．35四、阅读程序写结果（共4题，每题8分，共计32分）1. 32. 58503. 487 (杨辉三角)4. 0.(384615)（分数变小数）五．完善程序(前5空，每空2分，后6空，每空3分，共28分)（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1.①0②tmp+a[i]=ans或者a[i]+tmp=ans 或者ans=a[i]+tmp等③ <0④i⑤inc(tmp, a[i])或者tmp := tmp+a[i]2.①now<=maxnum 或者not(now>maxnum)② second-first③ (ans-1)④ hash[first]>=ans 或者 hash[second]>=ans 或者 hash[first+delta]>=ans⑤ ok⑥work(0)用心爱心专心。

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

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

）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机只是一个理论上的计算模型。

D)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

2、关于BIOS下面的说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制 ASCII编码为：A) 48 B) 49 C) 50 D) 以上都不是4、在字长为16101101。

其对应的十进制整数应该是：A)19 B) -19 C) 18 D) -185、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+16. 表达式a*(b+c)-d的后缀表达式是：A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd7、最优前缀编码，也称Huffman编码。

这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。

下面编码组合哪一组不是合法的前缀编码。

A)（00，01，10，11）B)（0，1，00，11）C)（0，10，110，111）D)（1，01，000，001）8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：n)，最坏情况O(n2)A) 平均情况 O(nlog2B) 平均情况 O(n)，最坏情况O(n2)n)C) 平均情况 O(n)，最坏情况O(nlog2D) 平均情况 O(logn)，最坏情况O(n2)29、右图给出了一个加权无向图，从顶点V开始用prim算法求最小生成树。

Noip2009 提高组第一题潜伏者(spy.pas/c/cpp)【问题描述】R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。

历经艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1、 S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所的内容均由大写字母‘A’—‘Z’构成（无空格等其他字母）。

2、 S国对于每个字母规定了对应的“密字”。

加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

3、每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。

“密字”可以和原字母相同。

例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。

现在，小C通过内线掌握了S国网络上发送的一条加密信息及其对应的原信息。

小C希望能通过这条信息，破译S国的军用密码。

小C的破译过程是这样的：扫描原信息，对于原信息中的字母x（代表任一大写字母），找到其在加密信息中的对应大写字母y，并认为在密码里y是x的密字。

如此进行下去直到停止于如下的某个状态：1、所有信息扫描完毕，‘A’—‘Z’所有26个字母在原信息中均出现过并获得了相应的“密字”。

2、所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

3、扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S过密码的编码规则）。

例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。

在小C忙得头昏脑胀之际，R国司令部又发来电报，要求他翻译另外一条从S国刚刚截取到的加密信息。

现在请你帮助小C：通过内线掌握的信息，尝试破译密码。

然后利用破译的密码，翻译电报中的加密信息。

【输入】输入文件名为spy.in，共3行，每行为一个长度在1到100之间的字符串。

第1行为小C掌握的一条加密信息。

第2行为第1行的加密信息所对应的原信息。

第3行为R国司令部要求小C翻译的加密信息。

、|!_一个人总要走陌生的路，看陌生的风景，听陌生的歌，然后在某个不经意的瞬间，你会发现，原本费尽心机想要忘记的事情真的就这么忘记了..[原创]NOIP2009提高组解题报告{继续供大牛BS}2009-11-21 10:46 P.M.第一题：水题，按照题目要求去枚举。

注意，同一个字母加密后的字母是一样的，加密后一样的字母原字母也是一样的。

vars1,s2,s3:string;a,b:array['A'..'Z']of char;i:longint;c:char;procedure main;beginreadln(s1);readln(s2);readln(s3);fillchar(a,sizeof(a),' ');fillchar(b,sizeof(b),' ');for i:=1 to length(s1) doif ((a[s1[i]]<>' ')and(a[s1[i]]<>s2[i]))or((b[s2[i]]<>' ')and(b[s2[i]]<>s1[i])) thenbeginwriteln('Failed');exit;endelsebegina[s1[i]]:=s2[i];b[s2[i]]:=s1[i];end;for c:='A' to 'Z' doif a[c]=' ' thenbeginwriteln('Failed');exit;end;for i:=1 to length(s3) dowrite(a[s3[i]]);writeln;end;beginassign(input,'spy.in');reset(input);assign(output,'spy.out');rewrite(output);main;close(input);close(output);end.第二题：数论题，分解质因数。

NOIP 19981．火车从始发站（称为第1站）开出，在始发站上车的人数为a ，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a 人。

从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。

现给出的条件是：共有N 个车站，始发站上车的人数为a ，最后一站下车的人数是m （全部下车）。

试问x 站开出时车上的人数是多少？2．设有n 个正整数（n ≤20），将它们联接成一排，组成一个最大的多位整数。

例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213又如：n=4时，4个整数7，13，4，246联接成的最大整数为：74246133．著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。

例如：其含义为：L+L=L ，L+K=K ，L+V=V ，L+E=E K+L=K ，K+K=V ，K+V=E ，K+E=KL E+E=KV根据这些规则可推导出：L=0，K=1，V=2，E=3同时可以确定该表表示的是4进制加法NOIP 1999第一题拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）输入：a ，n ，m 和x输出：从x 站开出时车上的人数。

2009年全国信息学联赛高中组初赛模拟试题组卷：东莞中学唐章辉全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、单项选择题（共10题，每题1.5分，共计15分。

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

1.微型计算机的性能主要取决于（）。

A）内存 B）主板 C）中央处理器 D）硬盘 E）显示器2. 128KB的存储器用十六进制表示，它的最大的地址码是( )A)10000 B)EFFF C)1FFFF D)FFFFF E)FFFF3.能将高级语言程序转换为目标程序的是( ).A)调试程序 B)解释程序 C)编辑程序 D)编译程序 E)连接程序4．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )BA)01011110 B)00001111 C)01011100 D)11001110 E)110010105.计算机病毒传染的必要条件是( ) 。

A)在内存中运行病毒程序B)对磁盘进行读写操作C)在内存中运行含有病毒的可执行程序D)复制文件E)删除文件6. TCP／IP协议共有( )层协议A)3 B)4 C)5 D)6 E)77.192.168.0.1是属于( ).A)A类地址 B)B类地址 B)C类地址 D)D类地址 E)E类地址8.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第一趟扫描的结果是( ).A)(24,21,35,54,67, 78,63,73,89)B)(24,35,21,54,67, 78,63,73,89)C)(24,21,35,54,67, 63,73,78,89)D)(21,24,35,54,63, 67,73,78,89)E)(24,21,35,54,67, 63,73,78,89)9.一棵n个结点的完全二叉树,则二叉树的高度h为( ).A)n/2 B)log2n C)(log2n)/2 D) [log2n]+1 E)2n-110.下图对该图进行广度优先拓朴排序得到的顶点序列正确的是( ).A)1,2,3,4,5,6 B)1,3,2,4,5,6 C)1,3,2,4,6,5D)1,2,3,4,6,5, E)1,3,2,4,5,6二、不定项选择题（共10题，每题1.5分，共计15分。

NOI分区联赛- 2000年第六届提高组试题解析注意：解析和源程序均为OIBH站长刘汝佳所写，疏漏在所难免，但至少程序均通过了比赛时使用的测试数据，所以还是可以一看。

第一题：大家对正数进制的转换应该比较熟悉吧！（不会的看我的《循序渐进》）负数进制一样。

每次取的余数保证在0~-m-1之间。

（例如m=-16,则余数应该在0~15）就可以直接输出。

所以用系统的“mod”运算符的时候必须注意检查是不是在该范围（可能在m+1~0），否则就调整。

调整的方法是：if 余数<0 thenbegin余数=余数-m;商=商+1;end;程序见附件。

第二题：很明显的动态规划。

令d[i,j,k]为第i个数字到第j个数字加k个乘号所能够达到的最大值。

状态转移方程是：d[i,j,k]=max{num[i,t]*d[t+1,j,k-1]} (枚举t, 满足i<=t<=j-1)注意到状态转移的时候总是使k减小（或不变）的，所以把k作为阶段来递推（节约空间）。

在每个状态中，l=j-i越来越小，所以从l=0递推到l=n即：for k:=1 to c dofor l:=0 to n dofor i:=1 to n do递推d[i,j,k]显然，用两个数组记录d[i,j,k]和d[i,j,k-1],就可以只用两维：d[i,j]于是算法框架就是(请对照我的源程序)：初始化d1[i,j]for k:=1 to c dobeginfor l:=0 to n dofor i:=1 to n do用d1[i,j](k-1阶段)递推d2[i,j]（k阶段）d1:=d2; {节省空间，因为递推的时候只与上个阶段有关，故只保留相邻两个阶段}end;高精度乘法的方法我不是用的模拟手算的过程（这个大家会做吧），而用了类似多项式乘法的方法，因为我觉得这种写法很好记！(大家仔细看看我的mul过程)程序见附件。

第三题：搜索。

数据很小，因此回溯就可以了。

T1:潜伏者【问题描述】R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。

历尽艰险后，潜伏于S国的R国间谍小C终于摸清了S国军用密码的编码规则：1．S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘A’-‘Z’构成（无空格等其他字符）。

2．S国对于每个字母规定了对应的“密字”。

加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

3．每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。

“密字”可以和原字母相同。

例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。

现在，小C通过内线掌握了S国网络上发送的一条加密信息及其对应的原信息。

小C希望能通过这条信息，破译S国的军用密码。

小C的破译过程是这样的：扫描原信息，对于原信息中的字母x（代表任一大写字母），找到其在加密信息中的对应大写字母y，并认为在密码里y是x的密字。

如此进行下去直到停止于如下的某个状态：1．所有信息扫描完毕，‘A’-‘Z’所有26个字母在原信息中均出现过并获得了相应的“密字”。

2．所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

3．扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S国密码的编码规则）。

例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。

在小C忙得头昏脑涨之际，R国司令部又发来电报，要求他翻译另外一条从S国刚刚截取到的加密信息。

现在请你帮助小C：通过内线掌握的信息，尝试破译密码。

然后利用破译的密码，翻译电报中的加密信息。

【输入】输入文件名为spy.in，共3行，每行为一个长度在1到100之间的字符串。

第1行为小C掌握的一条加密信息。

第2行为第1行的加密信息所对应的原信息。

第3行为R国司令部要求小C翻译的加密信息。

输入数据保证所有字符串仅由大写字母‘A’-‘Z’构成，且第1行长度与第2行相等。