下载文档原格式
![复赛noip2010提高组题解[新版]](https://img.taocdn.com/s1/m/7b1ee1c3b8f3f90f76c66137ee06eff9aef84965.png)
1.translate（20分）简单模拟。
开一个1000的队列，时刻保持队列长度不大于M，每次接受翻译请求时，先在队列中查找，查找失败则将单词加入队列。
查找使用Hash则为O(N)，直接扫描O(MN)，都在可接受范围内。
考试时只打了20分，原因至今不明，告诫大家对于水题不要多想，就像这道题最好不开hash，因为一个系统的可靠度是该系统所有子系统可靠度之积，程序越复杂越可能出错。
4.tortoise（50分）基础动规。
可以从题目背景中抽象出这样的问题：有一四维立方体（这里的立方体棱长不必相等，每一维对应一种卡片，每维的棱长对应该种卡片个数），每走一格（即使用一张卡片）的收益是当前位置坐标的函数。
求从(0,0,0,0)走到(a1,a2,a3,a4)最大收益。
故有方程f[x,y,z,t]=max{f[x-1,y,z,t], f[x,y-1,z,t], f[x,y,z-1,t], f[x,y,z,t-1]} + w[1 + x + y*2 + z*3 + t*4]目标状态： f[a1,a2,a3,a4]O(b^4)的代价，数据保证b<=40,完全满足要求5.prison（70分）问题可以重新描述为：寻找最小的冲突值c，使得存在一种方案，将原图分为两部分，并去掉这两部分之间的所有边后，余下的边权都不大于c。
对于这个问题我们可以二分查找c，并判定其可行性。
判定可行性的方法至今没想好。
考试的时候我是用并查集，将所有与u相连并与u之间边权大于c的点（设为点集Zu）必然不与u在同一集合中，枚举所有的u，每次将Zu合并成为一个集合，若存在某点u和Zu某个点处于同一个集合中，则c不可行，反之则可行。
但这种方法貌似存在bug，能拿70分。
如果把并查集合并查找的时间代价看作常数，则这种做法的时间代价为O(elogK),e是边数，K为最大的冲突值。
6.flow（100分）先用floodfill预处理出上方的每个格子能覆盖到下方的格子，构造一个布尔矩阵，行下标表示最上方的某个点，列下标表示最下方的某个点，矩阵对应点的值表示相应两个点的覆盖关系。
作者：钟野梓序今年Noip2010初赛刚结束，网上便铺天盖地地响起了“今年初赛好容易”“分数线一定很高，怎么办……”之类的声音。
确实，自2008年起，Noip初赛难度确有逐年下降的趋势，然而这并不是出题水平降低的缘故，相反，我认为这是中国计算机协会（下称CCF）对于N oip考核目的的审视和改变所导致的必然结果。
因此，我试图通过深入解析本届Noip初赛试囗题，来探寻这种变化下面深层的规律，从而令信息学竞赛选手能更好地备战往后数届的Noip初赛，让初赛不再成为一个问题。
由于条件所限，本文仅以Pascal语言的提高组试囗题作为对象进行分析，相对于普及组而言提高组试囗题一向具有较高的难度和较好的区分度，作为研究对象是个很好的选择；至于说语言的选择，仅是因为笔者个人选择原因。
一、概况本届题目在设置方面与往年相似，由选择题（普及组仅有单项选择题，提高组则有单项选择题与不定项选择题）、问题求解、阅读程序写结果及完善程序四大部分组成；但值得注意的是，今年提高组试囗题的分值设计与往年出现了较大的不同，除了选择题仍然是30分（15分单项+15分不定项），其余部分分值均发生了变化，其中问题求解由10分上升到15分，阅读程序由32分下降到28分，完善程序由28分下降到27分。
由于是第一年实行这种分值，目前暂时无法定言背后的含义，然而或许CCF在初赛更加重视选手的数学素质，而弱化了对于阅读程序能力的考察。
众所周知，阅读程序的能力并不能非常真实地反映选手的程序能力，并且纵观近几年的阅读程序题已没有了什么新意，这也可看做是一个“求新求变”的信号。
至于试囗题整体难度方面较上年有了明显下降，其中问题求解第一题可以看做是考察选手的语文水平，而阅读程序更是没有了以往的“死算”题（即给定若干常数，在程序中设置一系列运算过程，让选手进行阅读计算类型的题目），完善程序给定的源代码风格良好，第二题竟然还加上了注释，这不能不说就是一种降低难度的举动。
![【题解】[Noip2010]机器翻译-C++](https://img.taocdn.com/s1/m/4e9796036fdb6f1aff00bed5b9f3f90f76c64de7.png)
【题解】[Noip2010]机器翻译-C++题⽬Description⼩晨的电脑上安装了⼀个机器翻译软件，他经常⽤这个软件来翻译英语⽂章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英⽂单词⽤对应的中⽂含义来替换。
对于每个英⽂单词，软件会先在内存中查找这个单词的中⽂含义，如果内存中有，软件就会⽤它进⾏翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中⽂含义然后翻译，并将这个单词和译义放⼊内存，以备后续的查找和翻译。
假设内存中有 M 个单元，每单元能存放⼀个单词和译义。
每当软件将⼀个新单词存⼊内存前，如果当前内存中已存⼊的单词数不超过 M?1，软件会将新单词存⼊⼀个未使⽤的内存单元；若内存中已存⼊ M 个单词，软件会清空最早进⼊内存的那个单词，腾出单元来，存放新单词。
假设⼀篇英语⽂章的长度为 N个单词。
给定这篇待译⽂章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
Input输⼊⽂件共 2 ⾏。
每⾏中两个数之间⽤⼀个空格隔开。
第⼀⾏为两个正整数 M和 N，代表内存容量和⽂章的长度。
第⼆⾏为 N 个⾮负整数，按照⽂章的顺序，每个数（⼤⼩不超过 1000）代表⼀个英⽂单词。
⽂章中两个单词是同⼀个单词，当且仅当它们对应的⾮负整数相同。
0<M≤100，0<N≤1000Output包含⼀个整数，为软件需要查词典的次数。
Sample Input3 71 2 1 5 4 4 1Sample Output5//整个查字典过程如下：每⾏表⽰⼀个单词的翻译，冒号前为本次翻译后的内存状况：空：内存初始状态为空。
1． 1：查找单词1 并调⼊内存。
2． 1 2：查找单词 2 并调⼊内存。
3． 1 2：在内存中找到单词 1。
4． 1 2 5：查找单词 5 并调⼊内存。
5． 2 5 4：查找单词 4 并调⼊内存替代单词 1。
6． 2 5 4：在内存中找到单词 4。
7． 5 4 1：查找单词 1 并调⼊内存替代单词 2。
冲刺Noip2010模拟试题七１、数列(Sequence.pas/c/cpp)问题描述一个数列定义如下：f(1) = 1，f(2) = 1，f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7。
给定A,B和n的值，要求计算f(n)的值。
输入格式输入文件(sequence.in)仅一行包含3个整数A，B和n，其中(1≤ A, B ≤1000, 1 ≤n≤100,000,000)。
输出格式输出文件(sequence.out)仅一行，一个整数，即f(n)的值。
输入样列1 1 3输出样列2说明：若输入样例为1 2 10，则输出为5。
数据规模20%的数据，n≤1,00040%的数据，n≤100,000100%的数据，n≤100,000,000２、最长路(path.pas/c/cpp)问题描述设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当<i，j>为G中的一条边时有i < j。
设w（i，j）为边<i，j>的长度，请设计算法，计算图G中<1，n>间的最长路径。
输入格式输入文件path.in的第一行有两个整数n和m,表示有n个顶点和m条边，其中(2≤n≤1500，m≤50000)，接下来m行中每行输入3个整数a ，b，v表示从a点到b点有条边，边的长度为v。
输出格式输出文件path.out，一个整数，即1到n之间的最长路径.如果1到n之间没连通，输出-1。
输入样例2 11 2 1输出样例1说明：若输入样例为2 0，则输出为-1。
数据规模20%的数据，n≤100，m≤100040%的数据，n≤1,000，m≤10000100%的数据，n≤1,500，m≤500003、木棍(wooden.cpp/pas/c)问题描述有n根木棍，每根的长度l和重量w已知。
这些木棍将被一台机器一根一根的加工。
机器需要一些启动时间来做准备工作，启动时间与木棍被加工的具体情况有关。
第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组 C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确选项。
）1．与十六进制数 A1.2等值的十进制数是（）A．101.2 B．111.4 C．161.125 D．177.252．一个字节（byte）由（）个二进制组成。
A．8 B．16 C．32 D．以上都有可能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. exeB. comC. dllD. 以上都不是5．如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。
A. 100B. 144C. 164D. 1966．提出“存储程序”的计算机工作原理的是（）。
A. 克劳德•香农B. 戈登•摩尔C. 查尔斯•巴比奇D. 冯•诺依曼7．前缀表达式“+ 3 * 2 + 5 12 ”的值是（）。
A. 23B. 25C. 37D. 6 58．主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了( )。
A．寄存器 B．高速缓存 C．闪存 D．外存9．完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。
假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。
A．2k B．2k+1 C．k/2下取整 D．(k+1)/210．以下竞赛活动中历史最悠久的是（）。
报数【题目描述】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，允许居民想种树的各自区域可以交叉。
出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。
Noip2010提高组第1题translate 机器翻译【题意分析】现在要翻译一段文章，于是需要查词典。
而计算机拥有存储功能，可以减少一部分查询。
已知计算机内存可以存储m个单词，当要查询的单词在内存中时，可以不用去查词典。
当内存未满时，每查到一个新词，就会加入到内存中；当内存已满，查到的新词会加入到内存中，并把内存中的第一个单词顶出内存。
现要求出翻译一篇文章需要查询词典的次数。
【输入】3 7 第1行2个正整数m、n，表示内存长度及文章长度1 2 1 5 4 4 1 第2行n个非负整数，为文章的内容【输出】5 查询词典的次数【样例分析】整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：空：内存初始状态为空。
1．1：查找单词1 并调入内存。
2．1 2：查找单词2 并调入内存。
3．1 2：在内存中找到单词1。
4． 1 2 5：查找单词5 并调入内存。
5． 2 5 4：查找单词4 并调入内存替代单词1。
6． 2 5 4：在内存中找到单词4。
7． 5 4 1：查找单词1 并调入内存替代单词2。
共计查了5次词典。
【分析】本题就是一个简单的模拟：用队列q表示内存，l、r为内存的头、尾指针；用布尔数组f[i]表示i单词是否在数组中。
【代码】Program translate;Constinfile = 'translate.in';outfile = 'translate.out';Varf: Array[1..1000] Of Boolean;s, i, l, c, m, n, r: longint;q: Array[1..1000] Of Longint;BeginAssign(input, infile);Reset(input);Assign(output, outfile);Rewrite(output);ReadLn(m, n);Fillchar(f, Sizeof(f), False);s := 0;l := 1;r := 0;For i:=1 To n Do BeginRead(c);If f[c] Then Continue;Inc(r);q[r] := c;Inc(s);f[c] := True;If r - l + 1 > m Then Beginf[q[l]] := False;Inc(l);End;End;WriteLn(s);Close(input);Close(output);End.【总结】实在没什么好说的，只要仔细就不会错。
