第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx
- 文档编号:6253161
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:13
- 大小:103.59KB
第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx
《第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx》由会员分享,可在线阅读,更多相关《第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx(13页珍藏版)》请在冰点文库上搜索。
第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题
2016年第2届湖南涉外经济学院程序设计竞赛决赛试题
策划:
李桥、邹竞
选题、改编:
邹竞
竞赛系统环境安装:
罗明亮、邹竞、李桥
本次比赛共8道题,编号为A~H,所有题目均采用标准输入输出,请不要读写任何文件。
所有题目的正确输出均是惟一的,你的输出只有和正确输出完全一致时才能通过。
竞赛时间:
5小时。
题目范例(本题目不要求选手求解,只是给第一次参加比赛并首次使用自动评判系统的同学给出一个在输入输出上可供参考的样例)
范例1:
黑社会的打手(难度★)
这年头连黑社会都看重知识了,所以不好好读书是不行的。
刘宇同学就因为数学很好,被黑社会老大黄涛看重,充当军师。
一次,黑社会想招聘一个最能打架的打手,原想让众多应聘者两两之间捉对单挑PK晋级再两两单挑PK……直到决出最后的冠军,没想到因为经济不景气,找不到工作的人越来越多,来黑社会应聘打手的人数远远超过了预期的想象,可黑社会也因为经济不景气,只能招一个打手(打手也是要领工资的)。
如果PK场次太多,影响太大,就会惊动警察。
于是,刘宇军师对黄涛老大说:
“老大,现在打架不流行单挑了,流行群殴,咱们把PK规则改一下,改成三个人同时群殴PK,一场比赛中仅一人晋级,这个人能以一敌二,业务能力更强,如果到最后有必要的话,我们也举行两个人一场的单挑PK,这样能减少比赛场次,而且最后的冠军一定是高手高手高高手!
”黄涛老大说:
“Goodidea!
就照你说的做。
现在已知有n个人来应聘打手了,你帮我计算一下,我们至少需要举办多少场PK?
”如果你是刘宇同学,请帮他计算一下,至少需要多少场PK?
输入
本题目包含多组测试,每组测试占一行,每组测试包含一个整数N,表示最初参加PK的总人数。
当N=0时,表示输入结束,你的程序不应处理这一行。
输出
对每组测试数据,输出一个非负整数,表示产生最后的冠军最少需要多少场PK。
样例输入
样例输出
3
4
25
0
1
2
12
参考程序(以C/C++为例):
#include
usingnamespacestd;
intmain()
{
longlongn;//在VC++6.0中应定义为__int64n;邹竞注
cin>>n;
while(n>0)
{
longlongd,r,sum=0;//在VC++6.0中应定义为__int64d,r,sum=0;邹竞注
while
(1)
{
if(n==1)
{
cout< break; } if(n==2) { sum++; cout< break; } d=n/3; r=n%3; sum+=d; n=d+r; } cin>>n; } return0; } 通过此题了解了输入输出规则之后,比赛正式开始! 目前各位选手的电脑上安装了VisualStudio2013和Eclipse,分别对应C/C++和Java语言,题目一定要使用PC^2系统提交。 请注意,服务器中包含多个大规模测试数据。 使用C/C++语言的选手请注意,在VC++2012及高版本中,scanf和printf函数默认是不安全的,如果一定要使用scanf和printf函数,可选中项目->属性->配置属性->C/C++->预处理器->预处理定义中,加入命令参数_CRT_SECURE_NO_WARNINGS即可。 题目A_求和符号(难度★) 数学上的求和号 可以嵌套使用,例如 现在请你计算 的值。 (简单题) 输入 本题目包含多组测试,每组测试占多行,每组测试第1行包含2个整数n和m,接下来有n+m行,前n行每一行有一个整数,表示每一个ai的值,后m行每一行有一个整数,表示每一个bi的值。 当m=n=0时,表示输入结束,你的程序不应处理这一行。 对于60%的数据,保证1<=n,m<=100,所给出的整数的绝对值<=100,对于所有的数据,保证1<=n,m<=100000,所给出的整数的绝对值<=10000,编程时请选择合适的数据类型防止溢出。 输出 对每组测试数据,输出一行,仅包含一个整数,即你计算得到的答案。 输入保证只有一种理解方式。 样例输入 样例输出 32 1 2 3 5 7 45 10000 10000 10000 10000 10000 10000 10000 10000 5000 00 72 1800000000 题目B_酷酷的单词(难度★) 输入一些仅由小写字母组成的单词。 你的任务是统计有多少个单词是“酷”的,即每种字母出现的次数都不同。 比如ada是酷的,因为a出现2次,d出现1次,而1和2不同。 再比如,banana也是酷的,因为a出现3次,n出现2次,b出现1次。 但是,bbacccd不是酷的,因为a和d出现的次数相同(均为1次)。 (简单题) 输入 本题目包含多组测试(不超过30组数据)。 每组数据第一行为单词个数n(1<=n<=10000)。 以下n行各包含一个单词,字母个数为1~30。 输出 对于每组数据,输出测试点编号和酷单词的个数。 样例输入 样例输出 2 ada bbacccd 2 illness a Case1: 1 Case2: 0 使用C/C++的选手注意,本题中,如果需要在循环入口使用cin读入数据直到读入流的末尾,可以使用类似以下代码: while(cin>>n) { …//对控制台输入的数据进行处理 } 如果需要在循环入口使用scanf函数读入数据,判断是否正确读入一个数据,可以使用类似以下代码: while(scanf("%d",&n)==1) { …//对控制台输入的数据进行处理 } 题目C_残缺的棋盘(难度★) 在国际象棋里,王是最重要的一个棋子。 每一步,王可以往上下左右或者对角线方向移动一步,如图1所示。 图1 给定两个格子A(r1,c1),B(r2,c2),你的任务是计算出一个王从A到B至少需要走多少步。 为了避免题目太简单,我们从棋盘里拿掉了一个格子C(r3,c3)(ABC保证互不相同),要求王从A走到B的过程中不能进入格子C。 在本题中,各行从上到下编号为1~8,各列从左到右编号为1~8。 (简单题) 输入 本题目包含多组测试,不超过10000组数据,每组测试占一行,包含6个整数r1,c1,r2,c2,r3,c3(1<=r1,c1,r2,c2,r3,c3<=8).三个格子A,B,C保证各不相同。 输出 对于每组数据,输出测试点编号和最少步数。 样例输入 样例输出 118756 113322 Case1: 7 Case2: 3 使用C/C++的选手注意,本题中,如果需要在循环入口使用cin读入数据直到输入结束(流的末尾),可以使用类似以下代码: while(cin>>r[0]>>c[0]>>r[1]>>c[1]>>r[2]>>c[2]) { …//对控制台输入的数据进行处理 } 如果需要在循环入口使用scanf函数读入数据直到输入结束,可以使用类似以下代码: while(scanf("%d%d%d%d%d%d",&r[0],&c[0],&r[1],&c[1],&r[2],&c[2])! =EOF) { …//对控制台输入的数据进行处理 } 题目D_关羽闯关(难度★★) 在三国演义中,话说关羽当年一听到他结拜兄弟刘备的下落,就马上放弃了曹操给他的优厚条件,带上刘备的家眷去找刘备。 关羽从许都出发,历经艰辛,最后在古城找到了刘备。 现在你的任务是为关羽设计一条新的路线来寻找他的兄长。 假设关羽知道从许都到古城的所有关口的连通情况,并且知道在每个关口打败守卫并安全离开的概率。 请帮助关羽找一条能成功从许都逃往古城的最大概率的路线。 关羽不能去同一个关口两次。 (考查知识点: 最短路径,贪心) 输入 输入数据的第一行包含了一个整型数T(1<=T<=50)。 T代表输入数据的数量。 对于每组测试数据,第一行只包含一个整数N(3<=N<=1000)。 接下来的N行是一个表示关口之间的连通性的矩阵。 如果第i行第j列的数是1,这意味着从关口i到关口j是连通的。 否则,0表示从关口i到关口j是不连通的。 每组测试数据的最后一行是N-2个用空格分隔开的实数,每个实数表示关羽安全通过该关口的概率P(0<=P<=1)。 输出 对于每组测试数据,你需要输出一行,包含一个实数,表示关羽安全到达古城的最大概率。 这个实数需要精确到小数点后4位。 如果结果小于0.0001,那么输出“Cannotreach! ” 样例输入 样例输出 3 3 010 001 000 0.5 4 0100 0010 0001 0000 0.010.001 6 011000 001100 000110 001011 000001 000000 0.20.10.60.3 0.5000 Cannotreach! 0.1200 注意,假设有实型变量d,在C中输出d并精确到4位小数可使用printf("%.4f",d),在C++中输出d精确到4位小数,除了可以使用兼容的C方法外,还可使用cout.precision(4);cout< 题目E_穿越矩阵(难度★★) 给定一个m*n的数字矩阵,计算从左到右走过该矩阵且经过的方格中整数之和最小的路径。 一条路径可以从第1列的任意位置出发,到达地n列的任意位置。 每一步为从i列走到第i+1列相邻的行(水平移动或者沿两个45°斜线移动),如图1所示。 第一列和最后1行看作是相邻的,即应当把这个矩阵看成是一个卷起来的圆筒。 图1 两个略有不同的5*6的数字矩阵最小路径如图2所示,只有最下面一行的数不同。 右边的矩阵路径利用了第1行与最后1行相邻的性质。 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 8 6 4 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 图2 (考查知识点: 动态规划) 输入 输入包含多个测试用例,表示多个矩阵信息,每个测试用例的第1行为两个数m和n,分别表示矩阵的行数和列数,接下来的第m*n个整数按行优先的顺序排列,即前n个数组成的第1行,接下来的n个数组成第2行,以此类推。 相邻的整数间用一个或者多个空格分隔。 每个矩阵的行数在1到10之间,列数在1到100之间。 当m=n=0时,表示输入结束,你的程序不应处理这一行。 输出 对每一个矩阵的输出两行,第1行为最小整数之和的路径,路径由n个整数组成。 表示经过的行号,如果这样的路径不止一条,输出字典序最小的一条,第2行为对应的最小的整数之和。 样例输入 样例输出 56 341286 618274 593995 841326 372864 56 341286 618274 593995 841326 372123 22 910 910 00 123445 16 121545 11 11 19 题目F_脱离地牢(难度★★★) 年轻的彪彪王子贺一彪与美丽的馨馨公主但惠馨,在一起过着幸福的生活。 他们都随身带有一块带磁性的阴阳魔法石,王海涛教授,也就是传说中喜欢囚虐少女的大魔王涛大屌,想得到这两块魔法石,来吸收其精华大增自己的魔力。 于是有一天涛大屌抓住了二人,把他们带到地牢,分别困在了不同的地方。 然后涛大屌念起了咒语,准备炼狱。 彪彪王子想起了父王曾经留给他的备忘本,他告诉彪彪只要把两块魔法石合在一起,念出咒语,就能打败涛大屌,脱离地牢,而且本子上还附下了地牢的地图,彪彪从中了解到了馨馨公主的位置所在,于是他决定首先要找到馨馨,但是他发现这个地牢很奇怪,它会增强二人魔法石所带磁力的大小,而且会改变磁力的方向。 比如,每当彪彪向南走一步,馨馨有可能会被石头吸引向北走一步。 而地狱布满了岩石与熔浆,彪彪必须十分小心,不仅他不能走到岩石或熔浆上,而且由于他行走一步,馨馨的位置也会改变,如果馨馨碰到岩石上,那么她将停留在原地,但如果馨馨移动到了熔浆上,那么她就挂了。 彪彪需要找出了一条最快的行走方案与馨馨相聚。 (考查知识点: 广度优先搜索,分支限界) 输入 输入包含多个测试案例。 每个测试案例输入数据第一行为两个整数n,m(3<=n,m<=20),表示地牢的大小,n行m列。 接下来n行,每行m个字符,描述了地牢的地图,"."代表通路,"#"代表岩石,"! "代表熔浆。 输入保证地牢是封闭的,即四周均是均是岩石或熔浆。 接下来一行有四个字符"N"(北),"S"(南),"W"(西),"E"(东)的排列,表示彪彪王子分别向NSWE四个方向走时馨馨公主受磁石磁力影响的移动方向。 当n=m=0时,表示输入结束,你的程序不应处理这一行。 输出 对于每个测试案例,输出一行,如果彪彪王子能找到馨馨公主,打败涛大屌,则输出一整数,为彪彪王子最少需要行走的步数;如果彪彪在255步之后仍找不到馨馨,则输出“Impossible”。 注意相遇是指彪彪与馨馨最终到达同一个格子,或者二人在相邻两格移动后碰到了一起,而后者的步数算他们移动后的步数。 样例输入 样例输出 55 ##### #H..# #.! .# #.#P# ##### WNSE 34 #### #PH# #### ESNW 00 5 1 题目G_积木游戏(难度★★★) 从n块长度各不相同的积木找出k快积木,使他们的长度和为s,一共有多少种不同的方案? (考查知识点: 递归、回溯、散列) 输入 输入包含多个测试案例。 每个测试案例占两行,第一行为3个正整数n、k、s,表示有n块积木,要求选出k块,使其长度和为s,第二行为n个互不相同的正整数,为积木的高度数组。 积木的长度为不超过106的正整数,输入满足0 当n=k=s=0时,表示输入结束,你的程序不应处理这一行。 输出 对于每个测试案例,输出一行,包含一个正整数,表示不同的方案总数,当不存在方案时,输出0。 样例输入 样例输出 324 123 10570 11121314151617181920 000 1 7 仔细看题,注意降低时间复杂度。 题目H_刘婷的数字游戏(难度★★) 亲爱的选手们,很吃惊吧,这道预选赛出现的题目,决赛怎么又出现了? ! 可是,谁规定了决赛就不能出现跟预选赛一样的题目呀? 此题原本不难,初赛的时候,此题竟然无人做出,很意外。 可能限于时间紧迫来不及细想,一些原本能做出这道题的选手没有时间做这道题。 大家都认为决赛不可能出现和预选赛相同的题目,相信大多数选手初赛后也没有认真思考这道原本不难的题目应该怎么做。 但如果是态度认真,只为学习不为功利的选手,初赛后一定还会继续思考这道题该怎么做。 其实离开了紧张的比赛环境,这道题很容易就会想出解法。 所以,我让这道题在决赛的时候再度出现,作为对初赛后认真思考了这道题的选手的一个意外奖励! ——邹竞 刘婷是个喜欢数字的小姑娘,一日,她实在无聊,在纸上随意写了一个自然数n1,又在这个自然数n1的左侧添加了一个不超过n1的一半的数n2,并列举了n2的所有可能,接着又在n2的左侧添加了一个不超过n2的一半的数n3,并列举了n3的所有可能……反复如此。 后来刘婷自己也被搞晕了,不知道自己写出了多少个数字。 事实上这个问题归结如下: 给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1)n∈set(n); (2)在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3)按此规则进行处理,直到不能再添加自然数为止。 例如,set(6)={6,16,26,126,36,136}。 半数集set(6)中有6个元素。 请你编程帮刘婷计算,对于给定的自然数n,编程计算半数集set(n)中的元素个数。 输入 本题目包含多组测试,每组测试占一行,每组测试包含一个整数N(0 当N=0时,表示输入结束,你的程序不应处理这一行。 输出 对每组测试数据,输出一个非负整数,每行给出半数集set(n)中的元素个数。 样例输入 样例输出 6 99 0 6 9042
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 湖南 涉外经济 学院 程序设计 竞赛 校内 选拔赛 决赛 试题
![提示](https://static.bingdoc.com/images/bang_tan.gif)