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

2015年广东省青少年信息学竞赛广州市选拔赛


2015 年广东省青少年信息学竞赛广州市选拔赛 2015 年广东省青少年信息学竞赛广州市选拔赛

2015 年 3 月 28 日
注意事项: 1. 严格按照题目所要求的格式进行输入、输出,否则严重影响得分。 2. 题目测试数据有严格的时间限制,超时不得分。 3. 输入文件格式不用判错;输入输出文件名均已给定,不用键盘输入。 4. 源程序保存在以“序号

+姓名”命名的文件夹下,按题目要求命名。评测以源程序为准。 5. 四个小时完成。 6. 内存限制:256MB,代码长度限制 32KB。 7. 本次竞赛的最终解释权归 GDOI 评委会所有。 试题名称 提交文件名 输入文件名 输出文件名 满分 石子游戏
stone.pas/c/cpp stone.in stone.out

找回密码 pwd.pas/c/cpp pwd.in pwd.out 100

约瑟夫问题 josephus.pas/c/cpp josephus.in josephus.out 100

字符消除
string.pas/c/cpp

string.in string.out 100

100

第一题 石子游戏
提交文件:stone.pas/c/cpp 输入文件:stone.in 输出文件:stone.out

问题描述
Alice 和 Bob 总喜欢聚在一起玩游戏(T_T) ,今天他(她)们玩的是一款新型的取石 子游戏。游戏一开始有 N 堆石子,Alice 和 Bob 轮流取出石子。在每次操作中,游戏者必 须选择其中的一堆石子,并作出下列的其中一种操作: (1) 移去整堆石子 (2) 假设石子堆中有 X 颗石子,取出 Y 颗石子,其中 1<=Y<X,并且 X 和 Y 的最大公约数 是 1。 游戏结束的条件是:取出最后一颗石子的人胜出。众所周知,Alice 和 Bob 都是绝顶聪 明的,假设他们在游戏中都采取最优的策略,问最后谁会胜出游戏呢?

输入格式
第一行包含一个整数 T,表示测试数据的组数。 接下来 T 组测试数据,在每组数据中,第一行包含一个整数 N,表示有多少堆石子。第 二行 N 个正整数,分别表示每堆有多少颗石子。

输出格式
每组测试数据输出一行,表示获胜者的名字(Alice 或者 Bob) 。

2015 年广东省青少年信息学竞赛广州市选拔赛 输入样例:
3 3 3 5 6 4 2 3 6 9 5 3 2 1 1000000 999999

输出样例:
Alice Bob Alice

数据范围
20%的数据,N<=5,每堆石子数量少于 10 100%的数据,T<=100,N<=100,每堆石子数量不大于 1,000,000

第二题 找回密码
提交文件:pwd.pas/c/cpp 输入文件:pwd.in 输出文件:pwd.out

问题描述
Kevin 是一个热爱字符串的小孩。有一天,他把自己的微信登录密码给忘记了,万般无 奈之下只好点“找回密码” 。 这时候,网页上出现了当初设定的密保问题:在字符串 st 中,有若干个内容不同的子 串,请问其中字典序第 k 小的子串是什么? 很可惜的是,Kevin 现在已经不会写程序了,所以,他找到了睿智的你来帮忙。

输入格式
输入数据包括两行:第一行为字符串 st,第二行为正整数 k,定义如题目描述。 其中字符串 st 的长度不超过 100,000 且只由大小写英文字母组成

输出格式
一行,为第 k 小的字符串,如果字符串 st 中不足 k 个不同的子串,则输出字典序最大 的一个。 输入样例:
AAB 2

输出样例:
AA

数据范围
50%的数据,|st| <=1000 100%的数据,|st|<=100,000,K < 2^63

2015 年广东省青少年信息学竞赛广州市选拔赛

第三题 约瑟夫问题
提交文件:josephus.pas/c/cpp 输入文件:josephus.in 输出文件:josephus.out

问题描述
现有 N*(N+1)/2 个人围成一圈,编号从 1 到 N*(N+1)/2,其中编号 i 与编号 i+1 的人相 邻,编号 N*(N+1)/2 与编号 1 相邻。如今,我们要执行 N-1 个阶段的杀人仪式,在第一个阶 段开始前,从编号为 1 的人开始报数。在第 i 阶段中,报到 n+1-i 这个数的人要被杀害,之 后从被杀害者的下一个相邻的人开始从 1 开始报数,在第 i 个阶段里需要杀死 i 个人,随后 即可进入下一个阶段,更具体地说: 在第 1 个阶段中,报数为 N 的人会被杀害,在这个阶段中需要杀死 N 个人; 在第 2 个阶段中,报数为 N-1 的人会被杀害,在这个阶段中需要杀死 N-1 个人; . . . 在第 n-1 个阶段中,报数为 2 的人会被杀害,在这个阶段中需要杀死 2 个人。 仪式结束后,会剩下一个幸存者,请问这位幸存者的编号是多少?

