2021年安徽省安徽省大学生程序设计竞赛题目.docx

安徽省大学生程序设计竞赛

比

赛

题

目

安徽省高等学校计算机教诲研究会
安徽 合肥
.5.24

A First Blood
Time Limit：3000/1000 MS (Java/Others)
问题描述
盖伦是个小学一年级学生，在一次数学学时候，教师给她们出了一种难题：
教师给了一种正整数 n，需要在不不不大于n范畴内选取三个正整数(可以是相似)，使它们三个最小公倍数尽量大。盖伦很想第一种解决这个问题，你能协助盖伦拿到“first blood”吗？
输入
一方面是一种正整数T，表达有T组测试数据
每组测试数据是一种正整数n(1<=n<=10^6)
输出
对于每组测试数据，输出最大最小公倍数，每个输出单独占一行
样例输入
2
9
7
样例输出
504
210

注意事项
数据范畴超过32位整数，可用long long或__int64表达64位整数

B 求和
Time Limit：3000/1000 MS (Java/Others)
问题描述
对于正整数n,k，咱们定义这样一种函数，它满足如下规律

当前给出n和k，你任务就是要计算值。
输入
一方面是一种整数T，表达有T组数据
接下来每组数据是n和k()
输出
打印出f(n，k)值，每个输出单独占一行
样例输入
3
1 1
2 1
3 1
样例输出
-1
1
-2

C LU困惑
Time Limit：3000/1000MS (Java/Others)
问题描述
Master Lu 非常喜欢数学，当前有个问题：在二维空间上一共有n个点，LU每连接俩个点，就会拟定一条直线，相应有一种斜率。当前LU把平面上所有点中任意两点连接成一条线，并将这条线斜率加入一种集合（若斜率不存在则不计入集合），她想懂得这个集合中有多少元素。
输入
第一行是一种整数T，代表T组测试数据。
每组数据第一行是一种整数n，代表点数量，且2<n<1000。
接下来n行，每行两个整数，0<x<10000，0<y<10000，代表点坐标
输出
输出斜率集合中有多少个元素
样例输入
2
4
1 1
2 2
3 3
3 6
4
1 1
2 2
2 0
3 1
样例输出
3
3

D 锐雯上单不给就送
Time Limit：3000/1000 MS (Java/Others)
问题描述
《英雄联盟》（简称LOL）是由美国Riot Games开发，腾讯游戏运营英雄对战网游。《英雄联盟》除了即时战略、团队作战外，还拥有特色英雄、自动匹配战网平台，涉及天赋树、召唤师系统、符文等元素。简朴来说，LOL是两队对战游戏，一种队伍(5个人)对抗另一种队伍(5个人)，重要目是拆掉对面建筑物，一种每个队伍英雄都扮演着不同角色，分别为“上单”,“打野”,“中单”,“辅助”,“ADC”,普通状况是各自队伍“上单”VS“上单”,“打野”VS“打野”,“中单”VS“中单”,“辅助”VS“辅助”,“ADC”VS“ADC”。上单在LOL中始终是一种很吃香角色，普通小学生进入匹配后来都会强调一句“锐雯上单不给就送”作为联系暗号。zz_1215和devtang经常玩这个游戏，zz_1215是devtang宿敌，devtang很想懂得zz_1215玩什么角色，然后她就选同样角色和zz_1215决斗(solo)。通过观测devtang发现zz_1215选取什么角色是有规律，那就是取决于上一次她玩什么角色。现用一种5*5矩阵来表达，表达上一次如果zz_1215玩是第j个角色，那么她这一次玩第i个角色概率为，此外有。当前懂得zz_1215第一次玩是什么角色，devtang想懂得在第n次游戏中，zz_1215最有也许玩是什么角色。
输入
一方面是一种整数T，表达有T组数据
每组数据涉及
第一行是一种数字n，表达devtang想懂得第n次游戏中zz_1215最也许玩角色，
接下来会给出5*5矩阵表达概率关系.
最后一行给出整数m()表达zz_1215第一次游戏玩角色，角色表达办法见注意事项。
输出
输出第n次游戏中，zz_1215最有也许玩角色，角色表达办法见注意事项，每个输出单独占一行
样例输入
2
1
0 0.1 0.2 0.3 0.4
0.4 0 0.1 0.2 0.3
0.3 0.4 0 0.1 0.2
0.2 0.3 0.4 0 0.1
0.1 0.2 0.3 0.4 0
3
2
0 0.1 0.2 0.3 0.4
0.4 0 0.1 0.2 0.3
0.3 0.4 0 0.1 0.2
0.2 0.3 0.4 0 0.1
0.1 0.2 0.3 0.4 0
3
样例输出
3
4
注意事项
1,2,3,4,5分别代表“上单”，“打野”，“中单”，“辅助”，“ADC”这五个角色，如果存在各种角色概率相似话，那么就选取下标最小那个，例如通过计算1，3概率都是0.5，那么zz_1215会选取1这个角色。

