2016年第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx

《2016年第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx》由会员分享，可在线阅读，更多相关《2016年第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2021年第2届湖南涉外经济学院程序设计竞赛决赛试题筹划：李桥、邹竞选题、改编：邹竞竞赛系统环境安装：罗明亮、邹竞、李桥 本次比赛共8道题，编号为AH，所有题目均采用标准输入输出，请不要读写任何文件。 所有题目的正确输出均是惟一的，你的输出只有和正确输出完全一致时才能通过。竞赛时间：5小时。题目范例此题目不要求选手求解，只是给第一次参加比赛并首次使用自动评判系统的同学给出一个在输入输出上可供参考的样例范例1：黑社会的打手难度这年头连黑社会都看重知识了，所以不好好读书是不行的。刘宇同学就因为数学很好，被黑社会老大黄涛看重，充当军师。一次，黑社会想招聘一个最能打架的打手，原想让众多应聘者两两之间捉

2、对单挑PK晋级再两两单挑PK直到决出最后的冠军，没想到因为经济不景气，找不到工作的人越来越多，来黑社会应聘打手的人数远远超过了预期的想象，可黑社会也因为经济不景气，只能招一个打手打手也是要领工资的。如果PK场次太多，影响太大，就会惊动警察。于是，刘宇军师对黄涛老大说：“老大，现在打架不流行单挑了，流行群殴，咱们把PK规那么改一下，改成三个人同时群殴PK，一场比赛中仅一人晋级，这个人能以一敌二，业务能力更强，如果到最后有必要的话，我们也举行两个人一场的单挑PK，这样能减少比赛场次，而且最后的冠军一定是高手高手高高手！黄涛老大说：“Good idea！就照你说的做。现在有n个人来应聘打手了，你帮我

3、计算一下，我们至少需要举办多少场PK？如果你是刘宇同学，请帮他计算一下，至少需要多少场PK？输入此题目包含多组测试，每组测试占一行，每组测试包含一个整数N，表示最初参加PK的总人数。当N=0时，表示输入完毕，你的程序不应处理这一行。输出对每组测试数据，输出一个非负整数，表示产生最后的冠军最少需要多少场PK。样例输入样例输出342501212参考程序以C/C+为例：#include using namespace std;int main()long long n; /在中应定义为 _int64 n; 邹竞注cin n;while(n 0)long long d, r, sum = 0; /在中

4、应定义为 _int64 d, r, sum = 0; 邹竞注while(1)if(n = 1)cout sum n;break;if(n = 2)sum+;cout sum n;return 0;通过此题了解了输入输出规那么之后，比赛正式开场！目前各位选手的电脑上安装了Visual Studio 2021和Eclipse，分别对应C/C+和Java语言，题目一定要使用PC2系统提交。请注意，效劳器中包含多个大规模测试数据。使用C/C+语言的选手请注意，在VC+ 2021及高版本中，scanf和printf函数默认是不平安的，如果一定要使用scanf和printf函数，可选中工程-属性-配置属性

5、-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，编程时请选择适宜的数据类型防止溢出。输

6、出对每组测试数据，输出一行，仅包含一个整数，即你计算得到的答案。输入保证只有一种理解方式。样例输入样例输出3 2123574 5100001000010000100001000010000100001000050000 0721800000000题目B_酷酷的单词难度输入一些仅由小写字母组成的单词。你的任务是统计有多少个单词是“酷的，即每种字母出现的次数都不同。比方ada是酷的，因为a出现2次，d出现1次，而1和2不同。再比方，banana也是酷的，因为a出现3次，n出现2次，b出现1次。但是，bbacccd不是酷的，因为a和d出现的次数一样均为1次。简单题输入此题目包含多组测试不超过30组数

7、据。每组数据第一行为单词个数n (1=nn)/对控制台输入的数据进展处理如果需要在循环入口使用scanf函数读入数据，判断是否正确读入一个数据，可以使用类似以下代码：while(scanf(%d, &n) = 1)/对控制台输入的数据进展处理题目C_残缺的棋盘难度在国际象棋里，王是最重要的一个棋子。每一步，王可以往上下左右或者对角线方向移动一步，如图1所示。图1给定两个格子A(r1,c1), B(r2,c2)，你的任务是计算出一个王从A到B至少需要走多少步。为了防止题目太简单，我们从棋盘里拿掉了一个格子C(r3,c3)ABC保证互不一样，要求王从A走到B的过程中不能进入格子C。在此题中，各行从

