华为杯程序设计大赛.pdf

《华为杯程序设计大赛.pdf》由会员分享，可在线阅读，更多相关《华为杯程序设计大赛.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、问题问题 A:A:天梯评分系统天梯评分系统题目描述题目描述在一个下雨的日子，沈学姐和四个好基友约定无事一同打dota（dota 是一个 5 对 5MOBA 类游戏）因为想证明谁最 NB，他们就全部注册新号去爬天梯了。天梯有一套完整的评分系统，它可以根据每位选手每局的数据进行评分，因为 dota 的英雄既有辅助又有 ganker 还有后期，所以不同的英雄的评分标准不一样。可惜那天天梯服务器维护，无法进行评分。于是，他们记录下每一局的数据，找你来帮忙，希望你能够帮他们仿照天梯编一个评分系统，以便于他们比较谁是真正的神牛。已知对于每个账号每个英雄的初始积分都是 1200 分，并且该账号的天梯积分是所

2、有使用过的英雄的积分的加权平均数（按次数加权，最终用整除）。每局一个英雄的数据包括主数据（杀敌/死亡/助攻）和附数据（破塔/正补/反补），你会得到所出现的英雄的主数据评分标准。此外还会根据附数据评出 MVP，英魂，富豪，破军，偏将，补王的称号，每个称号都有一个得分。而每局英雄的最终得分是由胜负、初始积分、主数据得分和附数据得分决定的。主数据得分：每个英雄都有对应的 x,y,z 三个评分参数。主数据得分是：杀敌数*x+死亡数*y+助攻数*z胜负得分：胜利不影响正常的分，失败方额外扣去 200 分；附数据得分：MVP：胜利方主数据得分最高者获得 MVP，额外得到 20 分；英魂：失败方主数据得分最

3、高者获得英魂，免去失败扣分；以下称号仅胜利方获得：富豪：每个正补得到40 金钱，每个杀敌得到250 金钱，每次死亡失去 100 金钱，每次破塔得到 450 金钱，每局游戏获得金钱最多者获得富豪，额外得到10 分；破军：破塔最多者获得破军，额外得到 10 分；偏将：助攻最多者获得偏将，额外得到 10 分；补王：反补最多者获得补王，额外得到 10 分；最终得分=初始积分+主数据得分+附数据的分+胜负得分；输入输入第一行为一个整数 T,代表有 T 组数据。对于每组数据：第一行一个整数 n(n=15)，代表所要用到的 n 个英雄主数据评分标准；第 2 到 n+1 行，第 i 行三个整数x,y,z（0

4、x,z=10,-10=y0,x+z=10），代表编号为 i-1 的英雄的评分参数。第 n+2 行一个整数 m(m=5)，代表玩的局数，n+3 行到第 n+m*6+3 行每 6 行为一组，共 m 组代表 m 局游戏，每组第一到第五行代表每局游戏第一个人到第五人的数据，每一行7 个正整数，h 代表此局该人使用的英雄编号，a,b,c,d,e,f（a,b,c=20,d=11,e,f=100），代表杀敌/死亡/助攻/破塔/正补/反补，第六行一个数，0 代表失败，1 代表胜利。输出输出对于第 i 组数据先输出一行“Case#i:”(不含引号)接下来输出五行，每行一个数，第 i 行为第 i 个人的最终天梯积

5、分。样例输入样例输入41样例输出样例输出Case#1:2401240提示提示问题问题 B:B:三体问题三体问题题目描述题目描述沈学姐是一个科幻小说爱好者，最近她读了三体，喜欢数学的学姐对三体问题产生了兴趣。当然，学姐并不想去算某颗行星的轨道。她把整个三体星系简化为一个平面，三颗恒星的球心投影成平面上的三点，每颗恒星都有一个半径为 r 的圆形引力场(r 由恒星自身属性决定)。学姐想知道，三颗恒星的引力场总面积是多少。输入输入第一行为一个整数 T，表示数据组数。每组数据有三行输入：每行有三个数 x,y,r（保留两位小数），分别为该恒星中心坐标(x,y)和引力场半径 r。(|x|=5,|y|=5,0

6、=r=5)输出输出对于第 i 组数据，输出一行，形如“Case#i:ans”（不含引号）其中，ans 表示引力场总面积，保留整数部分(因为学姐不想太难)。样例输入样例输入.样例输出样例输出Case#1:9Case#2:79问题问题 C:C:男票管理系统男票管理系统题目描述题目描述“学姐，你有多少男票啊”学妹好奇地问。“不知道啊，太多了”，沈学姐无奈地说，“不过我有一个男票管理系统，我给你权限去登录看看。作为交换，你得帮我维护啊。”学妹登录之后，发现学姐有n 个男票(n=1000)。每个男票在学姐心中都有一个好感度 x(1=x=100000)，任意两个男票的好感度都不同。所谓维护任务呢，就是把所

