题目
[狼人杀模拟器]
逻辑
加粗是一些细节的理解
游戏过程：游戏分为夜晚和白天。
-
(夜晚) 拿到狼人身份的玩家睁眼，其他人闭眼。狼人们商量后选择一名玩家击杀；
11. 狼人只击杀非狼人，并且在场玩家知晓这点所以被狼人杀的人，死后 c 变为 100- 狼人优先击杀熊，其他时候击杀 c 最高的好人（村民阵营），如果有多个目标，则击杀座位号小号。如果熊活着，特判熊
- 每天夜里，如果相邻两名存活玩家有任何一个是狼人，熊会发出咆哮。如果驯熊人已经死亡，则这一局熊不再咆哮。驯熊人如果当晚被杀，熊也不会咆哮。（相邻指向左找第一名存活玩家和向右找第一名存活玩家，当晚被杀的玩家也视为死亡）熊如果被杀，当晚不叫。找相邻时也要处理当晚被杀的人
-
(白天) 所有人睁眼；
-
法官宣布昨晚出局的玩家，以及熊是否咆哮了；
31. 先宣布出局的玩家，如果是猎人，猎人虽然知道熊咆哮了，但是不知道熊是谁，所以在 c 没有更新的情况下选择目标- 如果驯熊人在第一次发言前死亡，则场上玩家不知道其位置，也无法利用熊的咆哮信息除了第一天晚上被狼人杀了，也有可能是第一天早上被不知情的猎人杀了，都发生在第一次熊说话之前。区别在于如果被狼人杀了，熊不会叫；如果没被狼人杀且熊身边有狼人，熊会叫；但是模拟器设定，只要熊没有说过话，信息就当做不知道。这里是与实际完美推理矛盾的
-
出局的玩家离开游戏，发动技能（如果有）；
41. 猎人出局时发动技能，使 ta 的 c 变为 100；猎人会射杀 c 最低的玩家，如果有多个目标，则射杀座位号小号猎人不是死亡时发动技能，而是在白天法官宣布之后，出局时发动技能 -
法官检查胜利条件，如果任何一个满足则结束游戏；
51. 狼人的胜利条件是 狼人阵营的玩家数 >= 村民阵营的玩家数- 村民的胜利条件是 所有狼人出局
-
在场玩家进行一轮发言，并票选最可疑的玩家出局；
61. 第一天发言时**（这里下面的官方解释第一天只有晚上，第一次发言是第二天白天）**，如果驯熊人依然存活，驯熊人会公布身份，使 ta 的 c 变为 100 只有这个时候熊活着，才能使用熊有关的信息- 如果熊咆哮了，人们开始怀疑其左右的未知身份玩家，这使他们的 c 变为原来的一半 (向下取整, 如果原来是 1 则不变)**特判 1 **
- 如果熊咆哮了且左右的在局一方为铁好人，则另一方成为铁狼；如果其中一方后来被发现是铁好人，人们也会更新另一方的 c 只有一方 c 为 100 时，另一方会变为 0 。c 为 0 时，另一方不会变为 100。后续回合也生效。
- 如果熊在场且没有咆哮，则左右的在场玩家成为铁好人
- 白痴被投票出局时自动亮出底牌并且不出局，使 ta 的 c 变为 100 只有投票时才有用，被猎人带走不能用
- 猎人出局时发动技能
-
被选中的玩家离开游戏，发动技能（如果有）；
71. 猎人出局时发动技能 -
法官检查胜利条件，如果任何一个满足则结束游戏；
-
重复 1；
用例
示例1：
Input: players = ["bear","vil","vil","ww","vil","vil","idiot","ww","hunter","ww","ww","vil"], credibility = [9,55,62,74,43,70,13,23,15,78,61,66]
Output: false官方解释：
第一天夜晚，狼人击杀玩家 5，熊没有咆哮。
第二天白天，玩家 0 公布自己熊的身份。玩家 1 和玩家 11 成为 铁好人。看上去最可疑的玩家 6 被投出，但是因为是 白痴 身份，并没有出局。玩家 6 成为 铁好人。
第二天夜晚，狼人击杀玩家 0 驯熊人。熊没有咆哮。
第三天白天，身份最低的玩家 8 猎人被投票出局。猎人选择带走场上可信度最低的玩家 7。
第三天夜晚，狼人击杀身份最高的玩家 1 村民。
第四天白天，身份最低的玩家 4 村民被投票出局。（此时狼人数 == 村民数，已经结束游戏了，狼人胜利）
第四天夜晚，狼人击杀玩家 6 白痴, 此时场上狼人数量等于好人数量，狼人胜利。
[log]
=== Night 1 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = b v v w v v i w h w w v
[C] = 9 55 62 74 43 70 13 23 15 78 61 66
1. Close Eyes Kill = 5
=== Day 2 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[5] dead
5. Check Game over: false
6. Talk Bear roar effect: true
Bear talk
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = b v v w v i w h w w v
[C] = 100 100 62 74 43 100 13 23 15 78 61 100
7. Vote Vote = 6
Idiot will not be voted out
8. Check Game over: false
=== Night 2 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = b v v w v i w h w w v
[C] = 100 100 62 74 43 100 100 23 15 78 61 100
1. Close Eyes Kill = 0
=== Day 3 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[0] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v w v i w h w w v
[C] = 100 100 62 74 43 100 100 23 15 78 61 100
7. Vote Vote = 8
Player[8] dead
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v w v i w w w v
[C] = 100 100 62 74 43 100 100 23 100 78 61 100
Hunter kill = 7
Player[7] dead
8. Check Game over: false
=== Night 3 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v w v i w w v
[C] = 100 100 62 74 43 100 100 23 100 78 61 100
1. Close Eyes Kill = 1
=== Day 4 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[1] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w v i w w v
[C] = 100 100 62 74 43 100 100 23 100 78 61 100
7. Vote Vote = 4
Player[4] dead
8. Check Game over: true示例2：
Input: players = ["vil", "vil", "vil", "ww", "vil", "ww", "ww", "vil", "ww", "bear", "hunter", "idiot"], credibility = [81, 71, 88, 31, 34, 40, 70, 94, 73, 79, 98, 48]
Output: true官方解释：
第一回合猎人出局，熊咆哮了，但由于熊没有跳身份，对于猎人是无效信息，不能更新 c ，猎人击杀 3 号位玩家狼人。本回合投票投出 11 号白痴，白痴亮出身份牌， c 变为 100 。
没问题
投票出 11 号是因为 10 号猎人晚上死了，9 号熊的相邻为 8 号和 11 号，所以两边 c /= 2
[log]
=== Night 1 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v w v w w v w b h i
[C] = 81 71 88 31 34 40 70 94 73 79 98 48
1. Close Eyes Kill = 10
=== Day 2 ===
2. Open Eyes
3. Announce Bear roar: true
4. Kill Player[10] dead
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v w v w w v w b i
[C] = 81 71 88 31 34 40 70 94 73 79 100 48
Hunter kill = 3
Player[3] dead
5. Check Game over: false
6. Talk Bear roar effect: true
Bear talk
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v v w w v w b i
[C] = 81 71 88 31 34 40 70 94 36 100 100 24
7. Vote Vote = 11
Idiot will not be voted out
8. Check Game over: false
=== Night 2 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v v w w v w b i
[C] = 81 71 88 31 34 40 70 94 0 100 100 100
1. Close Eyes Kill = 9
=== Day 3 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[9] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v v w w v w i
[C] = 81 71 88 31 34 40 70 94 0 100 100 100
7. Vote Vote = 8
Player[8] dead
8. Check Game over: false
=== Night 3 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v v w w v i
[C] = 81 71 88 31 34 40 70 94 0 100 100 100
1. Close Eyes Kill = 11
=== Day 4 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[11] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v v w w v
[C] = 81 71 88 31 34 40 70 94 0 100 100 100
7. Vote Vote = 4
Player[4] dead
8. Check Game over: false
=== Night 4 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v w w v
[C] = 81 71 88 31 34 40 70 94 0 100 100 100
1. Close Eyes Kill = 7
=== Day 5 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[7] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v w w
[C] = 81 71 88 31 34 40 70 100 0 100 100 100
7. Vote Vote = 5
Player[5] dead
8. Check Game over: false
=== Night 5 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v v w
[C] = 81 71 88 31 34 40 70 100 0 100 100 100
1. Close Eyes Kill = 2
=== Day 6 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[2] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v v w
[C] = 81 71 100 31 34 40 70 100 0 100 100 100
7. Vote Vote = 6
Player[6] dead
8. Check Game over: true示例3：
Input: players = ["vil","ww","bear","hunter","ww","idiot","vil","vil","ww","vil","ww","vil"], credibility = [45,67,32,25,1,27,99,85,3,54,3,25]
Output: true官方解释：
最后一轮投票，猎人被投出，发动技能。由于此时猎人已经是铁好人，通过第一轮熊咆哮可以得出 1 号位是铁狼，所以本轮猎人击杀 1 号位狼人，游戏结束，村民胜利。
没问题
[log]
=== Night 1 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w b h w i v v w v w v
[C] = 45 67 32 25 1 27 99 85 3 54 3 25
1. Close Eyes Kill = 6
=== Day 2 ===
2. Open Eyes
3. Announce Bear roar: true
4. Kill Player[6] dead
5. Check Game over: false
6. Talk Bear roar effect: true
Bear talk
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w b h w i v w v w v
[C] = 45 33 100 12 1 27 100 85 3 54 3 25
7. Vote Vote = 4
Player[4] dead
8. Check Game over: false
=== Night 2 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w b h i v w v w v
[C] = 45 33 100 12 1 27 100 85 3 54 3 25
1. Close Eyes Kill = 2
=== Day 3 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[2] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w h i v w v w v
[C] = 45 33 100 12 1 27 100 85 3 54 3 25
7. Vote Vote = 8
Player[8] dead
8. Check Game over: false
=== Night 3 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w h i v v w v
[C] = 45 33 100 12 1 27 100 85 3 54 3 25
1. Close Eyes Kill = 7
=== Day 4 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[7] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w h i v w v
[C] = 45 33 100 12 1 27 100 100 3 54 3 25
7. Vote Vote = 10
Player[10] dead
8. Check Game over: false
=== Night 4 ===
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w h i v v
[C] = 45 33 100 12 1 27 100 100 3 54 3 25
1. Close Eyes Kill = 9
=== Day 5 ===
2. Open Eyes
3. Announce Bear roar: false
4. Kill Player[9] dead
5. Check Game over: false
6. Talk Bear roar effect: false
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w h i v
[C] = 45 33 100 12 1 27 100 100 3 100 3 25
7. Vote Vote = 3
Player[3] dead
[ 0][ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9][10][11]
[P] = v w i v
[C] = 45 0 100 100 1 27 100 100 3 100 3 25
Hunter kill = 1
Player[1] dead
8. Check Game over: true答题
class Solution {
public:
void printPlayerStatus()
{
cout << "\t";
for (int n = 0; n < players.size(); n++)
{
cout << "[" << setiosflags(ios::right) << setw(2) << n << "]";
}
cout << endl;
cout << "[P] = \t";
for (int n = 0; n < players.size(); n++)
{
if (isAlive[n])
{
cout << setiosflags(ios::right) << setw(3) << players[n][0] << " ";
}
else
{
cout << " ";
}
}
cout << endl;
cout << "[C] = \t";
for (int n = 0; n < players.size(); n++)
{
cout << setiosflags(ios::right) << setw(3) << credibility[n] << " ";
}
cout << endl;
}
int getWerewolfTarget()
{
printPlayerStatus();
if (bearId[1] != -1 && isAlive[bearId[0]]) return bearId[0];
int target = -1;
int c = 0;
for (auto n : teamV)
{
if (!isAlive[n]) continue;
if (c >= credibility[n]) continue;
target = n;
c = credibility[n];
}
return target;
}
int getVillagerTarget()
{
printPlayerStatus();
int target = -1;
int c = 100;
for (int n = 0; n < players.size(); n++)
{
if (!isAlive[n]) continue;
if (c <= credibility[n]) continue;
target = n;
c = credibility[n];
}
return target;
}
bool checkGameOver()
{
if (cntW >= cntV)
{
winner = false;
return true;
}
if (cntW == 0)
{
winner = true;
return true;
}
return false;
}
void updateOpposite(int n, int c)
{
credibility[n] = c;
if (c != 100) return;
int rc = 0;
for (auto& p : opposite[n])
{
if (credibility[p] == rc) continue;
updateOpposite(p, rc);
}
}
vector<int> getBeside(int n, int killId)
{
vector<int> dd = { 1, 11 };
vector<int> ret;
for (auto d : dd)
{
int nxt = n;
do
{
nxt = (nxt + d) % players.size();
} while (!isAlive[nxt] || nxt == killId);
ret.push_back(nxt);
}
return ret;
}
bool actBearRoar(int killId, vector<int>& nxt)
{
int n = bearId[0];
if (killId == bearId[0]) return false;
if (!isAlive[n]) return false;
nxt = getBeside(n, killId);
for (auto p : teamW)
{
if (nxt[0] != p && nxt[1] != p) continue;
return true;
}
return false;
}
void actBearTalk(bool bearRoar, vector<int>& nxt)
{
int n = bearId[0];
if (daynum == 2)
{
cout << "\t\t\t\tBear talk" << endl;
bearId[1] = n;
updateOpposite(n, 100);
}
if (!bearRoar)
{
updateOpposite(nxt[0], 100);
updateOpposite(nxt[1], 100);
return;
}
for (int i = 0; i < nxt.size(); i++)
{
int p1 = (i == 0) ? nxt[0] : nxt[1];
int p2 = (i != 0) ? nxt[0] : nxt[1];
opposite[p1].push_back(p2);
int c = -1;
c = (credibility[p1] == 100) ? credibility[p1] : c;
if (c == -1)
{
credibility[p1] = (credibility[p1] == 1) ? 1 : credibility[p1] / 2;
}
else
{
int rc = 0;
updateOpposite(p2, rc);
}
}
}
void actHunter(int n)
{
updateOpposite(n, 100);
int hunterKillId = getVillagerTarget();
cout << "\t\t\t\tHunter kill = " << hunterKillId << endl;
onDead(hunterKillId);
}
void actIdiot(int n)
{
updateOpposite(n, 100);
cout << "\t\t\t\tIdiot will not be voted out" << endl;
}
void onDead(int n)
{
cout << "\t\t\t\tPlayer[" << n << "] dead" << endl;
isAlive[n] = 0;
for (auto p : teamV) cntV -= (p == n);
for (auto p : teamW) cntW -= (p == n);
}
void onKilled(int n)
{
onDead(n);
if (players[n] == "hunter")
{
actHunter(n);
}
else
{
updateOpposite(n, 100);
}
}
void onVoted(int n)
{
if (players[n] == "idiot")
{
actIdiot(n);
}
else
{
onDead(n);
}
if (players[n] == "hunter")
{
actHunter(n);
}
}
bool canVillagersWin(vector<string>& p, vector<int>& c)
{
players = p;
credibility = c;
cntV = 8;
cntW = 4;
daynum = 1;
isAlive = vector<int>(players.size(), 1);
bearId = vector<int>(2, -1);
opposite = vector<vector<int>>(players.size(), vector<int>());
for (int i = 0; i < players.size(); i++)
{
if (players[i] == "vil" || players[i] == "hunter" || players[i] == "idiot" || players[i] == "bear")
{
teamV.push_back(i);
bearId[0] = (players[i] == "bear") ? i : bearId[0];
}
else if (players[i] == "ww")
{
teamW.push_back(i);
}
}
bool gameOver = false;
while (!gameOver)
{
cout << endl << "=== Night " + to_string(daynum) << " ===" << endl;
int killId = getWerewolfTarget();
vector<int> beside;
bool bearRoar = actBearRoar(killId, beside);
cout << "1. Close Eyes \t\t\tKill = " << killId << endl;
daynum++;
cout << endl << "=== Day " + to_string(daynum) << " ===" << endl;
cout << "2. Open Eyes" << endl;
cout << "3. Announce \t\t\tBear roar: " << boolalpha << bearRoar << endl;
cout << "4. Kill";
onKilled(killId);
gameOver = checkGameOver();
cout << "5. Check \t\t\tGame over: " << boolalpha << gameOver << endl;
if (gameOver) break;
cout << "6. Talk \t\t\tBear roar effect: " << boolalpha << (bool)isAlive[bearId[0]] << endl;
if (isAlive[bearId[0]])
{
actBearTalk(bearRoar, beside);
}
int voteId = getVillagerTarget();
cout << "7. Vote \t\t\tVote = " << voteId << endl;
onVoted(voteId);
gameOver = checkGameOver();
cout << "8. Check \t\t\tGame over: " << boolalpha << gameOver << endl;
if (gameOver) break;
}
return winner;
}
private:
vector<string> players;
vector<int> credibility;
vector<int> isAlive;
vector<vector<int>> opposite;
vector<int> teamV;
vector<int> teamW;
vector<int> bearId;
int cntV;
int cntW;
int daynum;
bool winner;
};致谢
作为桌游玩家，一定完成这道题。
感谢大佬指点，提交已通过，文章已更新。
return "明年再战狼人杀！";
评论 (2)