8、上到下编号为18，各列从左到右编号为18。简单题输入此题目包含多组测试，不超过10000 组数据，每组测试占一行，包含6个整数r1, c1, r2, c2, r3, c3 (1=r1, c1, r2, c2, r3, c3r0c0r1c1r2c2)/对控制台输入的数据进展处理如果需要在循环入口使用scanf函数读入数据直到输入完毕，可以使用类似以下代码：while(scanf(%d%d%d%d%d%d, &r0, &c0, &r1, &c1, &r2, &c2) !=EOF)/对控制台输入的数据进展处理题目D_关羽闯关难度在三国演义中，话说关羽当年一听到他结拜兄弟刘备的下落，就马上放弃了曹操给

9、他的优厚条件，带上刘备的家眷去找刘备。关羽从许都出发，历经艰辛，最后在古城找到了刘备。现在你的任务是为关羽设计一条新的路线来寻找他的兄长。假设关羽知道从许都到古城的所有关口的连通情况，并且知道在每个关口打败守卫并平安离开的概率。请帮助关羽找一条能成功从许都逃往古城的最大概率的路线。关羽不能去同一个关口两次。考察知识点：最短路径，贪心输入输入数据的第一行包含了一个整型数T(1 = T = 50)。T代表输入数据的数量。对于每组测试数据，第一行只包含一个整数N(3 = N = 1000)。接下来的N行是一个表示关口之间的连通性的矩阵。如果第i行第j列的数是1，这意味着从关口i到关口j是连通的。否那

10、么，0表示从关口i到关口j是不连通的。每组测试数据的最后一行是N-2个用空格分隔开的实数，每个实数表示关羽平安通过该关口的概率P(0 = P = 1)。输出对于每组测试数据，你需要输出一行，包含一个实数，表示关羽平安到达古城的最大概率。这个实数需要准确到小数点后4位。如果结果小于，那么输出“Cannot reach!样例输入样例输出330 1 00 0 10 0 040 1 0 00 0 1 00 0 0 10 0 0 060 1 1 0 0 0 0 0 1 1 0 00 0 0 1 1 00 0 1 0 1 10 0 0 0 0 10 0 0 0 0 0Cannot reach!注意，假设有

11、实型变量d，在C中输出d并准确到4位小数可使用printf(%.4f,d)，在C+中输出d准确到4位小数，除了可以使用兼容的C方法外，还可使用cout.precision(4); cout fixed d;题目E_穿越矩阵难度给定一个m*n的数字矩阵，计算从左到右走过该矩阵且经过的方格中整数之和最小的路径。一条路径可以从第1列的任意位置出发，到达地n列的任意位置。每一步为从i列走到第i+1列相邻的行水平移动或者沿两个45斜线移动，如图1所示。第一列和最后1行看作是相邻的，即应当把这个矩阵看成是一个卷起来的圆筒。图1两个略有不同的5*6的数字矩阵最小路径如图2所示，只有最下面一行的数不同。右边的

12、矩阵路径利用了第1行及最后1行相邻的性质。341286618274593995841326372864341286618274593995841326372123图2考察知识点：动态规划输入输入包含多个测试用例，表示多个矩阵信息，每个测试用例的第1行为两个数m和n，分别表示矩阵的行数和列数，接下来的第m*n个整数按行优先的顺序排列，即前n个数组成的第1行，接下来的n个数组成第2行，以此类推。相邻的整数间用一个或者多个空格分隔。每个矩阵的行数在1到10之间，列数在1到100之间。当m=n=0时，表示输入完毕，你的程序不应处理这一行。输出对每一个矩阵的输出两行，第1行为最小整数之和的路径，路径由n

13、个整数组成。表示经过的行号，如果这样的路径不止一条，输出字典序最小的一条，第2行为对应的最小的整数之和。样例输入样例输出5 63 4 1 2 8 66 1 8 2 7 45 9 3 9 9 58 4 1 3 2 63 7 2 8 6 45 63 4 1 2 8 66 1 8 2 7 45 9 3 9 9 58 4 1 3 2 63 7 2 1 2 32 29 109 100 01 2 3 4 4 5161 2 1 5 4 5111 119题目F_脱离地牢难度年轻的彪彪王子贺一彪及美丽的馨馨公主但惠馨，在一起过着幸福的生活。他们都随身带有一块带磁性的阴阳魔法石，王海涛教授，也就是传说中喜欢囚虐少

14、女的大魔王涛大屌，想得到这两块魔法石，来吸收其精华大增自己的魔力。于是有一天涛大屌抓住了二人，把他们带到地牢，分别困在了不同的地方。然后涛大屌念起了咒语，准备炼狱。彪彪王子想起了父王曾经留给他的备忘本，他告诉彪彪只要把两块魔法石合在一起，念出咒语，就能打败涛大屌，脱离地牢，而且本子上还附下了地牢的地图，彪彪从中了解到了馨馨公主的位置所在，于是他决定首先要找到馨馨，但是他发现这个地牢很奇怪，它会增强二人魔法石所带磁力的大小，而且会改变磁力的方向。比方，每当彪彪向南走一步，馨馨有可能会被石头吸引向北走一步。而地狱布满了岩石及熔浆，彪彪必须十分小心，不仅他不能走到岩石或熔浆上，而且由于他行走一步，馨

