首页 > ACM题库 > HDU-杭电 > HDU 3969-Crazy Basketball Fan-模拟-[解题报告]HOJ
2015
04-14

HDU 3969-Crazy Basketball Fan-模拟-[解题报告]HOJ

Crazy Basketball Fan

问题描述 :

Alex is a big fan of basketball and he enjoys watching NBA matches. But as he always has classes in the morning when the game is on, he has to read literal living broadcast with his cellphone instead of TV live. The living broadcast gives messages about who scores or who gets the rebound, etc. After watching a few games with his cellphone, Alex finds a problem. After each game, he wants to know the status of the players (score, rebound…) but the system always fails to give. So Alex decides to calculate himself. Can you help him? If one of your teammates is a crazy basketball fan, you should make him solve this problem because he will find it interesting while working on this problem.
Angry Birds Again

输入:

The first line of input contains an integer t (t<=10) indicate the number of cases.

In each case, the first line contains the names of the two teams in the form of "A vs B", where A stands for the name of home team and B stands for the name of away team. The following 12 lines contain the name of the players play for the home team and another 12 lines contain the name of the players play for the away team. The first five players of each team will be the starters meaning they are on court when the game starts. All the names only contain letters from ‘a’ to ‘z’ and ‘A’ to ‘Z’ and ”’ without space and the length of each name is no more than 20. All the players’ names in one case will be different.

Then a line contains an integer n (2<=n<=500) indicates the number of the messages given by the broadcast.

The next n lines contain the messages, one message per line. The first line will always contain "Begin" and the last line will always contain "End". The game won’t end during a shot or free throw, but may end at any other time. A message in other lines may be one of the following (x, x1 and x2 stand for players from the teams, m and M stand for numbers):

Jump Ball x1 vs x2: this message will only be given on the second line right after "Begin". This means two players from different teams are jumping for the ball. This message will always be followed by "x Hold Ball" and x could be anyone.

x Hold Ball: this message will be given if the ball is currently in no one’s hand, which means: after jump ball or after a shot was made (including the last free throw) or after a shot was blocked or after timeout.

x1 Pass to x2: this means the ball is passed from x1 to x2. x1 is deferent from x2 and they are from the same team.

Layup/Slam Dunk/Hook Shot/Jump Shot/3pt Shot: the first four messages stand for an attempt for 2-point shot while the last message stand for an attempt for 3-point shot. These messages will only be given when someone is currently holding the ball. These messages may be followed by "Made"/"Missed"/"Blocked by x"/"x Foul".

Made/Missed: If a shot was made and scored, "Made" will be given, otherwise "Missed". These two messages will be given right after a shot was attempted if the shot was not fouled or blocked. If the shot was fouled, these two messages will still be given right after "x Foul" to indicate whether the shot was made even with the foul. But if a shot was blocked, these messages will not be given since the shot is definitely missed.

x Rebound: If a shot was missed, this message will be given to indicate who get the rebound (could be anyone from both teams). If someone gets the rebound, he holds the ball.

Blocked by x: If a shot is blocked, this message will be given right after the message which indicates the shot. This message will always be followed by "x Hold Ball" and x could be anyone. A shot will only be blocked by a player from the opposite team with the shooter.

x Foul: this message will be given when a player commit a foul to another player from the opposite team. There are two kind of foul. If this message is given right after the shot attempt, then this foul will lead to free throws. Otherwise this message will be followed by "x Hold Ball".

Free Throw m of M: If a shot is fouled, the shooter will make free throws. If the fouled shot is made, then the shooter will only make one free throw. If it’s missed and it’s a 2-point shot, the shooter will make two free throws. If it’s missed and it’s a 3-point shot, the shooter will make three free throws. Each made free throw earns one point. In this message, m indicates the number of this free throw (start from 1) and M indicates the number of total free throws this player is going to attempt. Both m and M will be no bigger than 3 and m is no bigger than M. After each free throw there will be a message says "Made" or "Missed" to indicate whether the free throw is made or missed. If the last free throw is missed, just like normal shot, someone will get the rebound and if it’s made, a player from the opposite team will hold the ball. No block could be made during the free throws.

x Steal: If a player is now holding the ball, a player from the opposite team could steal the ball away. If someone steals the ball, he will hold it.

x1 Substitution replaced by x2: this message means x1 is off court and replaced by x2. x1 and x2 are from the same team. This could only happen during timeout or before free throw or after a foul which doesn’t lead to free throw. The player who is going to make a free throw won’t be replaced. Before free throw means before any "Free Throw m of M" despite of m and M.