E 瓦莉拉小伙伴(选做)
Time Limit：3/1 Min (Java/Others)
问题描述
《炉石传说》是暴雪公司出品一款卡牌类对战游戏，俗话说暴雪出品必属精品，《炉石传说》集休闲性与竞技性于一体，是科研之余烧脑休闲必备神器。zz_2215是一种土豪玩家，充了诸多钱组了一套刀油贼，这是一套对技术规定很高瞬间爆发斩杀型牌组，但是zz_2215技术实在太菜了，连小学生算术都做不好，并不能在天梯中迅速上分。RudySnow在一旁看不下去了，决定帮zz_2215一把，计算此时zz_2215能否斩杀对方，赢得比赛胜利。

如果你没有玩过《炉石传说》，下面是游戏规则。

1、对战在两个玩家之间展开，每个玩家扮演一种英雄，每个英雄有某些血量，当某个英雄血量降为0或如下时候扮演她玩家就输了，对方玩家获得胜利。
2、玩家之间每回合轮流打出某些牌，每张牌消耗一定法力值，每个英雄每回合总法力值是有限，该回合打出牌法力值总消耗不能超过该回合英雄持有法力值。
3、玩家可以打出牌分为随从和法术牌。
4、随从牌可以在场上打出随从，每个随从拥有袭击力和血量，可以袭击对方随从或英雄。若袭击对方英雄，对方英雄失去相应血量；若袭击对方随从，两随从进行比较，双方随从血量都要减去对方袭击力导致伤害，若随从血量降为0或如下则该随从死亡。例如我方场上有一种4袭击力3血量随从，对方场上有一种3袭击力4血量随从，敌方随从袭击我方随从，双方随从都会死亡。
5、每个随从每回合只能袭击一次，且在普通状况下，当回合上场随从不能展开袭击。但是随从可以有某些属性，此处考虑属性为冲锋和嘲讽。拥有冲锋属性随从上场当回合可以立即展开袭击。当场上具备嘲讽属性随从时，对方英雄和随从袭击时必要先袭击该嘲讽随从，直至该嘲讽随从死亡才干袭击其她随从和英雄。（法术牌不受嘲讽效果影响，如果卡牌效果容许则法术牌可以选取任意目的）
6、法术牌不在场上打出随从，但是拥有各种各样效果，背面会详细解说某些法术牌效果。
7、你控制英雄是潜行者瓦莉拉，她有某些特殊职业专属效果。例如每回合她可以使用2点法力值英雄技能一次（每回合只能使用英雄技能一次），获得一把袭击力为1，耐久度为2匕首，使用这把匕首英雄可以袭击对方随从或英雄，对其导致等同于匕首袭击力伤害；若袭击对象是对方随从，瓦莉拉会受到等同于对方随从袭击力伤害（如果瓦莉拉血量不大于对方随从袭击力瓦莉拉还会死亡）。每回合最多只能使用匕首袭击一次，且袭击一次后匕首耐久度减少1点，若匕首耐久度降为0或如下该匕首会被摧毁。
8、潜行者尚有一种特殊职业特性是连击，若她某张法术牌有连击特性，那么如果你在打出该张卡片前打出过其她卡片，就能触发卡片连击效果。例如某张法术牌效果是“对敌方英雄导致2点伤害；连击：对敌方英雄导致4点伤害”，那么这一回合你只打出这张法术牌，能对敌方英雄导致2点伤害，但是如果你在打出这张法术牌前使用了其她随从或法术牌，然后再打出这张牌，就能对敌方英雄导致4点伤害。连击必要由卡片触发，英雄技能并不能触发连击。

本题中你扮演英雄瓦莉拉，当前是你行动回合，你场上没有随从，也未装备匕首，对方场上也许会有某些随从，这些随从都带有嘲讽属性。题目会给出当前对方英雄血量，以及你英雄血量，可用法力值，手牌中随从和法术牌状况，对方场上随从状况。请你计算在当前回合能否通过使用英雄技能和一套最优出牌顺序，在自己英雄不死亡前提下，将对方英雄血量击杀到0或如下，完毕斩杀。

