2013安徽省青少年信息学奥林匹克竞赛中学组试题

《2013安徽省青少年信息学奥林匹克竞赛中学组试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2013年安徽省青少年信息学奥林匹克竞赛中学组试题2013年安徽省青少年信息学奥林匹克竞赛中学组试题AOI2013（请选手仔细阅读本页内容）比赛用时（5小时）竞赛时间：2013年5月18日8:00-13:00题目名称体育课打地鼠公交系统目录sportmolebus可执行文件名sport.exemole.exebus.exe输入文件名sport.inmole.inbus.in输出文件名sport.outmole.outbus.out每个测试点时限1秒2秒2秒内存限制256M256M256M测试点数目1020

2、10每个测试点分值10510是否有部分分否否否题目类型传统型传统型传统型提交源程序须加后缀对于Pascal语言sport.pasmole.pasbus.pas对于C语言sport.cmole.cbus.c对于C++语言sport.cppmole.cppbus.cpp注意：最终测试时，所有编译命令均不打开任何优化开关。安徽合肥2013.5.1812013年安徽省青少年信息学奥林匹克竞赛中学组试题体育课【故事背景】JYY很喜欢踢足球，所以一到体育课JYY就很高兴。但是今天JYY在上课前听说体育老师KFC要在排

3、队的时候让个子最高的几个同学去帮PUPPY老师搬桌子，这可急坏了JYY（搬桌子去了就没球踢了）。JYY需要想一个好的办法，使得自己在排队的时候站的尽量靠后些。【问题描述】体育课里一共有N个同学，学号分别为1到N，JYY的学号是P。学号为i的同学的身高为hi。JYY的体育老师KFC有一个特殊排队方法：KFC先让班里的N个同学按照学号从小到大的顺序，从左到右站成一排，然后从到队列的最左边（也就是第一个学生面前）开始，一直向右走动到第N-1个学生面前；接着KFC再回到第一个学生面前，继续开始向右走，就这样一共

4、走动N-1次。每次当KFC走到第i个学生面前时，KFC会比较一下队列里第i个学生和第i+1个学生的身高，如果左边（第i个）的学生比右边（第i+1）的学生高，那么KFC就会交换这两个学生在队列里的位置。最终，在N-1次走动全部结束之后，KFC会选出队列最右边的一些学生去搬桌子。自然的，JYY希望能够站在尽量靠左的位置来增加自己踢足球的机会。此外，JYY还有一个绝招，那就是在KFC老师快走到自己面前的时候，开始蹲下来系鞋带！如果JYY蹲下来系鞋带了，那么在这一次走动中，好说话的KFC老师就不会让JYY和相邻的

5、同学比较身高了，自然也就不会让JYY和相邻的同学交换位置。（只有JYY最聪明会蹲下来系鞋带，其他同学都只会老老实实的让KFC老师比较身高）蹲下来系鞋带是很耗费体力的。为了留着体力踢足球，JYY最多只能蹲下K次。JYY想知道，按照怎样的下蹲策略可以使自己在队列里站的尽量靠左。我们用一个长度为N-1的字符串来表示一个策略：如果字符串的第i个字符是“+”，则表示在第i次走动时JYY蹲下来系鞋带；如果第i个字符是“-”，则表示JYY会老老实实的比较身高。【输入格式】从文件sport.in中读入数据。第一行包含三

6、个整数N，P，K。第二行包含N个整数，第i个整数表示hi。安徽合肥2013.5.1822013年安徽省青少年信息学奥林匹克竞赛中学组试题【输出格式】输出到文件sport.out中。输出文件的第一行包含一个正整数，表示按照最优策略JYY可以排在的最靠左的位置。输出文件的第二行包含一个长度为N-1的字符串，表示最佳策略。如果有多个最佳策略，JYY希望知道字典序最大的策略。注意：此题没有部分分！【样例输入】10778354574213【样例输出】3----+++++【数据规模与约定】对于20%的数据满足N≤10

7、；对于50%的数据满足N≤3000；59对于100%的数据满足1≤P≤N≤10，0≤K≤N-1，1≤hi≤10。安徽合肥2013.5.1832013年安徽省青少年信息学奥林匹克竞赛中学组试题打地鼠【故事背景】JYY特别喜欢到游戏厅玩打地鼠游戏——拿起两个锤子用力敲打不断冒出来的地鼠。打到不同的地鼠有不同的得分，JYY想知道怎样才能得到最高的分数。【问题描述】游戏里一共会冒出来N个地鼠，这些地鼠冒出来的位置都分布在一条直线上。第i个地鼠会在Ti时刻在Xi位置冒出来，打到第i个地鼠的得分是Pi。当游戏开始时

8、（也就是0时刻），JYY左手的位置为XLEFT，右手的位置为XRIGHT。JYY的手的最大移动速度是V（每单位时刻最多移动的距离为V）。地鼠会在瞬间冒出来然后消失。如果在对应的时刻JYY的一只手恰好也在地鼠冒出来的位置，那么JYY就可以在瞬间完成击打动作并得到对应的分数；否则，JYY就只能错过这只地鼠了。JYY两只手都拿着锤子，所以两只手是可以同时打地鼠的。然而，如果在游戏过程中JYY的两只手交叉的话，JYY会感到很不舒服（