Timeout: timeout could be called when someone is holding the ball. During timeout, substitution could be made. Timeout is ended with the message "x Hold Ball".

It is guaranteed that all the messages are valid and follow the rules. The names of the players will not be the same with words like "rebound" and "block", etc. Actually all the names will be familiar to you if you watch NBA a lot.

输出:

The first line of input contains an integer t (t<=10) indicate the number of cases.

In each case, the first line contains the names of the two teams in the form of "A vs B", where A stands for the name of home team and B stands for the name of away team. The following 12 lines contain the name of the players play for the home team and another 12 lines contain the name of the players play for the away team. The first five players of each team will be the starters meaning they are on court when the game starts. All the names only contain letters from ‘a’ to ‘z’ and ‘A’ to ‘Z’ and ”’ without space and the length of each name is no more than 20. All the players’ names in one case will be different.

Then a line contains an integer n (2<=n<=500) indicates the number of the messages given by the broadcast.

The next n lines contain the messages, one message per line. The first line will always contain "Begin" and the last line will always contain "End". The game won’t end during a shot or free throw, but may end at any other time. A message in other lines may be one of the following (x, x1 and x2 stand for players from the teams, m and M stand for numbers):

Jump Ball x1 vs x2: this message will only be given on the second line right after "Begin". This means two players from different teams are jumping for the ball. This message will always be followed by "x Hold Ball" and x could be anyone.

x Hold Ball: this message will be given if the ball is currently in no one’s hand, which means: after jump ball or after a shot was made (including the last free throw) or after a shot was blocked or after timeout.

x1 Pass to x2: this means the ball is passed from x1 to x2. x1 is deferent from x2 and they are from the same team.

Layup/Slam Dunk/Hook Shot/Jump Shot/3pt Shot: the first four messages stand for an attempt for 2-point shot while the last message stand for an attempt for 3-point shot. These messages will only be given when someone is currently holding the ball. These messages may be followed by "Made"/"Missed"/"Blocked by x"/"x Foul".

Made/Missed: If a shot was made and scored, "Made" will be given, otherwise "Missed". These two messages will be given right after a shot was attempted if the shot was not fouled or blocked. If the shot was fouled, these two messages will still be given right after "x Foul" to indicate whether the shot was made even with the foul. But if a shot was blocked, these messages will not be given since the shot is definitely missed.

x Rebound: If a shot was missed, this message will be given to indicate who get the rebound (could be anyone from both teams). If someone gets the rebound, he holds the ball.

Blocked by x: If a shot is blocked, this message will be given right after the message which indicates the shot. This message will always be followed by "x Hold Ball" and x could be anyone. A shot will only be blocked by a player from the opposite team with the shooter.

x Foul: this message will be given when a player commit a foul to another player from the opposite team. There are two kind of foul. If this message is given right after the shot attempt, then this foul will lead to free throws. Otherwise this message will be followed by "x Hold Ball".

Free Throw m of M: If a shot is fouled, the shooter will make free throws. If the fouled shot is made, then the shooter will only make one free throw. If it’s missed and it’s a 2-point shot, the shooter will make two free throws. If it’s missed and it’s a 3-point shot, the shooter will make three free throws. Each made free throw earns one point. In this message, m indicates the number of this free throw (start from 1) and M indicates the number of total free throws this player is going to attempt. Both m and M will be no bigger than 3 and m is no bigger than M. After each free throw there will be a message says "Made" or "Missed" to indicate whether the free throw is made or missed. If the last free throw is missed, just like normal shot, someone will get the rebound and if it’s made, a player from the opposite team will hold the ball. No block could be made during the free throws.

x Steal: If a player is now holding the ball, a player from the opposite team could steal the ball away. If someone steals the ball, he will hold it.

x1 Substitution replaced by x2: this message means x1 is off court and replaced by x2. x1 and x2 are from the same team. This could only happen during timeout or before free throw or after a foul which doesn’t lead to free throw. The player who is going to make a free throw won’t be replaced. Before free throw means before any "Free Throw m of M" despite of m and M.

Timeout: timeout could be called when someone is holding the ball. During timeout, substitution could be made. Timeout is ended with the message "x Hold Ball".

It is guaranteed that all the messages are valid and follow the rules. The names of the players will not be the same with words like "rebound" and "block", etc. Actually all the names will be familiar to you if you watch NBA a lot.

样例输入:

