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

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


相关文章:
2013德清青少年信息学竞赛试卷
2013德清青少年信息学竞赛试卷_学科竞赛_小学教育_教育专区。2013 年德清县信息学竞赛(初中)说明:比赛时间:120 分钟 满分:100 分 请将答案填写(选择题为涂写)在...
2015年山东省信息学奥赛总结表彰会议通知(最新)
(2015 年)全国青少年信息学奥林匹克联赛(NOIP2015) (山东赛区) , 经过 2015 ...竞赛与环境; ◆山东省 2016 夏令营时间与课程安排; ◆2016 年省队选拔赛安排;...
2010年青少年信息学竞赛合肥市队选拔赛小学组试题
2010/4/11 合肥 第1页 共 5页 2010 年青少年信息学竞赛合肥市队选拔赛 第一题 最大公约数 (gcd.pas/gcd.cpp/gcd.c) 【题目描述】 给你两个正整数 A...
2010年青少年信息学竞赛阜阳市队选拔赛小学组试题
2010年青少年信息学竞赛阜阳市队选拔赛小学组试题 2011阜阳市信息学奥林匹克选拔小学组测试题 可以用作考前训练 也可以作为考题使用。2011阜阳市信息学奥林匹克选拔小...
2010年青少年信息学竞赛阜阳市队选拔赛中学组试题
2010年青少年信息学竞赛阜阳市队选拔赛中学组试题 可以作为练习题 或者考试题目2010年青少年信息学竞赛阜阳市队选拔赛中学组试题 可以作为练习题 或者考试题目隐藏>> ...
关于组织参加2015嘉兴市青少年信息学小学组竞赛的通知...
2015嘉兴市青少年信息学小学组竞赛将于 2015年 4月 11 日举行,为了组织好海宁...团体总分计算办法:以每个学校比赛成绩前 10 名选手的总分作为该校团体成绩,择优...
2015年蜀山区青少年信息学竞赛小学组试题
2015年蜀山区青少年信息学竞赛小学组试题_学科竞赛_小学教育_教育专区。小学信息学竞赛真题 2015年蜀山区青少年信息学竞赛 小学组试题一、题目概况题目名称 文件名 ...
附中学子在2015年全省信息学代表队选拔赛中一枝独秀
附中学子在2015年全省信息学代表队选拔赛中一枝独秀_其它课程_高中教育_教育专区...日举行的安徽省 青少年信息学奥林匹克竞赛暨信息学代表队选拔赛中,获得 优异成绩...
2015小学生信息学科普日活动试题
2015小学生信息学科普日活动试题_学科竞赛_小学教育_教育专区。2015年信息学北京市市赛题目 2015 年北京小学生信息学科普日活动试题考试时间: 2015 年 11 月 15 ...
怎样做好信息学奥赛培训辅导
信息学奥林匹克竞赛是智力与计算机应用的比赛,是推动...2、我对信息学奥赛的了解 青少年信息学(计算机)奥...2015 年 11 月份全国组织的奥林匹 克竞赛复赛,我们...
更多相关标签:
广东省信息学竞赛 | 广东省信息学竞赛培训 | 全国青少年信息学联赛 | 青少年信息学奥林匹克 | 青少年信息学竞赛 | 全国青少年信息学竞赛 | 青少年信息学 | 全国青少年信息学奥赛 |