《金华一中信息学奥林匹克联赛(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 。