华为杯程序设计大赛.doc

问题 A: 天梯评分系统题目描述在一个下雨的日子，沈学姐和四个好基友约定无事一同打dota（dota是一个5对5 MOBA类游戏）因为想证明谁最NB，他们就全部注册新号去爬天梯了。天梯有一套完整的评分系统，它可以根据每位选手每局的数据进行评分，因为dota的英雄既有辅助又有ganker还有后期，所以不同的英雄的评分标准不一样。可惜那天天梯服务器维护，无法进行评分。于是，他们记录下每一局的数据，找你来帮忙，希望你能够帮他们仿照天梯编一个评分系统，以便于他们比较谁是真正的神牛。已知对于每个账号每个英雄的初始积分都是1200分，并且该账号的天梯积分是所有使用过的英雄的积分的加权平均数（按次数加权，最终用整除）。每局一个英雄的数据包括主数据（杀敌/死亡/助攻）和附数据（破塔/正补/反补），你会得到所出现的英雄的主数据评分标准。此外还会根据附数据评出MVP，英魂，富豪，破军，偏将，补王的称号，每个称号都有一个得分。而每局英雄的最终得分是由胜负、初始积分、主数据得分和附数据得分决定的。主数据得分：每个英雄都有对应的x,y,z三个评分参数。主数据得分是：杀敌数*x+死亡数*y+助攻数*z胜负得分：胜利不影响正常的分，失败方额外扣去200分；附数据得分：MVP：胜利方主数据得分最高者获得MVP，额外得到20分；英魂：失败方主数据得分最高者获得英魂，免去失败扣分；以下称号仅胜利方获得：富豪：每个正补得到40金钱，每个杀敌得到250金钱，每次死亡失去100金钱，每次破塔得到450金钱，每局游戏获得金钱最多者获得富豪，额外得到10分；破军：破塔最多者获得破军，额外得到10分；偏将：助攻最多者获得偏将，额外得到10分；补王：反补最多者获得补王，额外得到10分；最终得分=初始积分+主数据得分+附数据的分+胜负得分；输入第一行为一个整数T,代表有T组数据。对于每组数据：第一行一个整数n (n<=15)，代表所要用到的n个英雄主数据评分标准；第2到n+1行，第i行三个整数x,y,z（0<x,z<=10,-10<=y<0,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个人的最终天梯积分。样例输入1 5 8 -8 2 2 -3 8 9 -5 1 5 -5 5 4 -6 6 1 1 9 1 5 4 90 20 2 1 4 9 0 14 10 3 11 4 2 2 58 44 4 6 2 4 1 33 31 5 7 4 6 1 22 24 1 样例输出Case #1: 1294 1272 1311 1240 1240 提示问题 B: 三体问题题目描述沈学姐是一个科幻小说爱好者，最近她读了三体，喜欢数学的学姐对三体问题产生了兴趣。当然，学姐并不想去算某颗行星的轨道。她把整个三体星系简化为一个平面，三颗恒星的球心投影成平面上的三点，每颗恒星都有一个半径为r的圆形引力场(r由恒星自身属性决定)。学姐想知道，三颗恒星的引力场总面积是多少。输入第一行为一个整数T，表示数据组数。每组数据有三行输入：每行有三个数x,y,r（保留两位小数），分别为该恒星中心坐标(x,y)和引力场半径r。(|x|<=5,|y|<=5,0<=r<=5)输出对于第i组数据，输出一行，形如“Case #i: ans”（不含引号）其中，ans表示引力场总面积，保留整数部分(因为学姐不想太难)。样例输入2 0.00 0.00 1.00 0.00 2.00 1.00 2.00 0.00 1.00 0.00 0.00 5.00 1.00 1.00 2.22 2.00 0.00 1.00 样例输出Case #1: 9 Case #2: 79问题 C: 男票管理系统题目描述“学姐，你有多少男票啊？”学妹好奇地问。“不知道啊，太多了”，沈学姐无奈地说，“不过我有一个男票管理系统，我给你权限去登录看看。作为交换，你得帮我维护啊。”学妹登录之后，发现学姐有n个男票(n<=1000)。每个男票在学姐心中都有一个好感度x(1<=x<=100000)，任意两个男票的好感度都不同。所谓维护任务呢，就是把所有男票按好感度从高到低排序。由于这个系统直接套用了大一同学写的模板，一次只能交换相邻两个男票的信息。学妹表示很无语，她想请你帮忙算一下完成维护任务一共需要交换多少次。输入第一行一个整数T，表示有T组数据。对于每组数据，共两行：第一行为一个整数n，表示男票数量。第二行为n个整数，表示每个男票的好感度。输出对每组数据输出一行，形如”Case #i: ans”(不含引号)i表示数据组数，ans表示所需交换次数。样例输入2 5 5 4 3 2 1 5 3 4 1 2 5 样例输出Case #1: 0 Case #2: 6问题 D: 男票的名字题目描述学妹知道了学姐的男票信息后，又好奇地问：“学姐，那你又拒绝过多少可爱的男孩子啊？”“还是不知道啊，太多了”，沈学姐无奈地说，“但是那些被我拒绝的人，都有一个特点，他们的名字我不喜欢。反正我也给你我的男票管理系统权限了，自己看吧。”而你作为一个爱慕学姐的男/女孩子，通过学妹搞到了那份学姐讨厌的人的名单，你想根据这份名单给自己取个新名字，新的名字应该是你的名字里尽可能短的子串（连续），同时不是学姐讨厌的人的名字的子串。输入第一行一个整数T（1=<T<=42），表示有T组数据。对于每组数据：第一行一个整数n（2<=N<=50000），表示有n个名字接下来n行，每行一个非空字符串Si（N<=S1+S2+.+SN<=250000），该字符串仅由小写字母组成。第一个字符串表示你的名字，后面n-1个字符串表示学姐讨厌的人的名字。输出对每组数据输出一行，形如”Case #i: ans”(不含引号)i表示数据组数，ans表示答案字符串或者“Impossible”。样例输入2 2 cdc dcd 3 a aa aaa 样例输出Case #1: cdc Case #2: Impossible 问题 E: 学姐招亲题目描述号外号外！美丽的沈学姐要以抛绣球的方式招亲了！假设从0时刻，沈学姐会陆续抛一些绣球，一个人可以左右移动来接住绣球（绣球实在平面内动），移动速度是1。现在你已知会有N个绣球被沈学姐在时刻抛在。如果你要接住所有绣球，只靠你一个人是不可能的，于是你决定去雇佣一些人帮你接绣球，好让你抱得学姐归。因为雇佣别人是要收费的，所以需要尽可能少地雇佣别人。输入第一行为一个整数T,代表有T组数据。对于每组数据：第一行包含一个正整数N（1N100000）。接下来N行，每行两个整数Si和Ti（0Si,Ti109）。输出对于第i组数据，输出一行，形如“Case #i: ans”（不含引号）ans为接住绣球所需要的最少人数（包括你自己）。样例输入1 1 1 1 样例输出Case #1: 1问题 F: 学姐护卫队题目描述沈学姐想要出去逛街，有怕自己的美貌引来好色之徒的窥探，就召集自己N个男票，要他们跟随保护。但当他们按沈学姐给的编号排好队后，学姐又发现，如果相邻两个人身高相差大于H，就会显得很不整齐。因此，学姐想要去掉一部分人，使得队伍显得整齐。什么，你问学姐为什么不直接按身高排？她当然是希望她越喜欢的人越靠近她啦，所以虽然麻烦了一点，她的男票们也当然是选择原谅她啊。同时，为了享受左拥右抱的感觉，沈学姐至少会带两个人。问沈学姐在满足上述条件下有多少种带队方案呢？输入第一行一个数T（T10），表示数据组数。对于每组数据：第一行一个整数N（N100000）和H（1H109），含义如题所述。接下来N行，每行一个整数hi（1hi109），表示学姐的男票的身高。输出对于第i组数据，输出一行，形如“Case #i: ans”（不含引号）ans为沈学姐最能带出门的男票队列的方案数，学姐考虑到你可能不会处理大数据，ans只需要是真正方案数模9901的结果就好了。样例输入1 4 2 1 3 7 5 样例输出Case #1: 4问题 G: 礼物分配题目描述沈学姐送给她的男票们一些礼物。现在有n个男票，收到了m件礼物，他们要分配这些礼物。沈学姐的男票们是民主的，他们依次按1-N编号。然后1号男票提出个礼物分配案。剩下的(包括1号男票本身)对这个案进投票，如果持提案的数超过一半，那么这个案被通过，家按数目分礼物；如果不通过，则沈学姐会和1号男票分手。剩下的男票编号都减，数减，再次分礼物。假设男票们都是绝对理性的，是旗相当的对。个男票会反对投票，当且仅当他知道当前这个被否决了以后，他定不会被分手，并且获得至少和当前提案相当的礼物。现在，请你回答第个男票最多能提案分配给多少礼物不被分手。如果论如何都会被分手，输出-1。输入第一行一个整数T，表示有T组数据。接下来T行：每行为两个整数n，m，表示男票人数和礼物数量。(n<=2000,m<=2000)输出对每组数据输出一行，形如”Case #i: ans”(不含引号)ans如题面描述样例输入1 3 5 样例输出Case #1: 5问题 H: 学姐的树题目描述春天来了，沈学姐特别想在课上睡觉。今天是概率论，老师讲了期望的概念，学姐觉得太水就睡着了。在梦里，学姐看见了许多树：主席树，替罪羊树，仙人掌树.学姐只记得那些都是二叉树，现在沈学姐想知道有N个节点的二叉树的期望深度是多少（假设根节点深度为1），你能帮帮学姐吗？输入输入数据有多行，每行为一组。每行为一个正整数N(N<=60)，表示二叉树的节点个数。输出对于每组数据，输出一行形如”Case #i: ans”(不含引号)i表示数据组数，ans表示期望深度（保留两位小数）。样例输入2 3 样例输出Case #1: 2.00 Case #2: 2.80问题 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阵营。(1<=y<=3)数据保证不会有人同时属于多个阵营。输出对每组数据输出一行，形如”Case #i: *”(不含引号)其中，能推断出每一个人的所属阵营时*是YES，否则*是NO样例输入2 5 5 1 1 3 1 1 4 1 3 5 1 4 5 2 1 1 5 6 1 1 3 1 1 4 1 3 5 1 4 5 2 1 1 2 2 3 样例输出Case #1: NO Case #2: YES问题 J: 去吧贝塔题目描述沈学姐作为计算机科学与工程界的dalao，受AlphaGo的刺激，决定自己做个机器人，命名为“去吧贝塔”。为了让机器人能够对外界信息作出反应，首先就是要能够识别图像。沈学姐就拿了包含数字的01矩阵来训练“去吧贝塔”。学姐想让你帮忙检测一下她的数据有没有问题。输入第一行一个数T（T15），表示数据组数。对于每组数据：第一行一个整数N（N15），表示矩阵大小。接下来N行，每行N个数（是0或1），表示图像矩阵。输出对于第i组数据，输出一行，形如“Case #i: ans”（不含引号）ans为矩阵中1组成的数字。数据保证这个数字符合大多人的书写习惯且一个矩阵中只有一个数字。样例输入1 5 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 样例输出Case #1: 1问题 K: 反立方数题目描述立方数是形如x3的数，如1，8，27.定义反立方数为：所有非1因子中不含有立方数的数。学姐想知道在区间L,R中，所有反立方数的平方和。由于答案可能很大，输出结果对19260817的取模即可。输入第一行一个整数T，表示有T组数据。接下来T行：每行为两个整数L,R。(1<=L<=R<=1018)输出对每组数据输出一行，形如”Case #i: ans”(不含引号)ans为区间L,R中所有反立方数的平方和样例输入2 1 5 1 10 样例输出Case #1: 55 Case #2: 321