发布于  更新于 

洛谷P2482 [SDOI2010]猪国杀

模拟 题解 OI

感到颓废怎么办? 当然是写大模拟了。

你一看这道题的题面长度,就知道坑点一定很多。建议大家先自己按自己理解写完再看题解(Orz某一遍AC的大佬)。

有关于身份的判断:事实上只要有人主动打出杀,决斗和无懈可击,就可以直接确定他的身份了,所以我们不需要真的模拟每个人对别人的看法,只需要把每个人是否暴露身份这一状态存起来,由他自己在行动的时候维护就行。

坑点:

  1. 死人要从场上清掉,维护next指针。
  2. 只能杀下家,不能杀上家。
  3. 牌堆的牌摸完后,再摸牌始终摸出最后的一张(题面好像没说,但洛谷的数据是这么造的,有两个点需要这么处理)
  4. AOE时,优先出无懈可击,然后是杀和闪。
  5. 有可能对自己用无懈可击。
  6. 无懈可击分两种,一种是献殷勤:挡格斗和AOE,一种是表敌意:抵消别人的无懈可击。
  7. 调不出来,多打log
  8. 枚举类型能有效地提升代码可读性
  9. 多复用代码,比如说南蛮入侵和万箭齐发就可以写进一个函数
  10. STL容器用户请注意:迭代中对容器的擦除有可能导致UB。(但是我用了STL,代码可读性就是比用数组的好,我用list维护手牌时间复杂度也比数组强(然并卵))
  11. 每出掉一张牌,要从头开始检查可能出的下一张牌(比如装了诸葛连弩,之前的杀都可以用了),所以迭代器非法化的情况也不存在了,反正都要break

代码

我自认为风格(特别是针对这种大模拟题)要比不少变量名不超过4个字符的人优秀。有了VSCode的IntelliSense,打着也不费事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
// 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;
}