输入格式
第一行一个整数 T,表示数据的组数。 接下来 T 行,每行一个整数 N,N 定义如题目所述。

输出格式
输 出 一 个 整 数 , 表 示 幸 存 者 的 编 号 输入样例:
3 1 2 3

输出样例:
1 3 2

数据范围
20%数据,1<=n<=100,T <=10 40%数据,1<=n<=100,000,T<=10 100%数据,1<=n<=5,000,000,T<=100000

2015 年广东省青少年信息学竞赛广州市选拔赛

第四题 字符消除
提交文件:string.pas/c/cpp 输入文件:string.in 输出文件:string.out

问题描述
给定两个字符串 A 和 B,你的任务是把两个字符串的所有字符消除掉,每次执行消除, 你可以选取使用下列的其中一种方式: (1) 消除 A 字符串当前的第一个字符, 如果该字符为原来 A 串中的第 i 位, 那么需 要花费 costA[i]的代价; (2) 消除 B 字符串当前的第一个字符, 如果该字符为原来 B 串中的第 i 位, 那么需 要花费 costB[i]的代价; (3) 同时消除 A 字符串和 B 字符串的第一个字符, 如果该字符为原来 A 串中的第 i 位和原来 B 串中的第 j 位,那么需要花费 costAB[i][j]的代价。 消除的总代价为每一步操作代价的总和,当然我们需要将总代价最小化。同时,当我们 选择执行(1)操作的时候,我们可以选择对 B 串进行旋转(言下之意,就是将 B 串分成两部 分,然后交换位置之后连在一起,如“yaouf”可以旋转成“oufya” ) 。 现在,请问消除的最小总代价是多少?

输入格式
第一行两个整数 M,N。表示 A 串和 B 串的长度。 第二行 M 个整数,表示 costA[1] 至 costA[M]; 第三行 N 个整数,表示 costB[1] 至 costB[N]; 接下来 M 行,每行 N 个整数,第 i 行第 j 个数表示 costAB[i][j]。

输出格式
输 出 一 个 整 数 , 表 示 最 小 的 总 代 价 输入样例:
4 4 2 4 6 7 8 10 12 10 14 16 18 17 13 17 5 19 2 4 6 14 1 10 12 3

输出样例:
29

数据范围
30%的数据,M,N<=100

2015 年广东省青少年信息学竞赛广州市选拔赛 50%的数据,M,N<=500 100%的数据,M,N<=1000, 所有 cost 的数非负且不大于 1000


相关文章:
附中学子在2015年全省信息学代表队选拔赛中一枝独秀
附中学子在2015年全省信息学代表队选拔赛中一枝独秀_其它课程_高中教育_教育专区...日举行的安徽省 青少年信息学奥林匹克竞赛暨信息学代表队选拔赛中,获得 优异成绩...
2015小学生信息学竞赛试题
2015小学生信息学竞赛试题_学科竞赛_小学教育_教育专区。2015小学生信息学竞赛试题 中山市第七届小学生信息学邀请赛试题比赛时间:2015 年 4 月 19 日上午 9:00...
NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛普及组C语言试题
NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛普及组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛普及组C语言...
2015年世界青少年奥林匹克数学竞赛(中国区)选拔赛广东省赛区决赛试卷五年级试题
2015年世界青少年奥林匹克数学竞赛(中国区)选拔赛广东省赛区决赛试卷五年级试题_学科竞赛_小学教育_教育专区。2015年世界青少年奥林匹克数学竞赛(中国区)选拔赛广东省...
第13届2015少儿信息学竞赛笔试试题
第13届2015少儿信息学竞赛笔试试题_学科竞赛_小学教育_教育专区。第十三届绍兴市...“心理博弈” ,单次的输赢可能 更多取决于运气,但是多次比赛的话,赢家一定是个...
NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言试题
NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言...
2014中山市选拔赛
2014中山市选拔赛_学科竞赛_初中教育_教育专区。OI Guangdong Zhongshan2014 年广东省青少年信息学竞赛中山市选拔赛 2014 年广东省青少年信息学竞赛中山市选拔赛 2014...
广州信息选拔赛2014
2014 年广州市信息学尖子选拔赛第一试 3 月 29 日 2014 年广州市信息学尖子选拔赛所有文件必须严格按题目要求输入输出,不要有多余的空格或空行,所有输 出文件...
第十八届全国青少年信息学奥林匹克联赛初赛
第十八届全国青少年信息学奥林匹克联赛初赛_学科竞赛_初中教育_教育专区。第十八届...体育比赛中,每一级比赛的优胜者晋级上一级比赛 11.矢量图(Vector Image)图形...
更多相关标签:
广东省信息学奥赛 | 青少年信息学奥林匹克 | 全国青少年信息学竞赛 | 全国青少年信息学联赛 | 2016全国青少年信息学 | 全国青少年信息学奥赛 | 青少年信息学竞赛官网 | 青少年信息学奥赛 |