洛谷P2482 [SDOI2010]猪国杀
28 August 2019 |
duanyll | Tags:
OI
题解
模拟
感到颓废怎么办？ 当然是写大模拟了。
你一看这道题的题面长度，就知道坑点一定很多。建议大家先自己按自己理解写完再看题解（Orz某一遍AC的大佬）。
有关于身份的判断：事实上只要有人主动打出杀，决斗和无懈可击，就可以直接确定他的身份了，所以我们不需要真的模拟每个人对别人的看法，只需要把每个人是否暴露身份这一状态存起来，由他自己在行动的时候维护就行。
坑点：
- 死人要从场上清掉，维护
next指针。 - 只能杀下家，不能杀上家。
- 牌堆的牌摸完后，再摸牌始终摸出最后的一张（题面好像没说，但洛谷的数据是这么造的，有两个点需要这么处理）
- AOE时，优先出无懈可击，然后是杀和闪。
- 有可能对自己用无懈可击。
- 无懈可击分两种，一种是献殷勤：挡格斗和AOE，一种是表敌意：抵消别人的无懈可击。
- 调不出来，多打log
- 枚举类型能有效地提升代码可读性
- 多复用代码，比如说南蛮入侵和万箭齐发就可以写进一个函数
- STL容器用户请注意：迭代中对容器的擦除有可能导致UB。（但是我用了STL，代码可读性就是比用数组的好，我用
list维护手牌时间复杂度也比数组强（然并卵）） - 每出掉一张牌，要从头开始检查可能出的下一张牌（比如装了诸葛连弩，之前的杀都可以用了），所以迭代器非法化的情况也不存在了，反正都要
break。
代码
我自认为风格（特别是针对这种大模拟题）要比不少变量名不超过4个字符的人优秀。有了VSCode的IntelliSense，打着也不费事。
// luogu-judger-enable-o2
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 12;
const int MAXM = 1010;
const int PLAYER_MAX_HP = 4;
enum card_type : char {
// no_card = '\0',
peach = 'P', // 桃
kill = 'K', // 杀
dodge = 'D', // 闪
fight = 'F', // 决斗
south_attack = 'N', // 南蛮入侵
arrow_attack = 'W', // 万箭齐发
watertight = 'J', // 无懈可击
crossbow = 'Z' // 诸葛连弩
};
string card_name(card_type card) {
switch (card) {
case peach:
return "桃";
case kill:
return "杀";
case dodge:
return "闪";
case fight:
return "决斗";
case south_attack:
return "南蛮入侵";
case arrow_attack:
return "万箭齐发";
case watertight:
return "无懈可击";
case crossbow:
return "诸葛连弩";
}
}
enum player_type { king, minister, rebel };
queue<card_type> card_heap; // 牌堆
class player;
int n;
player* p[MAXN];
#ifndef DEBUG
#define clog \
if (false) clog
#endif
void end_game(string winner);
class player {
protected:
void take_card() {
if (card_heap.empty()) {
cerr << "错误! 牌堆被摸完了." << endl;
exit(EXIT_FAILURE);
}
clog << id << "摸了一张" << card_name(card_heap.front()) << endl;
hand_card.push_back(card_heap.front());
// 据说牌堆摸完后，一直取最后一张牌
if (card_heap.size() > 1) card_heap.pop();
}
void show_identity() {
clog << id << "暴露了身份, 他的身份是" << role << endl;
if (role == rebel) {
possible_role = enemy;
} else if (role == minister) {
possible_role = loyal;
}
}
// 是否向目标表敌意
bool should_attack(player* target) {
switch (role) {
case king:
return (target->possible_role == enemy ||
target->possible_role == pseudo_enemy);
case minister:
return (target->possible_role == enemy);
case rebel:
return (target->role == king || target->possible_role == loyal);
}
return false;
}
// 是否向目标献殷勤
bool should_protect(player* target) {
switch (role) {
case king:
case minister:
return (target->role == king || target->possible_role == loyal);
case rebel:
return (target->possible_role == enemy);
}
return false;
}
// 返回是否成功被无懈可击抵消, is_friendship:
// 使用这次无懈可击是对target献殷勤还是表敌意
bool ask_around_for_watertight(player* target, bool is_friendship) {
bool first = true;
for (player* cur = this; first || cur != this;
cur = cur->next, first = false) {
if (is_friendship ? (cur->should_protect(target))
: (cur->should_attack(target))) {
if (cur->try_use_card(watertight)) {
clog << cur->id << "使用了无懈可击抵消了" << id
<< "的锦囊, 向" << target->id
<< (is_friendship ? "献殷勤" : "表敌意") << endl;
// 只要用了无懈可击就暴露身份了
cur->show_identity();
return (!cur->ask_around_for_watertight(cur, false));
}
}
}
return false;
}
// 返回所有对象中当前应该表敌意的对象
player* find_enemy() {
if (role == rebel) return p[1];
for (player* cur = next; cur != this; cur = cur->next) {
if (should_attack(cur)) return cur;
}
return nullptr;
}
// 返回应该出杀的对象
player* find_kill_target() {
if (role == rebel) {
// 在主公旁边
if (next == p[1]) return p[1];
}
if (should_attack(next)) return next;
return nullptr;
}
bool try_kill(list<card_type>::iterator& card) {
player* target = find_kill_target();
if (target == nullptr) return false;
card = hand_card.erase(card);
clog << id << "向" << target->id << "使用了杀" << endl;
// 尝试使用杀，已经是跳忠或跳反的行为
show_identity();
if (!target->try_use_card(dodge)) target->hurt(this);
return true;
}
bool try_fight(list<card_type>::iterator& card) {
player* target = find_enemy();
if (target == nullptr) return false;
card = hand_card.erase(card);
clog << id << "向" << target->id << "使用了决斗" << endl;
// 尝试使用决斗，已经是跳忠或跳反的行为
show_identity();
if (!ask_around_for_watertight(target, true)) {
// 忠臣不会对主公出杀
if (role == king && target->role == minister) {
target->hurt(this);
return true;
}
while (true) {
if (!target->try_use_card(kill)) {
target->hurt(this);
return true;
}
if (!try_use_card(kill)) {
hurt(target);
return true;
}
}
}
return true;
}
// 尝试出牌，返回是否成功
bool try_use_card(card_type card) {
for (auto i = hand_card.begin(); i != hand_card.end(); i++) {
if (*i == card) {
clog << id << "出了" << card_name(card) << endl;
hand_card.erase(i);
return true;
}
}
return false;
}
void use_aoe(card_type response) {
for (player* cur = next; cur != this; cur = cur->next) {
if (!ask_around_for_watertight(cur, true)) {
if (!cur->try_use_card(response)) {
cur->hurt(this);
if (cur->role == king && possible_role == unknown) {
clog << "主公将" << id << "视作了类反贼" << endl;
possible_role = pseudo_enemy;
}
}
}
}
}
// 挨血一点
void hurt(player* source) {
hp--;
clog << id << "受到一点伤害, 当前HP: " << hp << endl;
if (hp == 0) {
if (try_use_card(peach)) {
hp = 1;
return;
} else {
clog << id << "死亡" << endl;
// 玩家死亡
// 判断是否达成游戏条件
if (role == king)
end_game("FP");
else {
bool remain_rebel = false;
for (int i = 1; i <= n; i++) {
if (p[i]->role == rebel && p[i]->hp > 0) {
remain_rebel = true;
break;
}
}
if (!remain_rebel) end_game("MP");
}
prev->next = next;
next->prev = prev;
if (role == rebel) {
clog << "反贼被杀, " << source->id << "摸三张牌" << endl;
source->take_card();
source->take_card();
source->take_card();
} else if (role == minister && source->role == king) {
clog << "主公杀死了忠臣, 弃置所有手牌和装备" << endl;
source->hand_card.clear();
source->equipment = (card_type)'\0';
}
}
}
}
public:
int hp = PLAYER_MAX_HP;
int id;
list<card_type> hand_card; // 手牌
player_type role;
card_type equipment = (card_type)'\0';
player* next = nullptr;
player* prev = nullptr;
enum possible_role_type {
unknown,
loyal,
enemy,
pseudo_enemy
} possible_role = unknown;
player(int ID, player_type r) : id(ID), role(r) {}
void run_round() {
clog << "开始" << id << "的回合, 当前HP: " << hp << ", 身份: " << role
<< endl;
// 摸两张牌
take_card();
take_card();
clog << id << "当前手牌: ";
for (auto i : hand_card) {
clog << card_name(i) << ' ';
}
clog << endl;
bool kill_used = false, card_used = false;
do {
card_used = false;
for (auto i = hand_card.begin(); i != hand_card.end(); i++) {
switch (*i) {
case peach:
if (hp < PLAYER_MAX_HP) {
i = hand_card.erase(i);
card_used = true;
hp++;
clog << id << "使用了桃, 回血到" << hp << endl;
}
break;
case kill:
if (kill_used && equipment != crossbow) break;
card_used = kill_used = try_kill(i);
break;
case fight:
card_used = try_fight(i);
break;
case south_attack:
clog << id << "使用了南蛮入侵" << endl;
i = hand_card.erase(i);
use_aoe(kill);
card_used = true;
break;
case arrow_attack:
clog << id << "使用了万箭齐发" << endl;
i = hand_card.erase(i);
use_aoe(dodge);
card_used = true;
break;
case crossbow:
clog << id << "装备了诸葛连弩" << endl;
i = hand_card.erase(i);
equipment = crossbow;
card_used = true;
break;
default:
card_used = false;
break;
}
// 考虑手牌被弃置的情况
if (card_used) break;
}
} while (card_used && hp > 0);
clog << "结束" << id << "号玩家的回合" << endl << endl;
}
};
void end_game(string winner) {
cout << winner << endl;
for (int i = 1; i <= n; i++) {
if (p[i]->hp == 0) {
cout << "DEAD" << endl;
} else {
int cnt = 0;
for (auto j : p[i]->hand_card) {
cout << (char)j
<< (++cnt == p[i]->hand_card.size() ? '\n' : ' ');
}
if (p[i]->hand_card.size() == 0) cout << endl;
// cout << endl;
}
}
exit(EXIT_SUCCESS);
}
int main() {
int m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
player_type role =
(s == "MP") ? king : ((s == "ZP") ? minister : rebel);
p[i] = new player(i, role);
for (int j = 1; j <= 4; j++) {
char ch;
do {
ch = getchar();
} while (!isupper(ch));
p[i]->hand_card.push_back((card_type)ch);
}
}
for (int i = 1; i <= n; i++) {
p[i]->next = p[(i == n) ? 1 : i + 1];
p[i]->prev = p[(i == 1) ? n : i - 1];
}
for (int i = 1; i <= m; i++) {
char ch;
do {
ch = getchar();
} while (!isupper(ch));
card_heap.push((card_type)ch);
}
while (true) {
for (int i = 1; i <= n; i++) {
if (p[i]->hp > 0) {
p[i]->run_round();
}
}
}
return 0;
}