当前位置:首页 >> 学科竞赛 >>

2013安徽省省赛题


2013 安徽省省赛题

2013.05.30
2013 安徽省省赛裁判出题组

安徽省 2013 年“京胜杯”大学生程序设计 竞赛

A.单词反转
Time limit 1s Problem Description

给你一些英文句子,请将这些句子中的每个英语单词反转,然后再将其输出.这里听说的英 语单词仅由大小写英文字母组成. Input 多个英文句子,每句占一行,且每句不超过80个字符. Output 按题目要求输出 Sample Input Hello world! Happy programming,happy

life!

Sample Output olleH dlrow! yppaH gnimmargorp,yppah

efil!

B.等差数列
time limit 1s Problem Description
有一个长度为N(1<=N<=100000)的整数序列s[] ,在这个序列上定义了两种操作: Add L R A D:对于每一个i(L<=i<=R) ,S[i]+=A+(i-L)*D,也就是 在子序列S[L,R]加上首项A,公差为D的等差数列: Query L 列。 R:询问[L,R]区间内最长的等差数列的长度,亦即寻找最大的len,使S[i] , S[i+1] , . . . ,S[i+len-1] (L<=i<=R,L<=i+len-1<=R)构成等差数

Input
多组测试数据。 每组测试数据的第一行为两个正整数N(1<=N<=100000)和M(1<=M<=10000) , 分别代表序列的长度和操作个数,接下来有M行,每行代表一个操作,操作具体含义见题目描述。其中, 0<=L<=R<N,0<=A<=100000,0<=D<=10.

Output 对于每组测试数据,首先输出组号。然后对于每次询问,输出所求结果。详见样例输出。 Sample Input
5 3 Add 1 4 1 4 3 1 1 9 5 1 1 1 Query 0 Query 2 10 4 Add 0 Add 4 9 9

Query 0 Query 5

Sample Output
Case#1: 5 2 Case#2: 7 1

C.进程调度
time Limit 1s Proble Description 操作系统的一个重要功能是进行进程调度, 其进程调度的算法有多种, 其中最简单的调度算 法是先进先出服务(FCFS)算法,该算法的思想是:先进入就绪队列的先执行,后进入 的后执行, 同一时刻进入就绪队列的执行时间少的先执行。 我们认为某一进程一旦开始执行, 就一直占用处理机,直到执行结束。而一旦处理机被其它进程占用,就绪队列中的进程就必 须等待。当某一进程执行结束后,队列中排在最前面的进程就会立即执行。一个进程从进入 就绪队列到执行完毕所用的时间为其周转时间, 即周转时间=等待时间+执行时间。 现在给 你若干进程到达就绪队列的时间以及每个队列的执行时间, 请编程计算这些进程的平均周转 时间。 Input 多组测试数据。 每组测试数据的第一行为一个正整数N(N<=1000) ,表示要处理的进程数目。 接下来有N行,每行有两个正整数Ai(Ai<=1000)和Ei(Ei<=1000) , 分别表示一个进程到达就绪队列的时刻和执行该进程所需的时间。 Output 对于每组测试数据,输出平均周转时间,结果保留4位小数。 Sample Input
4 1 1 3 3 2 2 4 4

Sample Output
3.500

Hint 进程1等待时间为0,执行时间为1,其周转时间为0+1=1 进程3等待时间为0,执行时间为2,其周转时间为0+2=2 进程2等待时间为1,执行时间为3,其周转时间为1+3=4 进程4等待时间为3,执行时间为4,其周转时间为3+4=7 故平均周转时间为(1+2+4+7)/4=3.500

D.进击的巨人
题目描述: 艾伦作为第104期训练兵团卒业生于的NO.5,其它他还有一个特殊能力(主角光环) 在艾伦怀有强烈意志时进行自我伤害, 就能变身为最大15米级的巨人, 现在巨人已经突破 了赛罗之墙,如果不用巨大的石头堵上这堵墙的缺口的话,人类的领地就会进一步缩小,我 们用一个二维坐标(X0,Y0)表示巨人化的艾伦的初始位置,然后用(x1,y1)以 及R表示石块的以及(我们假设这个石块是圆形的) ,然后用2个点(x2,y2) , (x3, y3)表示罗塞之墙的缺口(一条线段) ,现在当务之急就是要把石块尽快搬到缺口处才行。 也就是要求所走的路径是从初始点到石块再到缺口处的距离之和最小。缺口肯定在石块外 输入: 多组数据输入,每组数据先是2个实数(x0,y0) ,然后再是x1,y1,R,接着再 是x2,y2,x3,y3. 输出: 对于每组数据,输出最短的路径的长度(结果保留2位小数) 样例输入:
1 1 0 0 1 0 1 1 0 0 1 -1 1. 00 2. 00 1 1 -2 1 2 0