1
Lakers vs Celtics
DerekFisher
KobeBryant
RonArtest
PauGasol
AndrewBynum
LamarOdom
MattBarnes
SteveBlake
ShannonBrown
LukeWalton
DerrickCaracter
DevinEbanks
RajonRondo
RayAllen
PaulPierce
KevinGarnett
ShaquilleO'Neal
JeffGreen
VonWafer
GlenDavis
JermaineO'Neal
TroyMurphy
NenadKrstic
CarlosArroyo
17
Begin
Jump Ball KevinGarnett vs PauGasol
KobeBryant Hold Ball
KobeBryant Pass to PauGasol
Slam Dunk
Made
RajonRondo Hold Ball
RajonRondo Pass to PaulPierce
Jump Shot
RonArtest Foul
Missed
Free Throw 1 of 2
Made
Free Throw 2 of 2
Missed
PauGasol Rebound
End

样例输出:

Lakers 2-1 Celtics
Lakers
              PLAYER PTS OFF DEF REB AST STL BLK PF FGM-A 3PM-A FTM-A
         DerekFisher   0   0   0   0   0   0   0  0   0-0   0-0   0-0
          KobeBryant   0   0   0   0   1   0   0  0   0-0   0-0   0-0
           RonArtest   0   0   0   0   0   0   0  1   0-0   0-0   0-0
            PauGasol   2   0   1   1   0   0   0  0   1-1   0-0   0-0
         AndrewBynum   0   0   0   0   0   0   0  0   0-0   0-0   0-0
           LamarOdom          DNP - Coach's Decision
          MattBarnes          DNP - Coach's Decision
          SteveBlake          DNP - Coach's Decision
        ShannonBrown          DNP - Coach's Decision
          LukeWalton          DNP - Coach's Decision
     DerrickCaracter          DNP - Coach's Decision
         DevinEbanks          DNP - Coach's Decision
Celtics
              PLAYER PTS OFF DEF REB AST STL BLK PF FGM-A 3PM-A FTM-A
          RajonRondo   0   0   0   0   0   0   0  0   0-0   0-0   0-0
            RayAllen   0   0   0   0   0   0   0  0   0-0   0-0   0-0
          PaulPierce   1   0   0   0   0   0   0  0   0-0   0-0   1-2
        KevinGarnett   0   0   0   0   0   0   0  0   0-0   0-0   0-0
     ShaquilleO'Neal   0   0   0   0   0   0   0  0   0-0   0-0   0-0
           JeffGreen          DNP - Coach's Decision
            VonWafer          DNP - Coach's Decision
           GlenDavis          DNP - Coach's Decision
      JermaineO'Neal          DNP - Coach's Decision
          TroyMurphy          DNP - Coach's Decision
         NenadKrstic          DNP - Coach's Decision
        CarlosArroyo          DNP - Coach's Decision

再没有比这道题更纯的模拟了,只不过超长的描述和超多的细节,使得一般没人会在比赛中做这种题。太浪费时间了。 我是因为只会做这种题才去做这道题的,谁知道就这样调了一下午,在比赛结束前半分钟才A掉。从来没写过这么长的模拟。

这道题主要是就是细节的考虑,而且所有要注意的题目中都说了,没有阴人的地方, 所以题目中提到的一定要注意。

容易出错的地方:

1.比分板上的后三项,由于要求靠右对齐,所以用数字输出的话就比较麻烦,转化成字符串相对方便一点,不过要考虑到10次投篮以上的,还有可能100次以上,不过不知道数据中有没有这种变态数据,但是理论上是能达到这么多的。

2.投篮后被犯规,这一条题目上用很醒目的语句标注了,如果进了,就算一投一中,不进,不算尝试投篮。

3.助攻,我就是WA在这上面了,助攻是接到传球后立刻投篮得分才算助攻,中间如果穿插了其他的动作,比如暂停了,再回来就不算助攻了。

4.注意盖帽后,算被盖者尝试了一次投篮

5.抢断后和得到篮板后,注意持球队员要及时变为该队员,因为随后不会有某某球员 hold ball 语句出现。

6.我记得nba上过场的球员都是排在前面的,但这道题显然不是这样,是按名单输出的,上场了就输出数据,没上过直接输出DNP,注意前5名是肯定上过场得,中间换人时在标记一下。

总之,在做这道题的时候一定要理清思路,想明白所有情况再去敲,现场赛如果碰见这种大模拟,就放一放吧,除非想好了,而且代码功底很强,否则是不值得投资这种题的。

代码如下,写的十分乱,这也说明了当时思路的不清晰。

