首页 > ACM题库 > HDU-杭电 > HDU 3719-Snooker Referee-二叉树-[解题报告]HOJ
2015
02-21

HDU 3719-Snooker Referee-二叉树-[解题报告]HOJ

Snooker Referee

问题描述 :

Snooker is a cue sport that is played on a large baize-covered table with pockets in each of the four corners and in the middle of each of the long side cushions. It is played using a cue and snooker balls: one white cue ball, 15 red balls worth one point each, and six balls of different colors: yellow (2 points), green (3), brown (4), blue (5), pink (6) and black (7). A player (or team) wins a frame (individual game) of snooker by scoring more points than the opponent(s), using the cue ball to pot the red and colored balls. In this problem, your job is the referee of snooker. You should score both players, ask the correct player to play next, as well as place some of the balls back to the table if necessary. The rules of snooker needed for this problem are following. (We ignore some fouls about incorrectly hitting the cue ball here. We assume that the cue ball is never snookered after a foul, so free ball will never occur. We also assume that both players will make their best attempts to hit the ball on, so you do not need to declare a miss when they do not hit the ball on first.)

Similarity

At the beginning of each frame the balls are set up by the referee as illustrated above. This will be followed by a break-off shot, the white cue ball can be placed anywhere inside the D (it is called in-hand, which also happens when the cue ball is potted). Players take turns in visiting the table. A break is the number of points scored by a player in one single visit to the table. A player’s turn and break end when he fails to pot a ball, when he does something against the rules of the game, which is called a foul, or when a frame has ended.
The ball or balls that can be hit first by the white are called the ball(s)
"on" for that particular stroke. The ball(s) "on" differ from shot to shot:
a red ball, if potted, must be followed by a color, and so on until a break
ends; if a red is not potted, any red ball remains the ball "on". Only
a ball or balls "on" may be potted legally by a player. If a ball not "on"
is potted, this is a foul.
The game of snooker generally consists of two phases. The first phase is the situation in which there are still red balls on the table. In the first phase, at the beginning of a player’s turn, the balls "on" are all remaining red balls. The player must therefore attempt to first hit and pot one or more red balls. For every red ball potted, the player will receive 1 point. When a red has been potted, it will stay off the table and the player can continue his break. If no red has been potted or a foul has been made, the other player will come into play. In case one or more red balls have been potted, the player can continue his break. This time one of the six colors (yellow, green, brown, blue, pink and black) is the ball "on". Only one of these can be the ball "on"
and the rules of the game state that a player must nominate his desired color to the referee, although it is often clear which ball the striker is playing and it is not necessary to nominate. When the nominated color is potted, the player will be awarded the correct number of points (yellow, 2; green, 3; brown, 4; blue, 5; pink, 6; black, 7). The color is then taken out of the pocket by the referee and placed on its original spot. Because only one of the colors is the ball "on", it is a foul to first hit multiple colors at the same time, or pot more than one color. If a player fails to pot a ball "on", it being a red or nominated color, the other player will come into play and the balls "on" are always the reds, as long as there are still reds on the table. The alternation between red balls and colors ends when all reds have been potted and a color is potted after the last red, or a failed attempt to do so is made. Then the second phase begins. All six colors have to be potted in ascending order of their points value (yellow, green, brown, blue, pink, black). Each becomes the ball "on" in that order. During this phase, when potted, the colors stay down and are not replaced on the table, unless a foul is made when potting the color, in which case the color is respotted.
When only the black is left, the first score or foul ends the frame, and the player who has scored most points has won it. However, if the score is tied after that, the black is respotted, the players draw lots for choice of playing, the next player plays from in-hand, and the next score or foul ends the frame. When a foul is made during a shot, the player’s turn is ended and he will receive no points for the foul shot. The other player will receive penalty
points. Colors illegally potted are respotted (while reds are not), and if the cue ball is potted, the next player will play from in-hand. Fouls concerned in this problem are:

。failing to hit any other ball with the cue ball
。first hitting a ball "not-on" with the cue ball
。potting a ball "not-on"
。potting the white (in-off)

Penalty points are at least 4 points and at most 7 points. The number of penalty points is the value of the ball "on", or any of the "foul" balls, whichever is highest. When more than one foul is made, the penalty is not the added total – only the most highly valued foul is counted. As players usually do not nominate a color explicitly when hitting the colors, please be tolerant and assume that he always nominate the ball with the lowest score when it cannot be deduced from the ball first hit (i.e. when the cue ball does not hit any ball or hit a red first). If a player commits a foul, and his opponent considers that the position left is unattractive, he may request that the offender play again from the resulting position.

输入:

