《金华一中信息学奥林匹克联赛(NOIP2009)复赛模拟试题》由会员分享，可在线阅读，更多相关《金华一中信息学奥林匹克联赛(NOIP2009)复赛模拟试题（6页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 6 页金华一中信息学奥林匹克联赛（NOIP2009）复赛模拟试题（三）一、题目概览中文题目名称 遥控车 车展 拉力赛 舞台设置英文题目名称 car exhibit rally stage可执行文件名 car exhibit rally stage输入文件名 car.in exhibit.in rally.in stage.in输出文件名 car.out exhibit.out rally.out stage.out每个测试点时限 1 秒 1 秒 1 秒 1 秒测试点数目 10 10 10 10每个测试点分值 10 10 10 10比较方式 全文比较 全文比较 全文比较 全文比较
2、二、运行内存限制运行内存上限 512 M 512 M 512 M 512 M第一题：遥控车【题目描述】平平带着韵韵来到了游乐园，看到了 n 辆漂亮的遥控车，每辆车上都有一个唯一的名字namei。韵韵早就迫不及待地想玩名字是 s 的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个 i，使 s 是 namei的前缀） ，这时她就能玩第 i 辆车；或者是一个无中生有的名字，即 s 不是任何一辆车名字的前缀，这时候她什么也不能玩。你需要完成下面的任务：1.韵韵想了 m 个她想要的名字，请告诉她能玩多少次。2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错
3、，原来第 i 辆车现在的位置可能是 i-1、i、i+1 中的任意一个（第 1 辆车的位置不可能是 0，第 n 辆车的位置不可能是 n+1） 。请你计算出共有多少种可能的排列。注：数据保证当 s 是 namei的前缀时，i 是唯一确定的。一辆车可以玩多次。【输入格式】第一行是 2 个正整数 n、m。接下来 n 行，每行 1 个字符串 namei，表示第 i 辆车的名字。接下来 m 行，每行 1 个字符串 s，表示韵韵想要的名字。【输出格式】第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。【输入样例】4 4AbcdDeFAAaaBccc第 2 页 共 6 页AbAAAbCaBcc【输出样
4、例】35对于题目涉及到的字符串严格区分大小写，且长度小于 255。对于 20的数据 n10,m 10；对于 40的数据 n1000，m 1000；对于 100的数据 n10000，m 10000。第二题：车展【题目描述】遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办 m 次车展。车库里共有 n 辆车，从左到右依次编号为 1，2，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度 hi。主管已经列好一张单子：L1 R1L2 R2Lm Rm单子上的(Li,Ri)表示第 i 次车展将要展出编号从 Li 到 Ri 的车。为了更加美观，展览时需要调整展台的高度，使参展所有展台的高
5、度相等。展台的高度增加或减少 1 都需花费 1 秒时间。由于管理员只有一个人，所以只好对每个展台依次操作。每次展览结束后，展台高度自动恢复到初始高度。请告诉管理员为了举办所有展览，他最少需要花多少时间将展台调整好。【输入格式】第一行为两个正整数 n、m。第二行共 n 个非负整数，表示第 i 辆车展台的高度 hi。接下来 m 行每行 2 个整数 Li、Ri（LiRi） 。【输出格式】一个正整数，调整展台总用时的最小值。【输入样例】6 44 1 2 13 0 91 52 63 42 2【输出样例】48【数据范围】第 3 页 共 6 页对于 50的数据 n500，m 1000；对于 80的数据 n1
6、000，m 100000；对于 100的数据 n1000，m 200000；答案在 264 以内。第三题：拉力赛【题目描述】车展结束后，游乐园决定举办一次盛大的山道拉力赛，平平和韵韵自然也要来参加大赛。赛场上共有 n 个连通的计时点，n-1 条赛道（构成了一棵树） 。每个计时点的高度都不相同（父结点的高度必然大于子结点） ，相邻计时点间由赛道相连。由于马力不够，所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。举办方共拟举办 m 个赛段的比赛，每次从第 u 个计时点到第 v 个计时点，当然其中有不少比赛韵韵的遥控车是不能参加的（因为要上坡） 。平平想知道他能参加多
7、少个赛段的比赛，并且想知道他完成这些赛段的总用时。【输入格式】第一行两个整数 n，m。接下来 n-1 行每行 3 个整数 a、b、t。表示韵韵的遥控车可以花 t 秒从第 a 个计时点到第 b 个计时点。接下来 m 行每行 2 个整数 u、 v，意义如描述所示。【输出格式】第一行输出一个正整数，表示能参加的赛段数。第二行输出一个正整数，表示总用时。【输入样例】6 21 2 12 4 12 5 15 6 11 3 12 64 5【输出样例】12【提示及范围】第一个计时点的高度是最高的；uv；对于 50的数据 n1000 m 1000；对于 100的数据 n10000 m 100000；答案小于 2
8、64。第 4 页 共 6 页第四题：舞台设置【题目描述】游乐园决定在一个 nm 的广场上举办一次颁奖晚会，总管要你帮忙搭建一个舞台。现在给你广场的布置图（规定地图的上方为正北） ，有些位置需要布置为观众席（记为 1） ，另一些是空地（记为 0） 。舞台只能在空地上搭建。为了使晚会更加吸引人，平平觉得舞台应该是朝北的 h金字塔形。h金字塔形舞台是由 h个矩形舞台相接而成的，其中后方的矩形舞台的两端必须超出在其前面的矩形舞台，且最小矩形面对的朝向为舞台的方向。下面给出几个实例:第 5 页 共 6 页舞台的面积应该尽量大，输出面积最大的朝北 h金字塔形舞台的面积。【输入格式】第一行 3 个整数 n、m、h。接下来 n 行，每行 m 个 0 或 1，中间用一个空格隔开。【输出格式】一个整数，表示最大的朝北的 h金字塔形舞台的面积。如果没有符合题意的 h金字塔形舞台输出 0。【输入样例】4 6 20 0 1 0 0 10 0 0 0 0 00 0 1 0 0 00 1 1 0 0 0【输出样例】10【样例说明】第 6 页 共 6 页【数据范围】对于 10的数据 h=1；对于 40的数据 h5；对于 100的数据 h20；对于 100的数据 n、m100 。