#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
int main()
{
    int i, j, t, n, k;
    char team1[55], team2[55], tmp[122], tmp1[55][55], tmp2[55][55], fk[9];
    bool chuchang[3][13];
    int score[5], pts[5][55], off[5][55], def[5][55], reb[5][55], ast[5][55], pf[5][55], free[5][55][5], three[5][55][5], faqiu[55][55][5], stl[5][55], block[5][55];
    scanf("%d", &t);
    while(t--)
    {
        memset(chuchang, 0, sizeof(chuchang));
        memset(score, 0, sizeof(score));
        memset(pts, 0, sizeof(pts));
        memset(off, 0, sizeof(off));
        memset(def, 0, sizeof(def));
        memset(reb, 0, sizeof(reb));
        memset(ast, 0, sizeof(ast));
        memset(pf, 0, sizeof(pf));
        memset(free, 0, sizeof(free));
        memset(three, 0, sizeof(three));
        memset(faqiu, 0, sizeof(faqiu));
        memset(stl, 0, sizeof(stl));
        memset(block, 0, sizeof(block));
        map<string, int>teamnum;
        map<string, int>num;
        scanf("%s %s %s", team1, tmp, team2);
        for(i = 1; i <= 12; i++)
        {
            scanf("%s", tmp1[i]);
            string tmpname = tmp1[i];
            teamnum[tmpname] = 1;
            num[tmpname] = i;
        }
        for(i = 1; i <= 12; i++)
        {
            scanf("%s", tmp2[i]);
            string tmpname = tmp2[i];
            teamnum[tmpname] = 2;
            num[tmpname] = i;
        }
        scanf("%d", &n);
        string pre = "", now = "";
        bool ispass = 0,  twoout = 0, threeout = 0, fa = 0, fangui = 0;
        getchar();
        for(k = 0; k < n; k++)
        {
            gets(tmp);
            if(k == 0 || k == n - 1) continue;
            string str = tmp;
            if(str.find("Hold Ball") != -1)
            {
                int len = str.length() - 10;
                string tt = str.substr(0, len);
                now = tt;
                fangui = false;
            }
            else if(str.find("Pass to") != -1)
            {
                string tt = "";
                int len = str.length();
                for(i = 0; i < len; i++)
                {
                    if(str[i] == ' ') break;
                    else tt += str[i];
                }
                pre = tt;
                ispass = true;
                now = str.substr(pre.length() + 9);
            }
            else if(str.find("Layup") != -1 || str.find("Slam Dunk") != -1 || str.find("Hook Shot") != -1  || str.find("Jump Shot") != -1 )
            twoout = true;
            else if(str.find("3pt Shot") != -1)
            threeout = true;
            else if(str.find("Missed") != -1)
            {
                if(fa == true)
                {
                    faqiu[teamnum[now]][num[now]][2]++;
                    fa = false;
                }
                else if(twoout == true)
                {
                    if(!fangui) free[teamnum[now]][num[now]][2]++;
                    else fangui = false;
                    twoout = false;
                }
                else if(threeout == true)
                {
                    if(!fangui)
                    {
                        free[teamnum[now]][num[now]][2]++;
                        three[teamnum[now]][num[now]][2]++;
                    }
                    else fangui = false;
                    threeout = false;
                }
                ispass = false;
            }
            else if(str.find("Made") != -1)
            {
                if(fa == true)
                {
                    pts[teamnum[now]][num[now]]++;
                    score[teamnum[now]]++;
                    faqiu[teamnum[now]][num[now]][2]++;
                    faqiu[teamnum[now]][num[now]][1]++;
                    fa = false;
                }
                else if(twoout)
                {
                    pts[teamnum[now]][num[now]] += 2;
                    score[teamnum[now]] += 2;
                    free[teamnum[now]][num[now]][1]++;
                    free[teamnum[now]][num[now]][2]++;
                    if(ispass)
                    {
                        ast[teamnum[now]][num[pre]]++;
                        ispass = false;
                    }
                    twoout = false;
                }
                else if(threeout)
                {
                    pts[teamnum[now]][num[now]] += 3;
                    score[teamnum[now]] += 3;
                    free[teamnum[now]][num[now]][1]++;
                    free[teamnum[now]][num[now]][2]++;
                    three[teamnum[now]][num[now]][2]++;
                    three[teamnum[now]][num[now]][1]++;
                    if(ispass)
                    {
                        ast[teamnum[now]][num[pre]]++;
                        ispass = false;
                    }
                    threeout = false;
                }
                ispass = false;
            }
            else if(str.find("Rebound") != -1)
            {
                string tt = "";
                int len = str.length();
                for(i = 0; i < len; i++)
                {
                    if(str[i] == ' ') break;
                    else tt += str[i];
                }
                if(teamnum[tt] != teamnum[now])
                {
                    def[teamnum[tt]][num[tt]]++;
                    reb[teamnum[tt]][num[tt]]++;
                }
                else if(teamnum[tt] == teamnum[now])
                {
                    off[teamnum[tt]][num[tt]]++;
                    reb[teamnum[tt]][num[tt]]++;
                }
                now = tt;
                ispass = false;
                twoout = false;
                threeout = false;
            }
            else if(str.find("Blocked") != -1)
            {
                if(threeout)
                {
                    free[teamnum[now]][num[now]][2]++;
                    three[teamnum[now]][num[now]][2]++;
                    threeout = false;
                }
                else if(twoout)
                {
                    free[teamnum[now]][num[now]][2]++;
                    twoout = false;
                }
                string tt = str.substr(11);
                block[teamnum[tt]][num[tt]]++;
                ispass = false;
                twoout = false;
                threeout = false;
            }
            else if(str.find("Foul") != -1)
            {
                string tt = "";
                int len = str.length();
                for(i = 0; i < len; i++)
                {
                    if(str[i] == ' ') break;
                    else tt += str[i];
                }
                pf[teamnum[tt]][num[tt]]++;
                if(twoout || threeout)
                    fangui = true;
            }
            else if(str.find("Free Throw") != -1)
            {
                fa = true;
                ispass = false;
            }
            else if(str.find("Substitution") != -1)
            {
                int len = str.find("Substitution") + 25;
                string tt = str.substr(len);
                chuchang[teamnum[tt]][num[tt]] = 1;
                ispass = false;
                twoout = false;
                threeout = false;
            }
            else if(str.find("Timeout") != -1)
            ispass = false;
            else if(str.find("Jump Ball") != -1)
            ispass = false;
            else if(str.find("Steal") != -1)
            {
                string tt = "";
                int len = str.length();
                for(i = 0; i < len; i++)
                {
                    if(str[i] == ' ') break;
                    else tt += str[i];
                }
                stl[teamnum[tt]][num[tt]]++;
                now = tt;
                ispass = false;
            }
        }
        printf("%s %d-%d %s\n", team1, score[1], score[2], team2);
        printf("%s\n", team1);
        puts("              PLAYER PTS OFF DEF REB AST STL BLK PF FGM-A 3PM-A FTM-A");
        for(i = 1; i <= 12; i++)
        {
            if(i <= 5 || chuchang[1][i] == 1)
            {
                printf("%20s%4d%4d%4d%4d%4d%4d%4d%3d", tmp1[i], pts[1][i], off[1][i], def[1][i], reb[1][i], ast[1][i], stl[1][i], block[1][i], pf[1][i]);
                sprintf(fk, "%d-%d", free[1][i][1], free[1][i][2]);
                printf("%6s", fk);
                sprintf(fk, "%d-%d", three[1][i][1], three[1][i][2]);
                printf("%6s", fk);
                sprintf(fk, "%d-%d", faqiu[1][i][1], faqiu[1][i][2]);
                printf("%6s\n", fk);
            }
            else
            {
                printf("%20s", tmp1[i]);
                puts("          DNP - Coach's Decision");
            }
        }
        printf("%s\n", team2);
        puts("              PLAYER PTS OFF DEF REB AST STL BLK PF FGM-A 3PM-A FTM-A");
        for(i = 1; i <= 12; i++)
        {
            if(i <= 5 || chuchang[2][i] == 1)
            {
                printf("%20s%4d%4d%4d%4d%4d%4d%4d%3d", tmp2[i], pts[2][i], off[2][i], def[2][i], reb[2][i], ast[2][i], stl[2][i], block[2][i], pf[2][i]);
                sprintf(fk, "%d-%d", free[2][i][1], free[2][i][2]);
                printf("%6s", fk);
                sprintf(fk, "%d-%d", three[2][i][1], three[2][i][2]);
                printf("%6s", fk);
                sprintf(fk, "%d-%d", faqiu[2][i][1], faqiu[2][i][2]);
                printf("%6s\n", fk);
            }
            else
            {
                printf("%20s", tmp2[i]);
                puts("          DNP - Coach's Decision");
            }
        }
        puts("");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/6716188


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。