《2023年第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx》由会员分享，可在线阅读，更多相关《2023年第2届湖南涉外经济学院程序设计竞赛校内选拔赛决赛试题.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2023年第2届湖南涉外经济学院程序设计竞赛决赛试题策划：李桥、邹竞选题、改编：邹竞竞赛系统环境安装：罗光明、邹竞、李桥本次竞赛共8道题，编号为AH,全部题目均采纳标准输入输出，请不要读写任何文件。 全部题目的正确输出均是惟一的，你的输出只有和正确输出完全一样时才能通过。竞赛时间: 5小时。题目F_脱离地牢（难度）年轻的彪彪王子贺一彪与漂亮的馨馨公主但惠馨，在一起过着华蜜的生活。他们都随身 带有一块带磁性的阴阳魔法石，王海涛教授，也就是传闻中喜爱囚虐少女的大魔王涛大席, 想得到这两块魔法石，来汲取其精华大增自己的魔力。于是有一天涛大席抓住了二人，把他 们带到地牢，分别困在了不同的地方。然后涛大
2、席念起了咒语，打算炼狱。彪彪王子想起了 父王曾经留给他的备忘本，他告知彪彪只要把两块魔法石合在一起，念出咒语，就能战胜涛 大席，脱离地牢，而且本子上还附下了地牢的地图，彪彪从中了解到了馨馨公主的位置所在， 于是他确定首先要找到馨馨，但是他发觉这个地牢很惊奇，它会增加二人魔法石所带磁力的 大小，而且会变更磁力的方向。比如，每当彪彪向南走一步，馨馨有可能会被石头吸引向北 走一步。而地狱布满了岩石与熔浆，彪彪必需非常当心，不仅他不能走到岩石或熔浆上，而 且由于他行走一步，馨馨的位置也会变更，假如馨馨遇到岩石上，那么她将停留在原地，但 假如馨馨移动到了熔浆上,那么她就挂了。彪彪须要找出了一条最快的行走
3、方案与馨馨相聚。（考查学问点：广度优先搜寻，分支限界）输入输入包含多个测试案例。每个测试案例输入数据第一行为两个整数n,m（3=n,m=20）, 表示地牢的大小，n行m歹U。接下来n行，每行m个字符，描述了地牢的地图，心代表通 路，“#”代表岩石，”!”代表熔浆。输入保证地牢是封闭的，即四周均是均是岩石或熔浆。接 下来一行有四个字符“N“（北），（南），（西），（东）的排列，表示彪彪王子分 别向NSWE四个方向走时馨馨公主受磁石磁力影响的移动方向。当n=m=O时，表示输入结 束，你的程序不应处理这一行。输出对于每个测试案例，输出一行，假如彪彪王子能找到馨馨公主，战胜涛大席，则输出一 整数，为彪
4、彪王子最少须要行走的步数；假如彪彪在255步之后仍找不到馨馨，则输出 “Impossible”。留意相遇是指彪彪与馨馨最终到达同一个格子，或者二人在相邻两格移动后 遇到了一起，而后者的步数算他们移动后的步数。样例输出样例输入#H.#.!.#.#P# WNSE 34 #PH# ESNW 00题目G积木嬉戏（难度）从n块长度各不相同的积木找出k快积木，使他们的长度和为s, 一共有多少种不同的 方案？（考查学问点：递归、回溯、散列）输入输入包含多个测试案例。每个测试案例占两行，第一行为3个正整数n、k、s,表示有 n块积木，要求选出k块，使其长度和为s,其次行为n个互不相同的正整数，为积木的高 度数
5、组。积木的长度为不超过的正整数，输入满意0k=n=106, sl（）9,对于40%的数 据,有 l=k=6, nk=108,对于其余 60%的数据，有 2v=kv=3, nk=1012o 当 n=k=s=0 时, 表示输入结束，你的程序不应处理这一行。输出对于每个测试案例，输出一行，包含一个正整数，表示不同的方案总数，当不存在方案 时，输出0。样例输出样例输入324123 10 5 7011 12 13 14 15 16 17 18 19 20000细致看题，留意降低时间困难度。题目H_刘婷的数字嬉戏(难度)敬爱的选手们,很惊讶吧,这道预选赛出现的题目,决赛怎么又出现了? !可是,谁规定了决赛
6、就不能出现跟预选赛一样的题目呀?此题原本不难,初赛的时候，此题竟然无人做出,很意外。可能限于时间紧迫来不及 细想,一些原本能做出这道题的选手没有时间做这道题。大家都认为决赛不行能出现和预选赛相同的题目,信任大多数选手初赛后也没有细致 思索这道原本不难的题目应当怎么做。但假如是看法细致,只为学习不为功利的选手,初 赛后肯定还会接着思索这道题该怎么做。其实离开了惊慌的竞赛环境,这道题很简洁就会 想出解法。所以,我让这道题在决赛的时候再度出现,作为对初赛后细致思索了这道题的选手的 一个意外嘉奖!邹竞刘婷是个喜爱数字的小姑娘，一日，她实在无聊，在纸上随意写了一个自然数nl,又 在这个自然数nl的左侧添
7、加了一个不超过nl的一半的数n2,并列举了 n2的全部可能，接 着又在n2的左侧添加了一个不超过n2的一半的数n3,并列举了 n3的全部可能反复如 此。后来刘婷自己也被搞晕了，不知道自己写出了多少个数字。事实上这个问题归结如下：给定一个自然数n,由n起先可以依次产生半数集set(n)中的数如下。(1) neset(n)；(2)在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3)按此规则进行处理，直到不能再添加自然数为止。例如，set(6)=6,16,26,126,36,136。半数集 set(6)中有 6 个元素。请你编程帮刘婷计算，对于给定的自然数n,编程计算半数集set(
8、n)中的元素个数。输入本题目包含多组测试，每组测试占一行，每组测试包含一个整数N(0N1000),表示自 然数N。当N=0时，表示输入结束，你的程序不应处理这一行。输出对每组测试数据，输出一个非负整数，每行给出半数集set(n)中的元素个数。样例输入样例输出699 069042题目范例（本题目不要求选手求解，只是给第一次参与竞赛 并首次运用自动评判系统的同学给出一个在输入输出上可 供参考的样例）范例1:黑社会的打手（难度）这年头连黑社会都看重学问了，所以不好好读书是不行的。刘宇同学就因为数学很好， 被黑社会老大黄涛看重，充当军师。一次，黑社会想聘请一个最能打架的打手，原想让众多 应聘者两两之间
9、捉对单挑PK晋级再两两单挑PK直到决出最终的冠军，没想到因为经 济不景气，找不到工作的人越来越多，来黑社会应聘打手的人数远远超过了预期的想象，可 黑社会也因为经济不景气，只能招一个打手（打手也是要领工资的）。假如PK场次太多， 影响太大，就会惊动警察。于是，刘宇军师对黄涛老大说：“老大，现在打架不流行单挑了， 流行群殴，咱们把PK规则改一下，改成三个人同时群殴PK, 一场竞赛中仅一人晋级，这 个人能以一敌二，业务实力更强，假如到最终有必要的话，我们也实行两个人一场的单挑 PK,这样能削减竞赛场次，而且最终的冠军肯定是高手高手高高手!”黄涛老大说:“Good idea! 就照你说的做。现在已知有
10、n个人来应聘打手了，你帮我计算一下，我们至少须要举办多少 场PK?”假如你是刘宇同学，请帮他计算一下，至少须要多少场PK?输入本题目包含多组测试，每组测试占一行，每组测试包含一个整数N,表示最初参与PK 的总人数。当N=0时，表示输入结束，你的程序不应处理这一行。输出对每组测试数据，输出一个非负整数，表示产生最终的冠军最少须要多少场PK。样例输入样例输出342501212参考程序(以C/C+为例)：#include using namespace std;int main()long long n; 在VC+6.0中应定义为 _int64 n;邹竞注 cin n;while(n 0)(long
11、 long d, r, sum = 0; 在 VC+6.0 中应定义为int64 d, r, sum = 0;邹竞注 while(l)if(n = 1)cout sum ”n； break;)if(n 二二 2)(sum+;cout sum n； break;)d = n / 3;r = n % 3;sum += d;n = d + r;)cin n;)return 0;)通过此题了解了输入输出规则之后，竞赛正式起先！目前各位选手的电脑上安装了 Visual Studio 2023和Eclipse,分别对应C/C+和Java语言，题目肯定要运用PC八2系统提 交。请留意，服务器中包含多个大规模
12、测试数据。运用C/C+语言的选手请留意，在VC+ 2023及高版本中，scanf和printf函数默认是 担心全的，假如肯定要运用scanf和printf函数，可选中项目.属性，配置属性C/C+ 预处理器，预处理定义中，力口入吩咐参数_CRT_SECURE_NO_WARNINGS即可。题目A_求和符号（难度）数学上的求和号z可以嵌套运用，例如44EZa jbj a、b + /4 + 马4 + a、b、+ a2b、+ % 4 + a2b + a2b、 7=1 J=1+ a3bl + a3b2 + a3b3 + a、b+ aA bx + ab2 + a4b+ a4b/现在请你计算的值。（简洁题）输
13、入本题目包含多组测试，每组测试占多行，每组测试第1行包含2个整数n和m,接下来 有n+m行，前n行每一行有一个整数，表示每一个笺的值，后m行每一行有一个整数，表 示每一个氏的值。当m=n=O时，表示输入结束，你的程序不应处理这一行。对于60%的数 据，保证l=n,m=100,所给出的整数的肯定值二100,对于全部的数据，保证 l=n,m=100000,所给出的整数的肯定值=10000,编程时请选择合适的数据类型防止溢出。输出对每组测试数据，输出一行，仅包含一个整数，即你计算得到的答案。输入保证只有一 种理解方式。样例输入样例输出321235745100001000010000100001000
14、0100001000010000 500000721800000000题目B_酷酷的单词（难度）输入一些仅由小写字母组成的单词。你的任务是统计有多少个单词是“酷”的， 即每种字母出现的次数都不同。比如ada是酷的，因为a出现2次，d出现1次，而 1和2不同。再比如，banana也是酷的，因为a出现3次，n出现2次，b出现1次。 但是，bbacccd不是酷的，因为a和d出现的次数相同（均为1次）。（简洁题）输入本题目包含多组测试（不超过30组数据）。每组数据第一行为单词个数n （l=n=10000）o以下n行各包含一个单词，字母个数为1-30。输出对于每组数据，输出测试点编号和酷单词的个数。样例
15、输入样例输出2 ada bbacccd2 illnessaCase 1: 1Case 2: 0运用C/C+的选手留意,本题中，假如须要在循环入口运用cin读入数据直到读入流的末尾， 可以运用类似以下代码：while（cinn）（对限制台输入的数据进行处理）假如须要在循环入口运用scanf函数读入数据，推断是否正确读入一个数据，可以运用类似 以下代码：while（scanf（H%dM, &n） = 1）（对限制台输入的数据进行处理）题目c_残缺的棋盘(难度)在国际象棋里，王是最重要的一个棋子。每一步，王可以往上下左右或者对角 线方向移动一步，如图1所示。abcdefgh 图1给定两个格子A(rl
16、,cl), B(r2,c2),你的任务是计算出一个王从A到B至少须要 走多少步。为了避开题目太简洁，我们从棋盘里拿掉了一个格子C(r3,c3) (ABC保 证互不相同)，要求王从A走到B的过程中不能进入格子C。在本题中，各行从上 到下编号为卜8,各列从左到右编号为18。(简洁题)输入本题目包含多组测试，不超过10000组数据，每组测试占一行，包含6个整数rl, cl, r2, c2, r3, c3 (l=rl, cl, r2, c2, r3, c3=8).三个格子 A, B, C 保证各不相同。输出对于每组数据，输出测试点编号和最少步数。样例输入样例输出1 1 8 7 5 6113322Cas
17、e 1: 7Case 2: 3运用C/C+的选手留意，本题中，假如须要在循环入口运用cin读入数据直到输入结束(流 的末尾)，可以运用类似以下代码：while(cinr0c 0Jr 1 c 1 r2c2)(对限制台输入的数据进行处理)假如须要在循环入口运用scanf函数读入数据直到输入结束，可以运用类似以下代码：while(scanf(H%d%d%d%d%d%dH, &r0, &c0, &rl, &cl, &r2, &c2) !=EOF)对限制台输入的数据进行处理 )题目D_关羽闯关(难度)在三国演义中，话说关羽当年一听到他结拜兄弟刘备的下落，就立刻放弃了曹操给他的 优厚条件，带上刘备的家眷去
18、找刘备。关羽从许都动身，历经艰辛，最终在古城找到了刘备。 现在你的任务是为关羽设计一条新的路途来找寻他的兄长。假设关羽知道从许都到古城的全 部关口的连通状况，并且知道在每个关口战胜保卫并平安离开的概率。请帮助关羽找一条能 胜利从许都逃往古城的最也许率的路途。关羽不能去同一个关口两次。(考查学问点：最短 路径，贪心)输入输入数据的第一行包含了一个整型数T(1 v=Tv=50)。T代表输入数据的数量。对于每组测试数据，第一行只包含一个整数N(3=N= 1000)。接下来的N行是一个 表示关口之间的连通性的矩阵。假如第i行第j列的数是1,这意味着从关口 i到关口 j是连 通的。否则，0表示从关口 i
19、到关口 j是不连通的。每组测试数据的最终一行是N-2个用空 格分隔开的实数，每个实数表示关羽平安通过该关口的概率P(0=P=l)o输出对于每组测试数据，你须要输出一行，包含一个实数，表示关羽平安到达古城的最也许 率。这个实数须要精确到小数点后4位。假如结果小于0.0001,那么输出“Cannot reach!”样例输出样例输入0.5000Cannot reach!0.120000 10000.540 10000 1 0000 100000.01 0.00160 1 1 000001100000 1 1 00010110000010000000.2 0.1 0.6 0.3留意，假设有实型变量d,
20、在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所示，只有最下面一行的数不
21、同。右边 的矩阵路径利用了第1行与最终1行相邻的性质。412866X827459X995841、一f、6372865 9 3 9 9 5（考查学问点：动态规划）输入输入包含多个测试用例，表示多个矩阵信息，每个测试用例的第1行为两个数m和n,分别 表示矩阵的行数和列数，接下来的第m*n个整数按行优先的依次排列，即前n个数组成的 第1行，接下来的n个数组成第2行，以此类推。相邻的整数间用一个或者多个空格分隔。 每个矩阵的行数在1到10之间，列数在1到100之间。当m=n=0时，表示输入结束，你的 程序不应处理这一行。输出对每一个矩阵的输出两行，第1行为最小整数之和的路径，路径由n个整数组成。表示经过 的行号，假如这样的路径不止一条，输出字典序最小的一条，第2行为对应的最小的整数之 和。样例输入样例输出56341286 618274 593995 841326372864 56341286 618274 593995 841326372123 229 109 100012344516121545111 119