你也许拥有卡牌为：
1、南海船工：消耗法力值1，袭击力2，血量1，特效：在你正装备一把匕首时获得冲锋，否则不冲锋（你唯一也许拥有随从牌，并且最多也许拥有1张，你别的牌都是法术牌）
2、伺机待发：消耗法力值0，特效：本回合中你施放下一种法术牌法力值消耗减少3点，但不不大于0点
3、致命药膏：消耗法力值1，特效：使你匕首增长2点袭击力（若使用时没有装备匕首则无效果但仍消耗法力值）
4、剑刃乱舞：消耗法力值2，特效：摧毁你匕首，对敌方英雄和所有敌方随从角色导致等同于匕首袭击力伤害（若使用时没有装备匕首则无效果但仍消耗法力值）
5、刺骨：消耗法力值2，特效：对敌方英雄或任意一种敌方随从导致2点伤害；连击：对敌方英雄或任意一种敌方随从导致4点伤害
6、闷棍：消耗法力值2，特效：将一种指定敌方随从闷回对方手牌中。（必要对敌方随从使用，若敌方场上没有随从则无法使用）
7、修补匠磨刀油：消耗法力值4，特效：使你匕首增长3点袭击力（若使用时没有装备匕首则无效果但仍消耗法力值）；连击：使你匕首增长3点袭击力，同步使一种随机我方随从增长3点袭击力（若使用时没有装备匕首则只增长随从袭击力）
输入
一方面是一种正整数T(0<T<=30)
接下来是T组数据
每组数据第一行是两个正整数n1,n2(0<n1,n2<=40)，n1表达敌方英雄剩余血量，n2表达我方英雄剩余血量
下面一行是一种正整数m(0<m<=10)，表达我方英雄该回合可用法力值
下面一行是一种整数t1(0<=t1<=10)，表达该回合我方可用手牌数量
下面一行有t1个正整数，每个正整数表达我方拥有手牌，和题目描述中相应，例如为1 1 2 2，就表达我方当前拥有两张南海船工和两张伺机待发（若t1=0即没有手牌时没有这一行输入）
下面一行是一种整数t2(0<=t2<=7)，表达敌方场上随从数量，若t2等于0则输入结束，若t2>0，下面是t2行，每行有两个整数a,b用来表达一种敌方随从（所有敌方随从默认具备嘲讽属性），a(0<=a<=12)表达该随从袭击力，b(0<b<=12)表达该随从血量
输出
对每组数据表达场面，若通过特定出牌顺序可以完毕斩杀，输出“Bao Qian”，若并不能完毕斩杀，输出“Da De Bu Cuo”，每个输出单独占一行
样例输入
2
1 30
10
10
1 2 2 3 4 5 5 6 7 7
0
30 1
1
1
1
4
3 5
3 5
3 5
3 5
样例输出
Bao Qian
Da De Bu Cuo

F 多重某些和问题
Time Limit：30000/10000MS (Java/Others)
问题描述
有n种不同大小数字ai，每种各mi个。判断与否可以从这些数字之中选出若干使它们和正好为K。
输入
一方面是一种正整数T(1<=T<=100)
接下来是T组数据
每组数据第一行是一种正整数n(1<=n<=100)，表达有n种不同大小数字
第二行是n个不同大小正整数ai (1<=ai<=100000)
第三行是n个正整数mi (1<=mi<=100000)，表达每种数字有mi个
第四行是一种正整数K(1<=K<=100000)
输出
对于每组数据，如果能从这些数字中选出若干使它们和正好为K，则输出“Yes”，否则输出“No”，每个输出单独占一行
样例输入
2
3
3 5 8
3 2 2
17
2
1 2
1 1
4
样例输出
Yes
No

