P2482

[SDOI2010] 猪国杀

题目描述

游戏背景

《猪国杀》是一种多猪牌类回合制游戏，一共有 $3$ 种角色：主猪，忠猪，反猪。每局游戏主猪有且只有 $1$ 只，忠猪和反猪可以有多只，每只猪扮演 $1$ 种角色。

游戏目的

主猪 / $\texttt{MP}$ ：自己存活的情况下消灭所有的反猪。
忠猪 / $\texttt{ZP}$ ：不惜一切保护主猪，胜利条件与主猪相同。
反猪 / $\texttt{FP}$ ：杀死主猪。

游戏过程

游戏开始时，每个玩家手里都会有 $4$ 张牌，且体力上限和初始体力都是 $4$ 。

开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从 $1 , 2, 3 \ldots n , 1 \ldots$ 的顺序）依次行动。

每个玩家自己的回合可以分为 2 个阶段：

摸牌阶段：从牌堆顶部摸 $2$ 张牌，依次放到手牌的最右边；
出牌阶段：你可以使用任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。当然，要满足如下规则：
1. 如果没有猪哥连弩，每个出牌阶段只能使用 $1$ 次「杀」来攻击；
2. 任何牌被使用后被弃置（武器是装备上）；被弃置的牌以后都不能再用，即与游戏无关。

各种牌介绍

每张手牌用 $1$ 个字母表示，字母代表牌的种类。

基本牌

『桃 / $\texttt{P}$ 』在自己的回合内，如果自己的体力值不等于体力上限，那么使用 $1$ 个桃可以为自己补充 $1$ 点体力，否则不能使用桃；桃只能对自己使用；在自己的回合外，如果自己的体力变为 $0$ 或者更低，那么也可以使用。
『杀 / $\texttt{K}$ 』在自己的回合内，对攻击范围内除自己以外的 $1$ 名角色使用。如果没有被『闪』抵消，则造成 $1$ 点伤害。无论有无武器，杀的攻击范围都是 $1$ 。
『闪 / $\texttt{D}$ 』当你受到杀的攻击时，可以弃置 $1$ 张闪来抵消杀的效果。

锦囊牌

『决斗 / $\texttt{F}$ 』出牌阶段，对除自己以外任意 $1$ 名角色使用，由目标角色先开始，自己和目标角色轮流弃置 $1$ 张杀，首先没有杀可弃的一方受到 $1$ 点伤害，另一方视为此伤害的来源。
『南猪入侵 / $\texttt{N}$ 』出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置 $1$ 张杀，否则受到 $1$ 点伤害。
『万箭齐发 / $\texttt{W}$ 』和南猪入侵类似，不过要弃置的不是杀而是闪。
『无懈可击 / $\texttt{J}$ 』在目标锦囊生效前抵消其效果。每次有 $1$ 张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会；效果：用于决斗时，决斗无效并弃置；用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对 $1$ 个角色产生效果）；用于无懈可击时，成为目标的无懈可击被无效。

装备牌

『猪哥连弩 / $\texttt{Z}$ 』武器，攻击范围 $1$ ，出牌阶段你可以使用任意张杀; 同一时刻最多只能装 $1$ 把武器；如果先前已经有了 $1$ 把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器。

特殊事件及概念解释

伤害来源：杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪，决斗的伤害来源如上；
距离：两只猪的距离定义为沿着逆时针方向间隔的猪数 $+1$ 。即初始时 $1$ 和 $2$ 的距离为 $1$ ，但是 $2$ 和 $1$ 的距离就是 $n-1$ 。注意一个角色的死亡会导致一些猪距离的改变；
玩家死亡：如果该玩家的体力降到 $0$ 或者更低，并且自己手中没有足够的桃使得自己的体力值回到 $1$ ，那么就死亡了，死亡后所有的牌（装备区，手牌区）被弃置；
奖励与惩罚：反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸 $3$ 张牌。忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置。

注意：一旦达成胜利条件，游戏立刻结束，因此即使会摸 $3$ 张牌或者还有牌可以用也不用执行了。

现在，我们已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏，你需要做的就是告诉小猪 iPig 最后的结果。

几种行为

献殷勤：使用无懈可击挡下南猪入侵、万箭齐发、决斗；使用无懈可击抵消表敌意；
表敌意：对某个角色使用杀、决斗；使用无懈可击抵消献殷勤；
跳忠：即通过行动表示自己是忠猪。跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意；
跳反：即通过行动表示自己是反猪。跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤。

注意：主猪的身份一开始就公开了；忠猪不会跳反，反猪也不会跳忠；不管是忠猪还是反猪，能够跳必然跳。

行动准则

共性

每个角色如果手里有桃且生命值未满，那么必然吃掉；
有南猪入侵、万箭齐发，必然使用；有装备必然装上；
受到杀时，有闪必然弃置；
响应南猪入侵或者万箭齐发时候，有杀 / 闪必然弃置；
不会对未表明身份的猪献殷勤（包括自己）。

