首页 > ACM题库 > HDU-杭电 > hdu 3956 SanguoSHA待解决[解题报告]C++
2015
04-14

hdu 3956 SanguoSHA待解决[解题报告]C++

SanguoSHA

问题描述 :

SanguoSHA is a very popular game. The rules of SanguoSHA are too complex for me to describe it in English, so just let me simplify it a lot. ^ ^.
March

In this custom game we have several rules shown below, and you should read carefully:
Part I–Identifies:
1): There are at most 8 players while at least 4;
2): There are 4 roles: Lord, Minister, Rebel, and Traitor.
3): The goal of the Lord and Ministers is to kill all of the Rebels and the Traitor.
4): The goal of the Rebel is to kill the Lord.
5): The goal of the Traitor is to make himself alive until the game over.
6): There is only 1 Lord.
7): There is only 1 Traitor.
8): There will be at least 1 Rebel.
9): There will be at least 1 Minister.
10): Every player know the total remain number of Rebel and Minister.

Part II–How to determine the game over and who wins:
1): If the Lord is alive, and there is neither alive Rebel nor Traitor, then the game over, and the Lord and Ministers win.
2): When the Lord is killed by someone, the game over, if there is no one but the Traitor alive, then the Traitor wins; otherwise, the Rebels win.

Part III–How to play in this custom game:
1): At first, the roles of all players except for the Lord are hidden, they only know their own roles. That means players have to conjecture others’ role by analysing their behavior.
2): In each round, all alive players play one by one. The player1 plays first, then player2…
3): In each player’s turn, the player can choose one and only one player to attack. The probability of killing the chosen one is P.
4): When a player is killed, his role should be announced.

Part IV–How to analysis player’s behaviors:
1): The Lord is always be considered as Lord.
2): A player will be considered as Rebel when he attack the Lord.
3): A player will be considered as Rebel when he attack one which considered as Minister before all Rebels are eliminated.
4): A player will be considered as Minister when he attack one which considered as Rebel.
5): A player will be considered as Traitor when he have been considered as Minister and Rebel.
6): The players are not clever enough, they can’t analysis other behaviors.

Part V–The attack strategy of each role:
Eliminated player couldn’t do anything.
No one will attack eliminated player or himself.
For each strategy, all eligible player have equal probability of being attacked.
The Rebel will choose one of the following strategies by order:
1)The Lord or Ministers if some players are considered as Minister.
2)The Lord or Traitor if a player is considered as Traitor.
3)The Lord.
The Lord and Ministers will choose one of the following strategies by order:
1)The player which be considered as Rebel.
2)The player which be considered as Traitor.
3)If all rebel roles are eliminated, then attack anyone except Lord.
4)The player with unknown role.
The Traitor will choose one of the following strategies by order:
1)The player which be considered as Minister if alive Minister number more than alive Rebel number.
2)The player which be considered as Rebel if alive Rebel number not less than alive Minister number.
3)Anyone expect the Lord.
4)The Lord.

Such information will be given:
1): The number of players.
2): Each player’s identify.
3): The probability of killing the chosen one.
For each role, you should calculate the probability of winning within 10 round.

输入:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
Each case consists of three lines, the first line is an integer N(4<=N<=8), indicating the number of players.
The second line contains N integers, player1,player2…playern, indicating the role of each player.(The first player will always be the Lord).(0, 1, 2, 3 indicating Lord, Minister, Rebel, and Traitor respectively.)
Then the third line contains a real number P(0<P<1).

输出:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
Each case consists of three lines, the first line is an integer N(4<=N<=8), indicating the number of players.
The second line contains N integers, player1,player2…playern, indicating the role of each player.(The first player will always be the Lord).(0, 1, 2, 3 indicating Lord, Minister, Rebel, and Traitor respectively.)
Then the third line contains a real number P(0<P<1).

样例输入:

2
4
0 1 2 3
0.5
4
0 3 2 1
0.5

样例输出:

Case 1:
Lord and Minister:0.549
Rebel:0.334
Traitor:0.118
Case 2:
Lord and Minister:0.501
Rebel:0.334
Traitor:0.166


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

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