样例输出:

E.巨人的进击
题目描述: 悠长的历史之中, 人类层一度因被巨人捕食而崩溃。 面临着生存危机而残存下来的人类建造 了三重巨大防护墙,这在100年内防止了巨人的入侵。不过,作为“和平”的代价,人类 也失去了到墙壁外面去的“自由” 。正在人们安逸了100年之际,一个前所未有的超大型 巨人出现了!那一天,人类终于回想起了,曾经一度被我们所支配的恐怖,还有被囚禁于鸟 笼中那份屈辱,五年前,艾伦-耶格尔目睹母亲遭巨人吞食后,立誓要消灭所有的巨人。而 现在超大型巨人又再次出现在艾伦的面前, 并破坏了罗塞之墙, 现在必须要尽快堵上这个缺 口,现在我们已知缺口是一个凸多边形, (不要在意这些细节) ,我们必须要尽可能的把缺口 堵上,那么得用多大的石块(石块假设是圆形的) 。 输入: 多组测试数据, 每组给出一个n表示凸多边形的定点个数, 然后再给出这些凸多边形的顶 点的位置(xi,yi) 。 (逆时针给出) 输出: 对于每组数据,给出最大的石块的半径(结束保留2位小数) 样例输入:
4 0 0 1 0 1 1 0 1

样例输出:
0. 50

F.闪光的指压师
题目描述: 桐奈是未来道具研究所的研究员 No.005,有重度的手机依存症,她沉默寡言到了与别人的 交流全部都要通过手机短信的地步(就算对方在眼前) ,她打字的速度是连眼睛都跟不上的 杰出的特技。她对手机的操作可谓是了如指掌(不是现在的智能机。 。 ) ,我们已知手机的每 个按键有不同的含义:

按键 1: , 。 ! 按键 2:a b c 按键 3: d e f 按键 4: g h I 按键 5:j k l 按键 6: m n o 按键 7: p q r s 按键 8: t u v 按键 9: w x y z 按键 0:空格 按键#:数字和拼音切换 按键 ok: (仅对一个按键下有多个字符含义时才会用到,按键 0 用到因为它在拼音模式下只 有空格这个含义而在数字含义下仅代表 0,按键#用不到,以及数字输入法下的 0 到 9 键) 最初是拼音输入法, 我们知道这个手机每次只能输入单个字符,如果要输入数字 9997,就要按下按键#,然后我 们按下按键 9 三次和按键 7 一次,如果要输入 cd,先按下按键 2 三次,然后按下 ok 键,接 着按下按键 3 一次,再按下按键 ok 即可,也可以先按下按键 2 三次,然后再按下按键 3(因 为按下其他按键就表示你已经确定了要输入按键 2 下的第几个字符了, 这里表示按键 2 下的 第三个字符) ,这样就输入了 c,最后按下按键 ok 就输入了 d,很明显后者需要的操作要少 一些, 现在桐奈要发送一系列的信息, 她想要尽可能快的输入这些信息 (就是操作尽可能少) , 那么该怎么办呢?还要注意在切换输入法的时候,例如 a1,只需按下按键 2 一次,然后按 下#键一次(因为切换了输入法,故接下来的按键内容与上次肯定不同,所以判定你已经确 定了按键 2 下的第几个字符了) ,然后按下按键 1 即可;也可以按下按键 2 一次,然后按下 ok 键,然后再按下按键#一次,接着按下按键 1 即可,不过后者操作要多一次。 输入: 多组测试数据,每组输入只有一行字符,字符仅包含, 。 !a 到 z 0 到 9 以及空格。 输出: 每一行输出相应的按键。 样例输入: 21412 fs f32 23jkljsf j32 样例输出: #21412#033377770333#32#0#23#5ok55ok555ok5777733305#32

G.Alice&Marisa
Problem Description Alice 和 Marisa 是一对好 CP。Alice 和 Marisa 都要向同一个商人 Reimu 购买节操。Reimu 手中有 N 份节操,她会将它们一份份地卖给他们,Alice 和 Marisa 通过竞价的方式来决定节 操的归属。具体的过程如下:Reimu 首先指定其中一个人开始报价,之后两人轮流报价,要 求是一定要比对方报的价格更高。任何时候,如果一个人不愿出价或者出不起价时,可以宣 布弃权,则对手以最后一次报的价格将节操买下。当然,如果两个人都没钱,Reimu 是不会 卖节操的。首先报价至少为 1,并且只能报整数的价钱。 Alice 和 Marisa 特别爱攀比,因此她们都希望能比对方买到更多的节操。Alice 和 Marisa 各 自带了 CA 和 CM 的钱用于竞拍节操。此外,Marisa 和 Reimu 有很不错的私人关系,因此 Reimu 总会让 Marisa 先报价。现在请问,在 Alice 和 Marisa 都用最优策略的情况下,谁能 买到更多的节操?假设双方都知道对方手中的现金数量,以及 Reimu 将要拍卖的节操数量 N。 Input 本题有多组数据。每组数据为一行三个用空格隔开的整数 N,CM,CA,表示节操的数量, 以及双方带的现金。0<=N<=100000,0<CM,CA<=1000000 Output 对于每组测试数据, 输出一行 X, X 的取值为{-1,0, 1}, -1 表示 Alice 买到的节操会比 Marisa 多,0 表示两个人能买到一样多,1 表示 Marisa 能买到更多的节操。 Sample Input 435 747 Sample Output 0 1