7、有男票按好感度从高到低排序。由于这个系统直接套用了大一同学写的模板，一次只能交换相邻两个男票的信息。学妹表示很无语，她想请你帮忙算一下完成维护任务一共需要交换多少次。输入输入第一行一个整数 T，表示有 T 组数据。对于每组数据，共两行：第一行为一个整数 n，表示男票数量。第二行为 n 个整数，表示每个男票的好感度。输出输出对每组数据输出一行，形如”Case#i:ans”(不含引号)i 表示数据组数，ans 表示所需交换次数。样例输入样例输入34125样例输出样例输出Case#1:0Case#2:6问题问题 D:D:男票的名字男票的名字题目描述题目描述学妹知道了学姐的男票信息后，又好奇地问：“学

8、姐，那你又拒绝过多少可爱的男孩子啊”“还是不知道啊，太多了”，沈学姐无奈地说，“但是那些被我拒绝的人，都有一个特点，他们的名字我不喜欢。反正我也给你我的男票管理系统权限了，自己看吧。”而你作为一个爱慕学姐的男/女孩子，通过学妹搞到了那份学姐讨厌的人的名单，你想根据这份名单给自己取个新名字，新的名字应该是你的名字里尽可能短的子串（连续），同时不是学姐讨厌的人的名字的子串。输入输入第一行一个整数 T（1=T=42），表示有 T 组数据。对于每组数据：第一行一个整数 n（2=N=50000），表示有 n 个名字接 下 来n行，每 行 一 个 非 空 字 符 串Si（N=S1+S2+.+SN=2500

9、00），该字符串仅由小写字母组成。第一个字符串表示你的名字，后面 n-1 个字符串表示学姐讨厌的人的名字。输出输出对每组数据输出一行，形如”Case#i:ans”(不含引号)i 表示数据组数，ans 表示答案字符串或者“Impossible”。样例输入样例输入22cdcdcd3aaaaaa样例输出样例输出Case#1:cdcCase#2:Impossible问题问题 E:E:学姐招亲学姐招亲题目描述题目描述号外号外！美丽的沈学姐要以抛绣球的方式招亲了！假设从 0 时刻，沈学姐会陆续抛一些绣球，一个人可以左右移动来接住绣球（绣球实在平面内动），移动速度是 1。现在你已知会有 N 个绣球被沈学姐在

10、时刻抛在。如果你要接住所有绣球，只靠你一个人是不可能的，于是你决定去雇佣一些人帮你接绣球，好让你抱得学姐归。因为雇佣别人是要收费的，所以需要尽可能少地雇佣别人。输入输入第一行为一个整数 T,代表有 T 组数据。对于每组数据：第一行包含一个正整数 N（1N100000）。接下来 N 行，每行两个整数 Si 和 Ti（0Si,Ti109）。输出输出对于第 i 组数据，输出一行，形如“Case#i:ans”（不含引号）ans 为接住绣球所需要的最少人数（包括你自己）。样例输入样例输入1111样例输出样例输出Case#1:1问题问题 F:F:学姐护卫队学姐护卫队题目描述题目描述沈学姐想要出去逛街，有怕

11、自己的美貌引来好色之徒的窥探，就召集自己 N 个男票，要他们跟随保护。但当他们按沈学姐给的编号排好队后，学姐又发现，如果相邻两个人身高相差大于 H，就会显得很不整齐。因此，学姐想要去掉一部分人，使得队伍显得整齐。什么，你问学姐为什么不直接按身高排她当然是希望她越喜欢的人越靠近她啦，所以虽然麻烦了一点，她的男票们也当然是选择原谅她啊。同时，为了享受左拥右抱的感觉，沈学姐至少会带两个人。问沈学姐在满足上述条件下有多少种带队方案呢输入输入第一行一个数 T（T10），表示数据组数。对于每组数据：第一行一个整数 N（N100000）和 H（1H109），含义如题所述。接下来 N 行，每行一个整数 hi（

12、1hi109），表示学姐的男票的身高。输出输出对于第 i 组数据，输出一行，形如“Case#i:ans”（不含引号）ans 为沈学姐最能带出门的男票队列的方案数，学姐考虑到你可能不会处理大数据，ans 只需要是真正方案数模 9901 的结果就好了。样例输入样例输入1421375样例输出样例输出Case#1:4问题问题 G:G:礼物分配礼物分配题目描述题目描述沈学姐送给她的男票们一些礼物。现在有 n 个男票，收到了 m 件礼物，他们要分配这些礼物。沈学姐的男票们是民主的，他们依次按 1-N 编号。然后 1 号男票提出个礼物分配案。剩下的(包括 1 号男票本身)对这个案进投票，如果持提案的数超过一