The input file contains multiple test cases. The first line of the input file is a single integer T (T ≤ 200), the number of test cases. For each test case (frame), the first line contains the names of the two players separated by a whitespace. The first player will take the break-off shot. Each name is made up of no more than 20 English letters, and the two names are different.
After that, the input mainly consists of lines that describe a stroke each (with two exceptions stated later). A stroke is described by the color of the ball first hit by the cue ball (or "None" if the cue ball does not hit any ball), followed by zero or more colors of the balls potted, all separated by whitespaces. For example, a line "Red Red White Red" means the cue ball first hit a red ball, and 2 reds are potted as well as the cue ball itself; and a line "None" means the cue ball does not hit any ball thus no ball is potted. You can assume that all strokes are legal according to the balls remain on the table, and the cue ball will not hit two or more ball first simultaneously. A line "Play again" may appear if and only if the last stroke is a foul. It means the other player request that the offender play again from the resulting position.
If a score or foul occurs when only the black is left, and the score is tied after that, a line with either player’s name will follow. That means the player will play next as a result of the lot. The case end when the frame ends. There is a blank line before every test case.

输出:

The input file contains multiple test cases. The first line of the input file is a single integer T (T ≤ 200), the number of test cases. For each test case (frame), the first line contains the names of the two players separated by a whitespace. The first player will take the break-off shot. Each name is made up of no more than 20 English letters, and the two names are different.
After that, the input mainly consists of lines that describe a stroke each (with two exceptions stated later). A stroke is described by the color of the ball first hit by the cue ball (or "None" if the cue ball does not hit any ball), followed by zero or more colors of the balls potted, all separated by whitespaces. For example, a line "Red Red White Red" means the cue ball first hit a red ball, and 2 reds are potted as well as the cue ball itself; and a line "None" means the cue ball does not hit any ball thus no ball is potted. You can assume that all strokes are legal according to the balls remain on the table, and the cue ball will not hit two or more ball first simultaneously. A line "Play again" may appear if and only if the last stroke is a foul. It means the other player request that the offender play again from the resulting position.
If a score or foul occurs when only the black is left, and the score is tied after that, a line with either player’s name will follow. That means the player will play next as a result of the lot. The case end when the frame ends. There is a blank line before every test case.

样例输入:

1
Zero Maxbreak
Red White
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black
Red Red
Black Black

样例输出:

Frame 1
Zero's turn, in-hand
Foul!
0 : 4
Maxbreak's turn, in-hand
0 : 5
0 : 12
Respot Black
0 : 13
0 : 20
Respot Black
0 : 21
0 : 28
Respot Black
0 : 29
0 : 36
Respot Black
0 : 37
0 : 44
Respot Black
0 : 45
0 : 52
Respot Black
0 : 53
0 : 60
Respot Black
0 : 61
0 : 68

       http://acm.hdu.edu.cn/showproblem.php?pid=3791  

用数组建立二叉树:

                          二叉搜索树

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2354    Accepted Submission(s): 1016

Problem Description
判断两序列是否为同一二叉搜索树序列
 
Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
 
Output
如果序列相同则输出YES,否则输出NO
 
Sample Input
2
567432
543267
576342
0
 
Sample Output
YES
NO
 
Source
 
Recommend
notonlysuccess
//思路简单:只需要建树就行,判断是否为同一颗树。
//用数组建一颗树。
#include<stdio.h>
#include<string.h>
int main()
{
    int i,j,t,c;
    char s[22];
    int tree[1111];
    int tree1[1111];
    while(~scanf("%d",&t)&&t!=0)
    {
        scanf("%s",s);    
       memset(tree,-1,sizeof(tree));
        for(i=0;s[i]!='\0';i++)
        {
             c=s[i]-'0';
             j=1;
             while(tree[j]!=-1)
             {
             if(c<=tree[j]) j=j*2;
                else  j=j*2+1;
             }
             tree[j]=c;
        }//数组建树。
        while(t--)
        {
            scanf("%s",s);    
       memset(tree1,-1,sizeof(tree1));
        for(i=0;s[i]!='\0';i++)
        {
             c=s[i]-'0';
             j=1;
             while(tree1[j]!=-1)
             {
             if(c<=tree1[j]) j=j*2;
                else  j=j*2+1;
             }
             tree1[j]=c;
        }
        for(i=0;i<=1024&&tree[i]==tree1[i];i++);//判断是否为同一颗树。
    if(i>1024)
        puts("YES");
    else
        puts("NO");
        }
    }
return 0;
}



                  
        

 

参考:http://www.cnblogs.com/cancangood/archive/2013/10/10/3362103.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