G 你来擒孟获
Time Limit：3000/1000MS (Java/Others)
问题描述
三国时期，南蛮王孟获叛乱，诸葛亮起兵平乱。
当进一步南蛮之地时，遇本地人绘得地图，发现各地分别由各个寨主据守，若诸葛亮想兵分多路进军，尽快占领各个山寨(必要占领所有山寨)，并且最后所有士兵都汇聚到孟获所在山寨，若给你一次穿越机会，你用程序告诉诸葛亮至少需要多少天才干完毕任务。假设军队足够多，各分队行军速度同样，且诸葛亮神机妙算，到达每个山寨即日可以攻克。
输入
一方面是一种正整数T，接下来是T组测试数据，每组数据第一行是两个整数n,m(2=<n<=1000,1=<m<=10000)，表达山寨数量和山寨间道路数量，山寨编号0，1，2，3….n-1
接下来m行，每行三个整数i,j,k(0=<i,j<n且k<=10^4)，分别表达山寨i和山寨j之间有一条路，在这条路上需要行军k天，接下来一行两个整数s,t(0<=s,t<=n-1)，分别表达诸葛亮所在部队起点和孟获山寨所在终点编号。
输出
对每组数据输出一种整数，表达诸葛亮士兵占领所有山寨并汇聚到孟获所在山寨所需要至少天数，每个输出独占一行
样例输入
2
5 6
0 1 2
1 2 2
3 1 2
4 0 3
3 2 3
3 4 1
4 3
5 5
1 0 1
1 2 3
1 3 3
4 2 2
3 4 1
4 2
样例输出
7
9
H 数7
Time Limit：3000/1000 MS (Java/Others)
问题描述
数7是一种简朴饭桌游戏，有数人围成一桌，先从任意一人开始数数，1、2、3……那样数下去，逢到7倍数(7、14、21……)和具有7数字(17、27……)必要以敲桌子代替。如果有谁逢7却数出来了，就要接受惩罚。小明觉得这个游戏太简朴了，于是对它做出了改进，那就是每逢到素数时候就以敲桌子代替，并且数数方向发生变化，并且最开始那个人可以从1到中选一种合数，开始数数。假设当前有10个人，第一种人编号为1，她选取4开始数，由于4不是素数，那么就是1说:4，轮到下一种编号为2人来数，由于5是素数，2敲桌子(duang)，由于5是素数，顺序发生变化，当前又轮到1说:6，然后以此类推10敲桌子(duang)，1说:8，2说:9…始终到某人浮现错误为止。小明想懂得轮到自己时候应当干什么，你可以帮小明解决这个问题吗？
输入
一方面是一种整数T，表达有T组数据，接下来每组数据第一行会给出n和m()，分别表达饭桌上有n个人，小明编号是m，第二行会给出a和b()，分别表达从编号为a人开始，并且选取合数b开始数数
输出
输出轮到小明时候她应当干什么，如果是说数字就把该数字输出，如果是敲桌子就输出“duang”，每个输出单独占一行
样例输入
3
10 2
3 4
3 3
2 6
4 1
3 8
样例输出
duang
duang
10
注意事项
如果从第a个人开始，如果没有变化方向，下一种人就是a+1或者1，否则就是a-1或n
I 梯田
Time Limit：3000/1000MS (Java/Others)
问题描述
土豪YZK在一块小岛上有着一大片n*m梯田，每块1*1梯田均有它高度。奴隶们不甘被YZK剥削，她们联合起来决定发动一场海啸淹掉YZK梯田，由于要留一某些给自己吃，因此她们决定至少淹掉p块田地，但是不能超过q块田地，否则会由于剩余田地不够而把奴隶自己饿死。当前给你一种n*m矩阵，矩阵中元素代表梯田中每块田地高度，求能否发动一场高度为h海啸，满足奴隶们规定。由于发动海啸代价很高，因此如果存在各种解，请输出最小一种h，否则输出-1。当梯田高度及其周边8方向梯田高度均不大于等于海啸高度h时，以为梯田被淹。
输入
第一行是一种正整数T，代表数据组数
对于每组数据，第一行为四个整数n，m，p，q
之后是一种n*m矩阵，矩阵中每个数代表每块梯田高度
1<=T<=100
1<=n,m<=100
1<=p<=q<=n*m
1<=梯田高度<=1000000
输出
对于每组数据，如果能找到h，请输出最小h，否则输出-1
每组输出占一行
样例输入
2
3 3 3 6
1 2 3
4 5 6
7 8 9
4 4 5 6
1 2 2 1
2 1 1 2
2 1 1 2
1 2 2 1
样例输出
3
-1

J 镜像树
Time Limit：3000/1000MS (Java/Others)
问题描述
一棵二叉树，若其与自己镜像完全相似，就称其为镜像树（即这棵二叉树关于根完全对称）。例如

是一棵镜像树；
而

不是镜像树。
现给你一棵二叉树，请你判断其是不是镜像树。
输入
第一行是一种整数数T，表达测试数据有T组
每组数据第一行是一种正整数n(1<=n<=100)，表达二叉树中节点数量
下面n行，每行有三个正整数a b c(1<=a<=100,0<=b,c<=100)，表达以编号a节点为父节点，它左孩子节点编号为b，右孩子节点编号为c，若b=0表达没有左孩子节点，c=0表达没有右孩子节点，树根节点是编号为1节点，节点编号都>=1（保证数据中给出二叉树拓扑构造是合法）
下面一行是n个正整数vi(1<=vi<=100)，表达编号为i节点值。
输出
若数据中表达二叉树是镜像树，输出“Yes”，否则输出“No”，每个输出单独占一行
样例输入
2
7
1 2 3
2 4 5
3 6 7
4 0 0
5 0 0
6 0 0
7 0 0
1 2 2 3 4 4 3
5
1 2 3
2 0 4
3 0 5
4 0 0
5 0 0
1 2 2 3 3
样例输出
Yes
No