H.排列的前后
Problem Description 学霸向你讨教了全排列之后又自己仔细研究了一番信心满满又去面试另一家公司, 这次面试 官得知了上次全排列的经历后, 决定再次测试下不过这次的测试有点好玩, 考官表示只能手 算,要计算出给定的排列之后或者之前若干位置的排列是什么。 Input 本题有多组输入数据。每组数据两行,每一行一个字符串 s(1<=s 的长度<=26)第二行一个 整数 n(|n|<=2^90。s 是给定的前若干的大写字母组成的一排列。 Output 输出一行表示相对 s 位置为 n 的排列,若不存在这样的排列则输出“Are you kidding me . ” 这个字符串。 Sample BACD 2 BACD 0 BACD -2 BACD 9999 Sample Output BCAD BACD ADBC Are you kidding me.

I.

散步

Problem Description @每天吃完晚饭后都会从家出发到雾之湖及其周围去散步下,最终到达魔方森林的入口,并 尽可能尝试不同的路径。雾之湖及其周围可以抽象为一个矩形,划分为 n*m 块区域,@家 为(1,1) ,散步时@在某个区域会逗留一段时间,然后移动到东西南北相邻的其中一个格子 (移动时间忽略不计) ,经过若干次移动最终到达魔法森林(n,m) 。因为是散步,所以起 点和终点@都会逗留一段时间。@表示虽然是闲逛,但是也不能太浪费时间,还是得去终点 (n,m)的,所以至少存在一条从 B 到终点的时间比从 A 到终点的所有路径所花费的时间 更少时才可以从 A 到 B。 现在@想知道自己一共有多少种路径可以选择, 因为@的至少只有 @,她自己肯定没法算出来啦。你能帮帮@吗?? Input 本题有多组数据。每组数据第一行为 n,m(2<=n,m<=50)接下来为 n 行 m 列的矩阵,表 示在每个区域@逗留的时间 t(0<=t<=1000). Output 每组数据输出一行,表示路径总数(保证小于 2^63). Sample Input 33 123 123 123 33 111 111 111 Sample Output 1 6

J.IQ test?
Problem Description 猜数游戏在 XXX 国非常流行 游戏过程大概是这样的?? 一个裁判, 三个路人, 路人足够聪明\\你可以认为路人是 petr, acrush, tourist 之类的生物?? 每次裁判会选出三个正整数,其中某两个相加等于第三个 然后分别把这数写在三个路人的脸上 \\--||| 不要在意这下细节 也就是说,每个路人都知道另外两个路人的数字但不知道自己脸上的数是什么 游戏开始,裁判每一轮都会问他们三个能否猜出自己脸上是什么,为了体现游戏的公正性, 路人们必须同时给出回答。 直到有一个路人猜出自己的数时游戏停止 那么,如果告诉你这三个数 a,b,c,为了证明你比路人厉害,你能预测出游戏会在第几轮 停止吗? Input 每行三个正整数 a,b,c, (1<=a,b,c<=200) \\保证其中一个是另外两个的和 以 0 0 0 结束 Output 输出一个数,表示游戏在第几轮结束 Sample Input 112 123 321 000 Sample Output 1 2 2

\\从 1 开始计数

K.IQ test2
Problem Description 还是和 IQ test 一模一样的猜数游戏 路人们玩了几把后觉得 200 以下的数不能体现出他们强大的计算能力 随后一致认同把数字范围扩大到 10^18 之内 ?? ?? 现在,你还能帮助裁判预测游戏会在第几轮结束吗?? Input 每行三个正整数 a,b,c(1<=a,b,c<=10^18) 以 0 0 0 结束 Output 输出一个数,表示游戏在第几轮结束 \\从 1 开始计数 Sample Input 112 123 321 000 Sample Output 1 2 2

L.The end of the world
Problem Description 世界在流动 简单的说,你可以把世界想象成许多空间的集合(n 个)和连接这些空间的双向通道(n-1 条) ,并且任意两个空间都能相互连通,于是得到一个简化版的世界。 在这个世界中, 存在许多虚拟生命, 任何一个虚拟生命可以进入通道到达另一个空间它们从 来不走回头路,所以世界的流动必将停止。 为了使模型更加简单,假设每个空间中都有一只虚拟生命。由于世界的对称性,它们选择任 何一条通道的概率都是均等的(走过的除外) 。作为一个优秀的程序员,请计算世界终结时 每个空间中虚拟生命数量的期望。最后,这些期望中一定有个最大的,找到它,并且输出。 Input 第一行有一个数 n(3<=n<=100000) ,表示空间的数量(空间编号从 1 到 n) 接下来有 n-1 行,每行有两个整数 a,b(1<=a,b<=n) ,表示空间 a 和空间 b 之间存在一条 通道。 以 n=0 结束 Output 输出一个数,表示世界终结时所有空间的期望值中最大的那一个(保留三位小数) Sample Input 3 12 13 4 12 13 24 Sample Output 1.500 2.000

目录
A.单词反转..................................................................................................... 错误!未定义书签。 B.等差数列 ..................................................................................................... 错误!未定义书签。 C.进程调度 ..................................................................................................... 错误!未定义书签。 D.进击的巨人................................................................................................. 错误!未定义书签。 E.巨人的进击 ................................................................................................. 错误!未定义书签。 F.闪光的指压师.............................................................................................. 错误!未定义书签。 G.Alice&Marisa .............................................................................................. 错误!未定义书签。 H.排列的前后................................................................................................. 错误!未定义书签。 I.散步 .............................................................................................................. 错误!未定义书签。 J.IQ test?和 K.IQ test 2 ................................................................................... 错误!未定义书签。 L.the end of the world ..................................................................................... 错误!未定义书签。


相关文章:
2013年安徽省中学生生物学竞赛预赛试卷及答案
2013安徽省中学生生物学竞赛预赛试卷及答案_学科竞赛_高中教育_教育专区。2013安徽省中学生生物学竞赛预赛试卷注意事项: 1、本试卷共 100 题,全部为选择题,每...
2013—2015年全国高中化学竞赛(安徽赛区)初赛试题及答案
2013-2015 年化学竞赛(安徽赛区)初赛试题 第 6 页共 26 页 2015 年化学竞赛(安徽赛区)初赛试题参考答案与评分标准一、本题包括 15 小题,每小题 2 分,共 ...
安徽省2013年“京胜杯”大学生程序设计竞赛题目及解题...
安徽省2013年“京胜杯”大学生程序设计竞赛题目及解题报告_计算机软件及应用_IT/计算机_专业资料。2013 安徽省省赛题解 2013.05.30 2013 安徽省省赛裁判出题组 安...
2013安徽省初赛试题(含答案)
2013安徽省初赛试题(含答案)2013安徽省初赛试题(含答案)隐藏>> 第1 页 第 2 页 第 3 页 第 4 页 分享到: X 分享到: 使用一键分享,轻松赚取财富值...
2013安徽省信息学竞赛试题(小学组)
2013安徽省信息学竞赛试题(小学组)_五年级其它课程_其它课程_小学教育_教育专区。2013 年安徽省青少年信息学奥林匹克竞赛 小学组试题 2013 年安徽省青少年信息学奥林...
2013年安徽省中学生生物学竞赛预赛试题及参考答案
2013安徽省中学生生物学竞赛预赛试题及参考答案_学科竞赛_高中教育_教育专区。电子稿,可直接打印使用!2013安徽省中学生生物学竞赛预赛试卷注意事项: 1、本试卷共...
2013年安徽省中学生生物学竞赛预赛试题及参考答案_图文
2013安徽省中学生生物学竞赛预赛试卷注意事项: 1、本试卷共 100 题,全部为选择题,每小题 1 分,共 100 分;每小题答案完全正确得 1 分,错选、多选、漏...
2013年安徽省职业院校技能大赛比赛试题
2013安徽省职业院校技能大赛”中职组计算机技术——企业网竞赛 “2013安徽省职业院校技能大赛”中职组计算机技术——企业网项目 竞赛赛题 2013安徽省...
2013-2015年安徽省数学竞赛初赛答案
2013-2015年安徽省数学竞赛初赛答案_学科竞赛_高中教育_教育专区。2013-2015年...2015 年全国高中数学竞赛安徽赛区初赛答案一、填空题(每题 8 分,共 64 分) ...
2013年安徽省中学生生物学竞赛预赛试题及参考答案_图文
2013安徽省中学生生物学竞赛预赛试卷注意事项: 1、本试卷共 100 题,全部为选择题,每小题 1 分,共 100 分;每小题答案完全正确得 1 分,错选、多选、漏...
更多相关标签: