金华一中信息学奥林匹克联赛NOIP2009复赛模拟试题汇总

1、金华一中信息学奥林匹克联赛(NOIP2009 )复赛模拟试题、题目概览中文题目名称遥控车车展拉力赛舞台设置英文题目名称carexhibitrallystage可执行文件名carexhibitrallystage输入文件名car.inexhibit.inrally.instage.in输出文件名car.outexhibit.outrally.outstage.out每个测试点时1秒1秒1秒1秒限测试点数目10101010每个测试点分10101010值比较方式全文比较全文比较全文比较全文比较二、运行内存限制运行内存上限512 M512 M512 M512 M第一题：遥控车【题目描述】平平带着韵韵来

2、到了游乐园，看到了 n辆漂亮的遥控车，每辆车上都有一个唯一的 名字namei。韵韵早就迫不及待地想玩名字是 s的遥控车。可是韵韵毕竟还小， 她想象的名字可能是一辆车名字的前缀（也就是说能确定一个i,使s是namei的前缀），这时她就能玩第i辆车；或者是一个无中生有的名字，即 s不是任何一辆 车名字的前缀，这时候她什么也不能玩。你需要完成下面的任务：1 .韵韵想了 m个她想要的名字，请告诉她能玩多少次。2 .由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第 i辆车现在的位置可能是i-1、i、i+1中的任意一个（第1辆车的位置不可能是0, 第n辆车的位置不可能是n+1） o请

3、你计算出共有多少种可能的排列。注：数据保证当s是namei的前缀时，i是唯一确定的。一辆车可以玩多次。【输入格式】第一行是2个正整数n、m。接下来n行，每行1个字符串namei,表示第i辆车的名字。接下来m行，每行1个字符串s,表示韵韵想要的名字。【输出格式】第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。【输入样例】4 4AbcdDeFAAa aBcccAbAAAbCaBcc【输出样例】35对于题目涉及到的字符串严格区分大小写,且长度小于255。对于20%的数据n&10,m0 1;0对于 40% 的数据 n0 1000 me 1000;对于 100% 的数据 n0 1000

4、0 me 1000(1第二题：车展【题目描述】遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1, 2,，n,每辆车都有一个展 台。刚开始每个展台都有一个唯一的高度 hi。主管已经列好一张单子：L1 R1L2 R2Lm Rm单子上的(Li,Ri表示第i次车展将要展出编号从Li到Ri的车。为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人，所以只好对每个展 台依次操作。每次展览结束后，展台高度自动恢复到初始高度。请告诉管理员为了举办所有展览，他最少需要花多少时

5、间将展台调整好。【输入格式】第一行为两个正整数n、m。第二行共n个非负整数，表示第i辆车展台的高度hi。接下来m行每行2个整数Li、Ri （Li & Ri 。【输出格式】一个正整数，调整展台总用时的最小值。【输入样例】6 44 1 2 13 0 91 52 63 44 2【输出样例】48【数据范围】对于50%的数据n0500 me 1000;对于 80% 的数据 n0 1000 me 100000；对于 100% 的数据 n0 1000 me 200000;答案在2A64以内。第三题：拉力赛【题目描述】车展结束后，游乐园决定举办一次盛大的山道拉力赛，平平和韵韵自然也要来参加 大赛。赛场

6、上共有n个连通的计时点，n-1条赛道（构成了一棵树）。每个计时点的高度 都不相同（父结点的高度必然大于子结点），相邻计时点间由赛道相连。由于马力不够，所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。举办方共拟举办m个赛段的比赛，每次从第u个计时点到第v个计时点，当然其 中有不少比赛韵韵的遥控车是不能参加的（因为要上坡）。平平想知道他能参加多 少个赛段的比赛，并且想知道他完成这些赛段的总用时。【输入格式】第一行两个整数n, m。接下来n-1行每行3个整数a、b、t。表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。接下来m行每行2个整数u、v,意义如描述所示

7、。【输出格式】第一行输出一个正整数，表示能参加的赛段数。第二行输出一个正整数，表示总用时。【输入样例】6 21 2 12 4 13 5 15 6 11 3 12 64 5【输出样例】1【提示及范围】第一个计时点的高度是最高的;对于50%的数据n0 1000 m0 1000对于 100% 的数据 n0 10000 m< 100000答案小于2A64。第四题：舞台设置【题目描述】游乐园决定在一个n>m的广场上举办一次颁奖晚会，总管要你帮忙搭建一个舞 台。现在给你广场的布置图（规定地图的上方为正北），有些位置需要布置为观众席 （记为1）,另一些是空地（记为0）。舞台只能在空地上搭建。为了

8、使晚会更加吸引人，平平觉得舞台应该是朝北的h一金字塔形。h一金字塔形舞台是由h个矩形舞台相接而成的，其中后方的矩形舞台的两端必须超出在其前面 的矩形舞台，且最小矩形面对的朝向为舞台的方向。下面给出几个实例：这是 个朝北山fl泡是20的3-食字塔 膨谣台.这行是上7塔形舞花冈为门化向由第 :个矩形西端没行超过通一个却形,这是一个朝西任面枳为12的2 *.；, 形舞台这不是一个金字塔形舞件.因为矩形没 有相接.舞台的面积应该尽量大，输出面积最大的朝北 h金字塔形舞台的面积【输入格式】第一行3个整数n、m、ho接下来n行，每行m个0或1,中间用一个空格隔开。【输出格式】一个整数，表示最大的朝北的h一金字塔形舞台的面积如果没有符合题意的h金字塔形舞台输出00【输入样例】4 6