P2482 [SDOI2010] 猪国杀——大模拟题解
Author: Yuyi
一、先理解题意：这不是博弈，而是确定性模拟
这道题看起来像一局复杂的卡牌游戏，但题目已经规定了每只猪在任何情况下的行动准则，因此我们不需要搜索最优策略，也不需要做博弈论。
我们真正要做的是：
按照题目给定的优先级，完整、准确地重放整局游戏，直到一方满足胜利条件。
游戏中的每一个选择实际上都是确定的：
- 每回合固定摸两张牌；
- 出牌时，每次使用手牌中最靠左的可用牌；
- 「杀」只能攻击距离为 1 的目标；
- 「决斗」可以攻击任意距离的合法目标；
- 「南猪入侵」和「万箭齐发」按座位顺序逐个结算；
- 是否使用「无懈可击」由真实身份、目标的已知身份以及当前行为是献殷勤还是表敌意共同决定；
- 一旦有人死亡，要立刻判断胜负，再执行仍然需要执行的奖励或惩罚。
所以本题的核心不是算法复杂度，而是把题面中的每一条规则翻译成状态和函数，并保证事件发生的先后顺序完全正确。
二、最重要的建模：真实身份与公开身份必须分开
每只猪都有两个不同的“身份”。
1. 真实身份 sf[i]
真实身份在整局游戏中不会改变：
sf[i] | 真实身份 |
|---|
| 1 | 主猪 MP |
| 2 | 忠猪 ZP |
| 3 | 反猪 FP |
真实身份决定：
- 这只猪采用哪一套行动准则；
- 它死亡时是否触发奖励或惩罚；
- 忠猪与主猪决斗时是否放弃出杀；
- 游戏是否已经结束。
2. 公开状态 j[i]
其他猪做决策时，不能直接根据 sf[i] 看穿身份，而要根据它已经做出的行为判断。因此还需要记录公开状态：
j[i] | 含义 |
|---|
| 0 | 尚未跳身份 |
| 1 | 已跳忠 |
| 2 | 已跳反 |
| 3 | 被主猪视为类反猪 |
主猪的身份开局公开，所以初始化时令
注意，类反猪并不是真的跳反，它只代表主猪的怀疑。把它统一存在 j[i] 中没有问题，因为代码中只有主猪选择攻击目标时会把 j[i] == 3 当成敌人，忠猪和反猪都不会据此行动。
当一只忠猪或反猪通过「杀」「决斗」或「无懈可击」真正跳明身份后，直接覆盖原来的类反状态：
void jp(int p) {
if (sf[p] == 2) j[p] = 1;
if (sf[p] == 3) j[p] = 2;
}
这正好对应题目中的“如果之后跳了，那么主猪会重新认识这只猪”。
三、理解代码中所有主要变量
1. 全局状态
| 变量 | 含义 |
|---|
n | 猪的数量 |
m | 初始牌堆中的牌数 |
d | 牌堆，队首是当前牌堆顶 |
cd[i] | 第 i 只猪按从左到右顺序保存的手牌 |
cnt[i][c] | 第 i 只猪手中编号为 c 的牌有多少张 |
sf[i] | 第 i 只猪的真实身份 |
j[i] | 第 i 只猪当前公开出来的身份状态 |
bld[i] | 第 i 只猪当前的体力值 |
f_bld | 所有仍存活反猪的体力值之和 |
ak[i] | 第 i 只猪是否装备猪哥连弩 |
alive[i] | 第 i 只猪是否存活 |
其中最值得解释的是 cd 与 cnt 为什么要同时存在。
cd[i] 负责维护手牌顺序，因为主动出牌时必须找到最靠左的可用牌；cnt[i][c] 负责快速判断某种牌是否存在，例如受到「杀」时，只需判断：
二者始终满足不变量
cnt[i][c]=∣{k∣cd[i][k]=c}∣.
因此，每次摸牌、用牌和弃光手牌时，都必须同步修改这两个结构。
原代码开头还有一些竞赛模板中的通用定义：ll、inf、eps、dep、lowbit、maxn、mo、pi 等。它们并没有参与本题模拟，可以安全删除；rep 只是循环宏，read() 只是整数快读。为了让最终代码更清楚，文末版本删除了无关模板量，并统一使用 cin。
2. 牌的编号
为了方便使用数组统计，将八种牌映射为整数：
| 编号 | 字符 | 牌 |
|---|
| 1 | P | 桃 |
| 2 | K | 杀 |
| 3 | D | 闪 |
| 4 | F | 决斗 |
| 5 | N | 南猪入侵 |
| 6 | W | 万箭齐发 |
| 7 | J | 无懈可击 |
| 8 | Z | 猪哥连弩 |
check_cd() 完成字符到编号的转换，back_cd() 在最后输出时完成反向转换。
3. 各函数的职责
| 函数 | 职责 |
|---|
check_cd() | 把牌的字符转成 1∼8 的编号 |
back_cd() | 把牌的编号转回输出字符 |
use() | 使用并删除最靠左的一张指定牌 |
game_end() | 输出胜方及所有猪的最终手牌并结束程序 |
gave() | 从牌堆顶摸指定数量的牌 |
heal() | 回复一点体力，并同步反猪总血量 |
save() | 濒死时尝试使用桃自救 |
hurt() | 扣血，并处理自救、死亡、胜负、奖励和惩罚 |
get_next() | 找到下一只存活的猪 |
attack() | 按身份和牌种选择攻击目标 |
jp() | 在表敌意后跳明真实阵营 |
kill_player() | 结算「杀」与「闪」 |
wx() | 递归结算无懈可击链 |
nm() | 结算南猪入侵 |
wj() | 结算万箭齐发 |
jd() | 结算决斗 |
solve() | 初始化并执行整局游戏的回合循环 |
4. f_bld 为什么记录反猪总血量
代码维护
f_bld=i:sf[i]=3 ∧ alive[i]∑bld[i].
每当反猪受到一点伤害，就令 f_bld--；每当反猪吃桃，就令 f_bld++。
由于每次伤害都是 1 点，而且体力降到 0 后会立刻求桃或死亡，所以每只活反猪的体力一定为正。于是：
f_bld=0⟺所有反猪均已死亡.
这样便可以在反猪死亡后用 O(1) 的时间判断主猪阵营是否获胜。
四、手牌与摸牌的处理
1. 使用一张牌
use(p, cid) 做两件事：
- 将
cnt[p][cid] 减一；
- 从
cd[p] 中删除最靠左的一张 cid。
void use(int p, int cid) {
--cnt[p][cid];
for (int i = 0; i < (int)cd[p].size(); ++i) {
if (cd[p][i] == cid) {
cd[p].erase(cd[p].begin() + i);
break;
}
}
}
主动出牌时，外层已经从左到右找到了第一个可用牌种；同种牌在当前状态下的可用性完全相同，所以再删除最靠左的一张该种牌就是正确的。
2. 摸牌与牌堆耗尽
gave(p, x) 表示第 p 只猪连续摸 x 张牌。
题目规定牌堆空后，每次都视为摸到最后一张牌。因此牌堆中只剩一张牌时，不能再把它弹出：
if (d.size() > 1) d.pop_front();
这样最后一张牌会永远留在队首，之后每次摸牌都会得到它。
五、座位、距离与攻击目标
猪的行动顺序是
1→2→⋯→n→1→⋯
死亡的猪会被跳过。get_next(p) 从 p 的下家开始寻找第一只存活的猪，它就是与 p 距离为 1 的猪。
int get_next(int p) {
int curr = p % n + 1;
while (!alive[curr]) curr = curr % n + 1;
return curr;
}
attack(p, c) 统一寻找攻击目标，其中：
c == 0：使用「杀」，只能检查下一只存活的猪；c == 1：使用「决斗」，可以绕场寻找第一个合法目标。
目标规则如下：
| 使用者 | 「杀」的目标 | 「决斗」的目标 |
|---|
| 主猪 | 距离 1 且为跳反或类反 | 顺序第一只跳反或类反 |
| 忠猪 | 距离 1 且为跳反 | 顺序第一只跳反 |
| 反猪 | 优先距离 1 的主猪，否则距离 1 的跳忠 | 主猪 |
为什么反猪使用「决斗」时可以直接返回主猪？因为「决斗」没有距离限制，只要主猪仍存活就一定可以选择主猪；而主猪死亡时游戏已经立刻结束，不会继续模拟。
六、跳身份与类反猪
1. 使用「杀」或「决斗」
只要一只忠猪或反猪成功找到合法目标并打出「杀」或「决斗」，它就在表敌意，因此应立刻调用 jp(p)。
跳身份发生在牌打出时，而不是伤害生效时。即使「决斗」随后被无懈可击抵消，使用者也已经暴露身份。
2. 使用「无懈可击」
使用无懈可能是在献殷勤，也可能是在表敌意，但无论属于哪一种，忠猪和反猪只要使用了它，就一定会跳身份。因此 wx() 在用掉 J 后也要立即更新 j[i]。
3. 成为类反猪
只有同时满足以下条件时，主猪才会把某只猪视为类反猪：
- 该猪尚未跳身份，即
j[p] == 0；
- 它使用了「南猪入侵」或「万箭齐发」；
- 主猪没有无懈掉这次效果，也没有成功打出「杀」或「闪」；
- 主猪确实因此受到伤害。
所以类反判断必须放在 hurt() 之后，并且只在主猪实际掉血的分支执行：
hurt(i, p);
if (sf[i] == 1 && j[p] == 0) j[p] = 3;
七、逐张牌处理
1. 桃 P
自己的回合中，只要体力不足 4 且手中有桃，就把最靠左的桃吃掉。
濒死时，因为所有单次伤害都是 1，受伤前体力又一定大于 0，所以受伤后只可能恰好变成 0。此时至多需要一张桃即可回到 1 点体力。
2. 杀 K 与闪 D
找到合法目标后：
- 使用者打出「杀」并跳身份；
- 目标有「闪」就强制弃置最靠左的一张闪；
- 否则目标受到 1 点伤害。
每个出牌阶段用 used_k 记录是否已经出过杀。满足
时才允许继续出杀。装备猪哥连弩后 ak[i] = true，便不再受一次限制。
3. 决斗 F
先让目标出「杀」，然后双方交替出杀；第一个没有杀的一方受到对方造成的 1 点伤害。
唯一的特殊情况是：
主猪对真实身份为忠猪的目标发起决斗时，忠猪不会出杀。
代码直接让忠猪受伤：
if (sf[p] == 1 && sf[q] == 2) {
hurt(q, p);
return;
}
主猪之所以会攻击真实忠猪，只可能是该忠猪此前被误判成了类反猪。
4. 南猪入侵 N
从使用者的下家开始，按环形顺序逐一结算每只其他存活角色：
- 先询问是否有无懈链抵消当前目标的效果；
- 若未抵消，目标有「杀」则必须弃杀；
- 否则受到 1 点伤害；
- 若受伤者是主猪且使用者尚未跳身份，则使用者成为类反猪。
5. 万箭齐发 W
与南猪入侵完全相同，只需把响应牌从「杀」换成「闪」。
6. 猪哥连弩 Z
摸到后在出牌阶段必然装备。装备牌需要从手牌中移除，只在 ak[i] 中记录装备状态。
再次装备时旧武器被替换，但两把武器效果相同，所以仍然只需令
即可。
八、全题最难点：无懈可击链
定义：
bool wx(int p, int q, bool f)
三个参数分别表示：
p：原锦囊当前要作用的目标；q：本轮从哪只猪开始询问，初始时是锦囊使用者，递归时是上一张无懈的使用者；f：当前打出的无懈属于献殷勤还是表敌意。
其中：
f == true：要抵消锦囊或上一层敌意无懈，相当于对目标献殷勤；f == false：要抵消上一层献殷勤无懈，相当于对目标表敌意。
1. 哪些猪愿意献殷勤
| 无懈使用者 | 愿意保护的目标 |
|---|
| 主猪、忠猪 | 主猪或已经跳忠的猪 |
| 反猪 | 已经跳反的猪 |
未跳身份的猪不能被献殷勤，包括使用者自己。
2. 哪些猪愿意表敌意
| 无懈使用者 | 愿意敌对的目标 |
|---|
| 主猪 | 跳反猪或类反猪 |
| 忠猪 | 跳反猪 |
| 反猪 | 主猪或跳忠猪 |
3. 为什么递归返回取反
找到第一只必须使用无懈的猪 i 后：
- 用掉一张
J；
- 让它跳明身份；
- 从 i 开始询问，是否还有猪使用下一张无懈；
- 下一层行为的性质由献殷勤变为表敌意，或由表敌意变为献殷勤。
因此代码是：
如果后面无人再出无懈，递归返回 false，当前这张无懈就成功生效，因此取反后返回 true。
无懈数量与原锦囊是否生效的关系为：
递归中的每一层取反，恰好自动维护了这个奇偶关系。
特别注意：「南猪入侵」和「万箭齐发」不是整张牌只询问一次无懈，而是结算到每一只目标时，都要单独调用一次 wx()。
九、伤害、死亡、奖励与惩罚的严格顺序
hurt(p, q) 表示 p 受到来自 q 的一点伤害。处理顺序必须是：
- p 扣除一点体力；
- 如果 p 是反猪，同步令
f_bld--；
- 若体力仍大于 0，结束；
- 否则尝试使用自己的桃自救；
- 无桃则死亡，清空手牌和装备；
- 若死者是主猪，反猪立刻获胜；
- 若死者是最后一只反猪，主猪阵营立刻获胜；
- 若死者是反猪且游戏尚未结束，伤害来源摸三张牌；
- 若死者是忠猪且伤害来源是主猪，主猪弃掉所有手牌和装备。
题目强调“一旦达成胜利条件，游戏立刻结束”，所以判断最后一只反猪死亡必须放在摸三张奖励牌之前。
十、怎样保证每次使用最靠左的可用牌
每个出牌阶段都重复下面的过程：
- 从左到右扫描当前手牌；
- 判断当前牌在此刻是否可用；
- 找到第一张可用牌后立刻使用；
- 使用后重新从最左边开始扫描；
- 一整遍都找不到可用牌时，结束出牌阶段。
重新扫描非常重要，因为一张牌的结算可能造成：
- 有猪死亡，攻击距离发生变化；
- 使用者摸到击杀反猪奖励的三张新牌；
- 使用者跳身份，之后的无懈关系发生变化；
- 装上猪哥连弩，使后续的杀变得可用；
- 主猪误杀忠猪，手牌和装备被全部清空。
因此不能事先把“本回合要出的牌”一次性选出来。
十一、完整模拟流程
对每一只仍存活的猪 i：
- 摸两张牌；
- 令
used_k = false；
- 从左向右寻找第一张可用牌；
- 按牌的类型执行完整结算；
- 若成功用出一张牌，回到步骤 3；
- 若没有任何牌可用，结束该猪回合；
- 轮到下一只存活的猪。
外层不断循环，直到 game_end() 输出结果并立即结束程序。题目保证游戏一定结束。
十二、正确性证明
下面证明该算法最终输出题目规定的唯一游戏结果。
引理 1：手牌状态始终正确
摸牌时，算法同时把牌加入 cd[i] 末尾并增加对应的 cnt[i][c]；用牌时，同时删除 cd[i] 中最靠左的该类牌并减少计数；弃光手牌时同时清空二者。因此 cd 始终保存准确的手牌顺序，cnt 始终保存准确的牌数。
引理 2：算法每次使用的都是最靠左的可用牌
出牌阶段每次都从 cd[i] 的最左端开始扫描，并在遇到第一张当前可用的牌时立即使用，随后重新扫描。因此不会跳过任何更靠左的可用牌，符合题目规则。
引理 3：attack() 返回题目规定的攻击目标
对于「杀」，算法只检查下一只存活角色，恰好对应距离 1；对于「决斗」，算法按照逆时针顺序检查所有其他角色。各身份判断目标时使用的公开状态，与主猪、忠猪、反猪的行动准则逐项一致。因此返回的一定是题目规定的第一个合法目标；无目标时返回 0。
引理 4：wx() 正确模拟整条无懈链
每一层 wx() 都从当前锦囊或无懈的使用者开始，按逆时针顺序找到第一只按照行为准则必须使用无懈的猪。使用一张无懈后，下一层行为在献殷勤和表敌意之间切换，返回值同时取反。递归终点表示无人继续出无懈，所以逐层返回后，奇数张无懈抵消原效果，偶数张无懈保留原效果。故 wx() 与题面的无懈结算完全一致。
引理 5：每种牌的结算结果正确
桃、杀、闪、决斗、南猪入侵、万箭齐发、无懈可击和猪哥连弩分别由对应函数按题面顺序处理；其中群体锦囊按座位顺序对每个目标独立结算，决斗从目标开始交替出杀，忠猪面对主猪决斗时直接放弃出杀。因此每一张牌造成的状态变化都与题目一致。
引理 6：死亡后的胜负、奖励和惩罚正确
hurt() 在扣血后立刻处理桃、死亡和清牌，并在奖励与惩罚前优先判断主猪死亡或最后一只反猪死亡。因此所有死亡事件及其先后顺序都符合题意。
定理：算法输出正确的最终结果与手牌
初始状态由输入准确建立。假设某个游戏事件前，算法状态与真实游戏状态一致；由引理 1 至引理 6，算法选出的下一个行动、目标、响应及其造成的全部状态变化都与真实游戏一致，因此下一事件前状态仍然一致。由数学归纳法，直到游戏结束，算法始终与题目规定的游戏过程一致，所以输出的胜方、存活状态和手牌顺序均正确。
十三、复杂度分析
这是一道过程模拟题，游戏长度由实际对局决定。设：
- E 为整局游戏中发生的出牌、响应和结算事件总数；
- H 为游戏过程中单只猪手牌数的最大值。
扫描手牌和从双端队列中删除牌最坏需要 O(H)，寻找目标或寻找无懈使用者需要 O(n)，因此可以写成：
T=O(E(H+n)).
空间复杂度为：
O(nH+m).
本题中 n≤10、初始牌堆大小 m≤2000，且题目保证游戏结束，直接模拟足以通过。
十四、样例如何在代码中运行
样例第一轮中：
- 主猪摸到两张决斗，但忠猪和反猪都没有跳身份，所以没有合法目标；
- 忠猪连续打出三张南猪入侵；
- 主猪三次都无法出杀，掉到 1 点体力，并把忠猪记为类反猪；
- 反猪尚未跳反，因此不能对自己献殷勤，三次都不能用无懈保护自己，也掉到 1 点体力。
下一轮：
- 主猪把类反猪当作敌人，连续使用四张决斗；
- 目标真实身份是忠猪，所以面对主猪的决斗不会出杀，最终死亡；
- 主猪误杀忠猪，手牌与装备全部被清空；
- 反猪随后摸到一张杀，攻击主猪；主猪已经没有闪，因而死亡；
- 游戏立即结束，输出
FP。
十五、最容易丢分的细节
sf 是真实身份，j 是公开身份，二者绝对不能混用。- 类反猪仍然没有跳身份，其他角色不能把它当作已跳反猪。
- 只有主猪真的被南猪入侵或万箭齐发伤害，使用者才成为类反猪。
- 使用杀、决斗或无懈时立即跳身份，不能等到伤害生效。
- 南猪入侵和万箭齐发要对每个目标分别询问无懈。
- 无懈可以被无懈，行为性质每递归一层就翻转一次。
- 忠猪面对主猪的决斗不出杀；其他决斗都尽力出杀。
- 反猪死亡后应先判胜，再决定是否摸三张牌。
- 主猪误杀忠猪时，手牌和猪哥连弩都要清空。
- 装备牌不再属于手牌，最终输出时不能输出已装备的
Z。
- 使用一张牌后必须重新从手牌最左端扫描。
- 牌堆只剩最后一张时不能弹出，以后要反复摸这一张。
十六、AC 代码
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 2e3+5;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
X = 0;int w = 0; char ch = 0;
while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
if(w) X = -X;
}
int n,m;
deque<int> d;
deque<int> cd[11];
int sf[11];
int cnt[11][9];
int j[11];
int bld[11];
int f_bld;
bool ak[11];
bool alive[11];
int check_cd(string str)
{
if(str == "P") return 1;
if(str == "K") return 2;
if(str == "D") return 3;
if(str == "F") return 4;
if(str == "N") return 5;
if(str == "W") return 6;
if(str == "J") return 7;
if(str == "Z") return 8;
return 0;
}
string back_cd(int cdd)
{
if(cdd == 1) return "P";
if(cdd == 2) return "K";
if(cdd == 3) return "D";
if(cdd == 4) return "F";
if(cdd == 5) return "N";
if(cdd == 6) return "W";
if(cdd == 7) return "J";
if(cdd == 8) return "Z";
return "";
}
void use(int p,int cid)
{
cnt[p][cid] --;
rep(i,0,(int)cd[p].size()-1) if(cd[p][i] == cid)
{
cd[p].erase(cd[p].begin() + i);
break;
}
}
void game_end(bool f)
{
if(f) cout << "FP\n";
else cout << "MP\n";
rep(i,1,n)
{
if(!alive[i]) cout << "DEAD\n";
else
{
rep(k,0,(int)cd[i].size()-1)
{
if(k) cout << " ";
cout << back_cd(cd[i][k]);
}
cout << "\n";
}
}
exit(0);
}
void gave(int p,int x)
{
rep(i,1,x)
{
cnt[p][d.front()] ++;
cd[p].push_back(d.front());
if(d.size() > 1) d.pop_front();
}
}
void heal(int p)
{
bld[p] ++;
if(sf[p] == 3) f_bld ++;
return;
}
bool save(int p)
{
if(cnt[p][1])
{
use(p,1);
heal(p);
return 1;
}
else return 0;
}
void hurt(int p,int q)
{
bld[p] --;
if(sf[p] == 3) f_bld --;
if(bld[p] > 0) return;
if(save(p)) return;
alive[p] = 0;
cd[p].clear();
rep(i,1,8) cnt[p][i] = 0;
ak[p] = 0;
if(sf[p] == 1)
{
game_end(1);
}
if(sf[p] == 3)
{
if(f_bld == 0) game_end(0);
gave(q,3);
}
if(sf[p] == 2 && sf[q] == 1)
{
cd[q].clear();
rep(i,1,8) cnt[q][i] = 0;
ak[q] = 0;
}
}
int get_next(int p)
{
int curr = p % n + 1;
while(!alive[curr])
{
curr = curr % n + 1;
}
return curr;
}
int attack(int p,int c)
{
if(c)
{
if(sf[p] == 1)
{
rep(k,1,n-1)
{
int i = (p-1+k)%n+1;
if(alive[i] && (j[i] == 2 || j[i] == 3)) return i;
}
return 0;
}
if(sf[p] == 2)
{
rep(k,1,n-1)
{
int i = (p-1+k)%n+1;
if(alive[i] && j[i] == 2) return i;
}
return 0;
}
if(sf[p] == 3) return alive[1] ? 1 : 0;
}
else
{
int nxt = get_next(p);
if(sf[p] == 1)
{
if((j[nxt] == 2 || j[nxt] == 3) && alive[nxt]) return nxt;
return 0;
}
if(sf[p] == 2)
{
if(j[nxt] == 2) return nxt;
return 0;
}
if(sf[p] == 3)
{
if(sf[nxt] == 1 || j[nxt] == 1) return nxt;
return 0;
}
}
return 0;
}
void jp(int p)
{
if(sf[p] == 2) j[p] = 1;
if(sf[p] == 3) j[p] = 2;
}
void kill_player(int p,int q)
{
if(cnt[q][3])
{
use(q,3);
return;
}
hurt(q,p);
return;
}
bool wx(int p,int q,bool f)
{
int i = q;
rep(k,1,n)
{
if(alive[i] && cnt[i][7])
{
bool want_use = 0;
if(f)
{
if((sf[i] == 1 || sf[i] == 2) && (sf[p] == 1 || j[p] == 1)) want_use = 1;
if(sf[i] == 3 && j[p] == 2) want_use = 1;
}
else
{
if(sf[i] == 1 && (j[p] == 2 || j[p] == 3)) want_use = 1;
if(sf[i] == 2 && j[p] == 2) want_use = 1;
if(sf[i] == 3 && (sf[p] == 1 || j[p] == 1)) want_use = 1;
}
if(want_use)
{
use(i,7);
if(sf[i] == 2) j[i] = 1;
if(sf[i] == 3) j[i] = 2;
return !wx(p,i,!f);
}
}
i = i % n + 1;
}
return 0;
}
void nm(int p)
{
rep(i,p+1,n) if(alive[i])
{
if(wx(i,p,1)) continue;
if(cnt[i][2]) use(i,2);
else
{
hurt(i,p);
if(sf[i] == 1 && j[p] == 0) j[p] = 3;
}
}
rep(i,1,p-1) if(alive[i])
{
if(wx(i,p,1)) continue;
if(cnt[i][2]) use(i,2);
else
{
hurt(i,p);
if(sf[i] == 1 && j[p] == 0) j[p] = 3;
}
}
return;
}
void wj(int p)
{
rep(i,p+1,n) if(alive[i])
{
if(wx(i,p,1)) continue;
if(cnt[i][3]) use(i,3);
else
{
hurt(i,p);
if(sf[i] == 1 && j[p] == 0) j[p] = 3;
}
}
rep(i,1,p-1) if(alive[i])
{
if(wx(i,p,1)) continue;
if(cnt[i][3]) use(i,3);
else
{
hurt(i,p);
if(sf[i] == 1 && j[p] == 0) j[p] = 3;
}
}
return;
}
void jd(int p,int q)
{
if(wx(q,p,1)) return;
if(sf[p] == 1 && sf[q] == 2)
{
hurt(q,p);
return;
}
else
{
while(true)
{
if(cnt[q][2]) use(q,2);
else
{
hurt(q,p);
return;
}
if(cnt[p][2]) use(p,2);
else
{
hurt(p,q);
return;
}
}
}
}
void solve()
{
read(n),read(m);
rep(i,1,n)
{
string s;
cin >> s;
bld[i] = 4;
alive[i] = 1;
if(s == "MP")
{
sf[i] = 1;
j[i] = 1;
}
if(s == "ZP") sf[i] = 2;
if(s == "FP")
{
sf[i] = 3;
f_bld += 4;
}
rep(j,1,4)
{
string ss;
cin >> ss;
int tmp = check_cd(ss);
cnt[i][tmp] ++;
cd[i].push_back(tmp);
}
}
rep(i,1,m)
{
string s;
cin >> s;
d.push_back(check_cd(s));
}
if(f_bld == 0) game_end(0);
while(true)
{
rep(i,1,n) if(alive[i])
{
gave(i,2);
bool used_k = 0;
while(alive[i])
{
bool played = 0;
rep(cur,0,(int)cd[i].size()-1)
{
int now = cd[i][cur];
if(now == 1 && bld[i] < 4)
{
use(i,1);
heal(i);
played = 1;
break;
}
if(now == 5)
{
use(i,5);
nm(i);
played = 1;
break;
}
if(now == 6)
{
use(i,6);
wj(i);
played = 1;
break;
}
if(now == 8)
{
use(i,8);
ak[i] = 1;
played = 1;
break;
}
if(now == 2 && (ak[i] || !used_k))
{
int att = attack(i,0);
if(att)
{
use(i,2);
jp(i);
used_k = 1;
kill_player(i,att);
played = 1;
break;
}
}
if(now == 4)
{
int att = attack(i,1);
if(att)
{
use(i,4);
jp(i);
jd(i,att);
played = 1;
break;
}
}
}
if(!played) break;
}
}
}
return;
}
int main()
{
int T=1;
while (T--) solve();
return 0;
}
十七、按这个顺序一步一步写到 AC
如果自己重新实现，建议按以下顺序逐层调试：
- 先完成牌编号、输入、手牌顺序和
cnt 同步维护；
- 完成摸牌、末牌复用、桃与装备；
- 完成环形座位和「杀」的距离 1；
- 完成身份状态、跳忠、跳反和类反；
- 完成伤害、濒死吃桃、死亡清牌、奖励惩罚和立即判胜；
- 完成决斗，并单独处理忠猪面对主猪不出杀；
- 完成南猪入侵和万箭齐发的逐目标结算；
- 最后实现无懈递归，并检查奇偶张无懈的结果；
- 接入“从左到右找第一张可用牌，用后重新扫描”的出牌循环；
- 用题目样例检查输出，再针对上面的十二个易错点逐项造小数据。
这道题能否 AC，主要取决于状态是否分清、事件顺序是否严格，而不是使用了多高级的算法。