特性

主猪：
- 主猪会认为「没有跳身份，且用南猪入侵 / 万箭齐发对自己造成伤害的猪」是类反猪（没伤害到不算，注意类反猪并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪；
- 对于每种表敌意的方式，对逆时针方向能够执行到的第一只类反猪或者已跳反猪表；如果没有，那么就不表敌意；
- 决斗时会不遗余力弃置杀；
- 如果能对已经跳忠的猪或自己献殷勤，那么一定献；如果能够对已经跳反的猪表敌意，那么一定表。
忠猪：
- 对于每种表敌意的方式，对「逆时针方向能够执行到的第一只已经跳反的猪」表，如果没有，那么就不表敌意；
- 决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀；
- 如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献。
反猪：
- 对于每种表敌意的方式，如果有机会则对主猪表，否则，对「逆时针方向能够执行到的第一只已经跳忠的猪」表，如果没有，那么就不表敌意；
- 决斗时会不遗余力弃置杀；
- 如果有机会对已经跳反的猪献殷勤，那么一定献。

限于 iPig 只会用 P++ 语言写 A + B，他请你用 Pigcal (Pascal)、P (C) 或 P++ (C++) 语言来帮他预测最后的结果。

输入格式

输入文件第一行包含两个正整数 $n$ $(2 \leqslant n \leqslant 10)$ 和 $m$ $(m \leqslant 2000)$ ，分别代表玩家数和牌堆中牌的数量。数据保证牌的数量够用。

接下来 $n$ 行，每行 $5$ 个字符串，依次表示对第 $i$ 只猪的角色和初始 $4$ 张手牌描述。编号为 $1$ 的肯定是主猪。

再接下来一行，一共 $m$ 个字符串，按照从牌堆顶部到牌堆底部的顺序描述每张牌。

注意：所有的相邻的两个字符串都严格用 $1$ 个空格隔开，行尾没有多余空格。

输出格式

输出数据第一行包含一个字符串代表游戏结果。如果是主猪胜利，那么输出 $\texttt{MP}$ ，否则输出 $\texttt{FP}$ 。数据保证游戏总会结束。

接下来 $n$ 行，第 $i$ 行是对第 $i$ 只猪的手牌描述（注意只需要输出手牌），按照手牌从左往右的顺序输出，相邻两张牌用 $1$ 个空格隔开，行末尾没有多余空格。如果这只猪已阵亡，那么只要输出 $\texttt{DEAD}$ 即可。

注意：如果要输出手牌而没有手牌的话，那么只需输出 $1$ 个空行。

由于数据问题，若牌堆已空，按照每次抽牌抽到的都是最后一张。

输入输出样例

输入样例 #1

3 10
MP D D F F
ZP N N N D
FP J J J J
F F D D J J F F K D

输出样例 #1

FP
DEAD
DEAD
J J J J J J D

说明/提示

样例解释

第一回合：

主猪没有目标可以表敌意；
接下来忠猪使用了 $3$ 张南猪入侵，主猪掉了 $3$ 点体力，并认为该角色为类反猪， $3$ 号角色尽管手里有无懈可击，但是因为自己未表明身份，所以同样不能对自己用，乖乖掉 $3$ 点体力；

下一回合：

反猪无牌可出；
接下来主猪对着类反猪爆发，使用 $4$ 张决斗，忠猪死亡，结果主猪弃掉所有牌；
接下来反猪摸到 $1$ 张杀直接杀死主猪获胜。

子任务

一共 $20$ 组测试数据，每个点 $5$ 分。

$10\%$ 的数据没有锦囊牌，另外 $20\%$ 的数据没有无懈可击。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P2482 [SDOI2010] 猪国杀——大模拟题解 Author: Yuyi 一、先理解题意：这不是博弈，而是确定性模拟这道题看起来像一局复杂的卡牌游戏，但题目已经规定了每只猪在任何情况下的行动准则，因此我们不需要搜索最优策略，也不需要做博弈论。我们真正要做的是：按照题目给定的优先级，完整、准确地重放整局游戏，直到一方满足胜利条件。游戏中的每一个…

点击展开完整题解点击收起题解

2026年8月9日 22:34

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[1] = 1;

注意，类反猪并不是真的跳反，它只代表主猪的怀疑。把它统一存在 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] 负责快速判断某种牌是否存在，例如受到「杀」时，只需判断：

if (cnt[q][3])

二者始终满足不变量

cnt[i][c] = \left|\left\{k\mid cd[i][k]=c\right\}\right|.

因此，每次摸牌、用牌和弃光手牌时，都必须同步修改这两个结构。

