首页 > ACM题库 > HDU-杭电 > hdu 2536 Winner and loser待解决[解题报告]C++
2014
02-10

hdu 2536 Winner and loser待解决[解题报告]C++

Winner and loser

问题描述 :

棒球是美国的国球,是一项集力量、智慧于一体的运动。在棒球比赛中,两只球队轮流进攻,防守的一方有9名球员,其中负责向击球员投球的人称为投手,而进攻方的球员轮流试图用球棒将投手投出的球击打出去,并且争取跑垒得分。双方各进攻一次的过程叫一局,一方进攻一次叫做一个半局。一场棒球比赛通常进行9局,如果9局之后双方得分相同,就进入1局定胜负的延长赛,直到分出胜负为止。先进攻的一方是这场比赛的客队。如果第9局的上半局结束以后,客队仍然落后,则比赛胜负已定,不进行第9局的下半局比赛。比赛中可以替换球员,不过和足球类似,被替换下场的球员将不可以再上场。
在棒球运动中,投手通常是一个队最重要的球员。一名投手的好坏可以直接决定一场比赛的胜负,因此,对每一场棒球比赛,需要各找出一名胜利投手和一名败战投手。确定胜败投的规则如下:

(1)  如果先发投手(每队的第一名投手)投完5局或以上,而且在被替补时得分领先,替补后直至比赛结束为止一直保持领先(不曾被追平或者落后过),球队因而胜利时,记这名先发投手为胜利投手。
(2)  先发投手不管投多少局,只要在被替补时比分落后,而且之后本队到终场(2)  先发投手不管投多少局,只要在被替补时比分落后,而且之后本队到终场为止都从未把比分扳平或领先,球队因而失利时,记这名先发投手为败战投手。
(3)  投完整场比赛(没有被替补)的投手如果球队获胜,就是胜利投手;如果失利,就是败战投手。
(4)  在比赛的任何时刻,只要比分相等,就相当于重新争夺胜负,前面已经被换下的投手就不可能是胜利投手或者败战投手。
(5)  如果一名替补投手在场上的任何时刻,本队比分落后或打平,而他退场时比分领先并且一直保持到终场(或投完比赛剩下的局数没有退场,而终场时比分领先),记这名替补投手为胜利投手。
(6)  如果一名替补投手在场上的任何时刻,本队比分打平或领先,而他退场时比分落后并且一直保持到终场(或投完比赛剩下的局数没有退场,而终场时比分落后),记这名替补投手为败战投手。
(7)  如果先发投手没有投完5局,而在被替补时得分领先,并且一直保持到终场,则胜利投手属于“最起作用”的替补投手,即第一个上场的替补投手。

在本题中,投手必须在本队防守的半局刚开始的时候被换下。

如果对这些规则不是很清楚,请参见下面的样例和样例解释。

输入:

输入包含多组数据。每组数据第一行是一个整数N(9<=N<=20),表示这场比赛的局数。N=0表示输入结束。随后有两行,每行包含N个整数。第一行的第i个数表示第i局客队的得分(不超过20),第二行对应表示主队的得分。如果这个半局没有进行,用’X’表示。接下来的一行有两个整数A和B(1<=A,B<=10),分别表示客队和主队上场的投手人数。然后是A行,每行有一个字符串和一个整数,分别表示依上场顺序给出的客队的投手名字(由字母组成,保证没有空格,不超过20个字符),以及他被替换下场时的局数(局数从1算起)。如果他没有被替换下场,则用’E’表示。最后是B行,表示客队的投手信息。
输入保证是符合题目要求的。

输出:

输入包含多组数据。每组数据第一行是一个整数N(9<=N<=20),表示这场比赛的局数。N=0表示输入结束。随后有两行,每行包含N个整数。第一行的第i个数表示第i局客队的得分(不超过20),第二行对应表示主队的得分。如果这个半局没有进行,用’X’表示。接下来的一行有两个整数A和B(1<=A,B<=10),分别表示客队和主队上场的投手人数。然后是A行,每行有一个字符串和一个整数,分别表示依上场顺序给出的客队的投手名字(由字母组成,保证没有空格,不超过20个字符),以及他被替换下场时的局数(局数从1算起)。如果他没有被替换下场,则用’E’表示。最后是B行,表示客队的投手信息。
输入保证是符合题目要求的。

样例输入:

9
2 0 0 0 0 1 1 0 0
0 2 0 0 1 0 0 2 X
3 2
Peavy 6
Owings 7
Rivera E
Santana 6
Wang E
9
2 0 0 0 0 1 1 0 0
0 2 0 0 1 0 0 0 0
3 2
Peavy 6
Owings 7
Rivera E
Santana 6
Wang E
0

样例输出:

Win: Wang
Lose: Rivera
Win: Owings
Lose: Wang

第一组样例解释:
主队5-4击败客队,因此胜利投手从主队中产生。Santana是该队的先发投手,刚好投完了5局,而且退场的时候球队3-2领先。
不过后来球队比分被扳平(然后又被反超),因此Santana不是胜利投手。而Wang则符合胜利投手的条件:他上场时候第6局马上就丢了一分,
球队这时和对方3-3打平。
而他投完了剩余比赛,最终球队也获胜。因此胜利投手是Wang。
败战投手从客队中产生。Peavy是先发,
他投完的时候是3-3打平,不符合败战投手的条件。而Owings只上来投了一局,投完的时候球队4-3领先,也不符合败战投手的条件。
最后上场的Rivera也只投了1局丢了2分,正是这2分使球队输球。易验证Rivera符合败战投手的条件。
Owings被换下时,比分情况为:
2 0 0 0 0 1 1
0 2 0 0 1 0
客队4-3领先


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  5. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?