13、半，那么这个案被通过，家按数目分礼物；如果不通过，则沈学姐会和1 号男票分手。剩下的男票编号都减，数减，再次分礼物。假设男票们都是绝对理性的，是旗相当的对。个男票会反对投票，当且仅当他知道当前这个被否决了以后，他定不会被分手，并且获得至少和当前提案相当的礼物。现在，请你回答第个男票最多能提案分配给多少礼物不被分手。如果论如何都会被分手，输出-1。输入输入第一行一个整数 T，表示有 T 组数据。接下来 T 行：每行为两个整数 n，m，表示男票人数和礼物数量。(n=2000,m=2000)输出输出对每组数据输出一行，形如”Case#i:ans”(不含引号)ans 如题面描述样例输入样例输入135样

14、例输出样例输出Case#1:5问题问题 H:H:学姐的树学姐的树题目描述题目描述春天来了，沈学姐特别想在课上睡觉。今天是概率论，老师讲了期望的概念，学姐觉得太水就睡着了。在梦里，学姐看见了许多树：主席树，替罪羊树，仙人掌树.学姐只记得那些都是二叉树，现在沈学姐想知道有 N 个节点的二叉树的期望深度是多少（假设根节点深度为 1），你能帮帮学姐吗输入输入输入数据有多行，每行为一组。每行为一个正整数 N(N=60)，表示二叉树的节点个数。输出输出对于每组数据，输出一行形如”Case#i:ans”(不含引号)i 表示数据组数，ans 表示期望深度（保留两位小数）。样例输入样例输入23样例输出样例输出C

15、ase#1:#2:问题问题 I:I:谁是卧底谁是卧底题目描述题目描述沈学姐和她的男朋友去丽江旅游，在酒吧里，他们玩起了“谁是卧底”。几轮下来，学姐了解了一些信息，她想知道通过这些信息能否推断出每一个人的所属阵营。注：“谁是卧底”中共有 3 个阵营：村民，白板，卧底。分别用 1，2，3 表示。输入输入第一行一个整数 T，表示有 T 组数据。对于每组数据：第一行为两个 整数 n，m，表示游 戏人数和 信息条数。(n=2000,m=10000)接下来 m 行每行三个整数 k，x，y。(k=1 或 2)k=1 时表示标号 x 的人和标号 y 的人是同一阵营。K=2 时表示标号 x 的人属于 y 阵营。

16、(1=y=3)数据保证不会有人同时属于多个阵营。输出输出对每组数据输出一行，形如”Case#i:*”(不含引号)其中，能推断出每一个人的所属阵营时*是 YES，否则*是 NO样例输入样例输入1223样例输出样例输出Case#1:NOCase#2:YES问题问题 J:J:去吧贝塔去吧贝塔题目描述题目描述沈学姐作为计算机科学与工程界的 dalao，受 AlphaGo 的刺激，决定自己做个机器人，命名为“去吧贝塔”。为了让机器人能够对外界信息作出反应，首先就是要能够识别图像。沈学姐就拿了包含数字的 01 矩阵来训练“去吧贝塔”。学姐想让你帮忙检测一下她的数据有没有问题。输入输入第一行一个数 T（T1

17、5），表示数据组数。对于每组数据：第一行一个整数 N（N15），表示矩阵大小。接下来 N 行，每行 N 个数（是 0 或 1），表示图像矩阵。输出输出对于第 i 组数据，输出一行，形如“Case#i:ans”（不含引号）ans 为矩阵中 1 组成的数字。数据保证这个数字符合大多人的书写习惯且一个矩阵中只有一个数字。样例输入样例输入0样例输出样例输出Case#1:1问题问题 K:K:反立方数反立方数题目描述题目描述立方数是形如 x 的数，如 1，8，27.3定义反立方数为：所有非 1 因子中不含有立方数的数。学姐想知道在区间L,R中，所有反立方数的平方和。由于答案可能很大，输出结果对的取模即可。输入输入第一行一个整数 T，表示有 T 组数据。接下来 T 行：每行为两个整数 L,R。(1=L=R=1018)输出输出对每组数据输出一行，形如”Case#i:ans”(不含引号)ans 为区间L,R中所有反立方数的平方和样例输入样例输入215110样例输出样例输出Case#1:55Case#2:321