原代码开头还有一些竞赛模板中的通用定义：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\sim8$ 的编号
`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=\sum_{i:sf[i]=3\ \land\ alive[i]} bld[i].

每当反猪受到一点伤害，就令 f_bld--；每当反猪吃桃，就令 f_bld++。

由于每次伤害都是 $1$ 点，而且体力降到 $0$ 后会立刻求桃或死亡，所以每只活反猪的体力一定为正。于是：

f\_bld=0 \iff \text{所有反猪均已死亡}.

这样便可以在反猪死亡后用 $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\to2\to\cdots\to n\to1\to\cdots

死亡的猪会被跳过。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] || !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] 中记录装备状态。

再次装备时旧武器被替换，但两把武器效果相同，所以仍然只需令

ak[i] = true;

即可。

八、全题最难点：无懈可击链

定义：

bool wx(int p, int q, bool f)

三个参数分别表示：

p：原锦囊当前要作用的目标；
q：本轮从哪只猪开始询问，初始时是锦囊使用者，递归时是上一张无懈的使用者；
f：当前打出的无懈属于献殷勤还是表敌意。

其中：

f == true：要抵消锦囊或上一层敌意无懈，相当于对目标献殷勤；
f == false：要抵消上一层献殷勤无懈，相当于对目标表敌意。

1. 哪些猪愿意献殷勤

无懈使用者	愿意保护的目标
主猪、忠猪	主猪或已经跳忠的猪
反猪	已经跳反的猪

未跳身份的猪不能被献殷勤，包括使用者自己。

2. 哪些猪愿意表敌意

无懈使用者	愿意敌对的目标
主猪	跳反猪或类反猪
忠猪	跳反猪
反猪	主猪或跳忠猪

3. 为什么递归返回取反

找到第一只必须使用无懈的猪 $i$ 后：

用掉一张 J；
让它跳明身份；
从 $i$ 开始询问，是否还有猪使用下一张无懈；
下一层行为的性质由献殷勤变为表敌意，或由表敌意变为献殷勤。

因此代码是：

return !wx(p, i, !f);

如果后面无人再出无懈，递归返回 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\bigl(E(H+n)\bigr).

空间复杂度为：

O(nH+m).

本题中 $n\le 10$ 、初始牌堆大小 $m\le 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]; //身份{主,忠,反}->{1,2,3}
int cnt[11][9]; //表示i人j牌有多少
//P-桃 K-杀 D-闪 F-决斗 N-南蛮 W-万箭 J-无懈 Z-连弩
//1-P 2-K 3-D 4-F 5-N 6-W 7-J 8-Z
int j[11]; //所跳身份{无,忠,反,类反}->{0,1,2,3}
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) //使用牌 {使用者,牌编号}
{
    // cout << "a" << cid << " " << cnt[p][cid] << endl;
    cnt[p][cid] --;
    rep(i,0,(int)cd[p].size()-1) if(cd[p][i] == cid)
    {
        cd[p].erase(cd[p].begin() + i);
        // cout << p << " " << cid << " " << j[p] << " " << bld[p] << " " << cd[p].size() << " " << alive[p] << endl;
        break;
    } 
}
void game_end(bool f) //游戏结束 胜利方(0主忠,1反贼)
{
    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) //判断攻击 {使用者,牌(0杀,1决斗)} 返回可攻击玩家
{
    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) //决斗 {使用者,被锁定者}
{
    // cout << j[2] << endl;
    if(wx(q,p,1)) return;
    if(sf[p] == 1 && sf[q] == 2)
    {
        hurt(q,p);
        // cout << attack(p,1) << " ";
        // rep(i,0,cd[p].size()) cout << cd[p][i] << " ";
        // cout << endl;
        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;
//	freopen("mul.in","r",stdin);
//	freopen("mul.out","w",stdout);
//	read(T);
	while (T--) solve();
	return 0;
}

十七、按这个顺序一步一步写到 AC

如果自己重新实现，建议按以下顺序逐层调试：

先完成牌编号、输入、手牌顺序和 cnt 同步维护；
完成摸牌、末牌复用、桃与装备；
完成环形座位和「杀」的距离 $1$ ；
完成身份状态、跳忠、跳反和类反；
完成伤害、濒死吃桃、死亡清牌、奖励惩罚和立即判胜；
完成决斗，并单独处理忠猪面对主猪不出杀；
完成南猪入侵和万箭齐发的逐目标结算；
最后实现无懈递归，并检查奇偶张无懈的结果；
接入“从左到右找第一张可用牌，用后重新扫描”的出牌循环；
用题目样例检查输出，再针对上面的十二个易错点逐项造小数据。

这道题能否 AC，主要取决于状态是否分清、事件顺序是否严格，而不是使用了多高级的算法。

讨论

2 条讨论

登录后即可使用 Markdown 发起讨论和回复。

abcd2222Lv.1

2026年8月10日 02:18

这道题我认为非常有意义

回复 1