15、馨的位置也会改变，如果馨馨碰到岩石上，那么她将停留在原地，但如果馨馨移动到了熔浆上，那么她就挂了。彪彪需要找出了一条最快的行走方案及馨馨相聚。考察知识点：广度优先搜索，分支限界输入输入包含多个测试案例。每个测试案例输入数据第一行为两个整数n,m3=n,m=20，表示地牢的大小，n行m列。接下来n行，每行m个字符，描述了地牢的地图，.代表通路，#代表岩石，!代表熔浆。输入保证地牢是封闭的，即四周均是均是岩石或熔浆。接下来一行有四个字符N北，S南，W西，E东的排列，表示彪彪王子分别向NSWE四个方向走时馨馨公主受磁石磁力影响的移动方向。当n=m=0时，表示输入完毕，你的程序不应处理这一行。输出对于

16、每个测试案例，输出一行，如果彪彪王子能找到馨馨公主，打败涛大屌，那么输出一整数，为彪彪王子最少需要行走的步数；如果彪彪在255步之后仍找不到馨馨，那么输出“Impossible。注意相遇是指彪彪及馨馨最终到达同一个格子，或者二人在相邻两格移动后碰到了一起，而后者的步数算他们移动后的步数。样例输入样例输出5 5#H.#.!.#.#P#WNSE3 4#PH#ESNW0 051 题目G_积木游戏难度从n块长度各不一样的积木找出k快积木，使他们的长度和为s，一共有多少种不同的方案？考察知识点：递归、回溯、散列输入输入包含多个测试案例。每个测试案例占两行，第一行为3个正整数n、k、s，表示有n块积木，要

17、求选出k块，使其长度和为s，第二行为n个互不一样的正整数，为积木的高度数组。积木的长度为不超过106的正整数，输入满足0k=n=106，s109，对于40%的数据，有1=k=6，nk=108，对于其余60%的数据，有2=k=3，nk=1012。当n=k=s=0时，表示输入完毕，你的程序不应处理这一行。输出对于每个测试案例，输出一行，包含一个正整数，表示不同的方案总数，当不存在方案时，输出0。样例输入样例输出3 2 41 2 310 5 7011 12 13 14 15 16 17 18 19 200 0 017 仔细看题，注意降低时间复杂度。题目H_刘婷的数字游戏难度亲爱的选手们，很吃惊吧，这

18、道预选赛出现的题目，决赛怎么又出现了？！可是，谁规定了决赛就不能出现跟预选赛一样的题目呀？此题原本不难，初赛的时候，此题竟然无人做出，很意外。可能限于时间紧迫来不及细想，一些原本能做出这道题的选手没有时间做这道题。大家都认为决赛不可能出现和预选赛一样的题目，相信大多数选手初赛后也没有认真思考这道原本不难的题目应该怎么做。但如果是态度认真，只为学习不为功利的选手，初赛后一定还会继续思考这道题该怎么做。其实离开了紧张的比赛环境，这道题很容易就会想出解法。所以，我让这道题在决赛的时候再度出现，作为对初赛后认真思考了这道题的选手的一个意外奖励！邹竞刘婷是个喜欢数字的小姑娘，一日，她实在无聊，在纸上随意

19、写了一个自然数n1，又在这个自然数n1的左侧添加了一个不超过n1的一半的数n2，并列举了n2的所有可能，接着又在n2的左侧添加了一个不超过n2的一半的数n3，并列举了n3的所有可能反复如此。后来刘婷自己也被搞晕了，不知道自己写出了多少个数字。事实上这个问题归结如下：给定一个自然数n，由n开场可以依次产生半数集set(n)中的数如下。(1) nset(n)；(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3) 按此规那么进展处理，直到不能再添加自然数为止。例如，set(6)=6,16,26,126,36,136。半数集set(6)中有6个元素。请你编程帮刘婷计算，对于给定的自然数n，编程计算半数集set(n)中的元素个数。输入此题目包含多组测试，每组测试占一行，每组测试包含一个整数N(0N1000)，表示自然数N。当N=0时，表示输入完毕，你的程序不应处理这一行。输出对每组测试数据，输出一个非负整数，每行给出半数集set(n)中的元素个数。样例输入样例输出699069042