洛谷P2482 [SDOI2010] 猪国杀 题解

题目链接：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\%\)​ 的数据没有无懈可击。

---

题解

本题以超级长的题面和复杂的规则而臭名昭著。

实际上本题的规则和三国杀基本一致，除了部分牌（比如桃）。

那么实现的思路其实很简单。

先从最基础的杀、闪、桃开始实现，然后实现装备牌和锦囊牌。

不过本题作为一道 OI 题显然是不合格的，也许作为一道娱乐题更为合适。

时间复杂度 \(\mathcal{O}(\mathrm{ok})\)

代码：（基于参考文献[1]的实现）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const bool diff[3][3]={{0, 0, 1}, {0, 0, 1}, {1, 1, 0}};
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(15))
#define M ((int)(2e3 + 15))

int n, m, t, cnt;
queue<char> cards; int used[M];
class Pig
{
    public:
        char cards[M];
        int id, health = 4, len = 4, type, nxt, perf = 0;
        bool live = true, Zhuge = false;
} a[N];
void Debug()
{
    for(int w = 1; w <= n; w++)
    {
        cout << a[w].health << ' ';
        if(!a[w].live) cout << "DEAD\n";
        else {
            if(a[w].len > 0) cout << a[w].cards[1];
            for(int j = 2; j <= a[w].len; j++) cout << ' ' << a[w].cards[j];
            cout << '\n';
        }
    }
    cout << "--------------\n";
}
void output()
{
    cout << (a[1].live ? "MP" : "FP") << '\n';
    for(int i = 1; i <= n; i++)
    {
        if(!a[i].live) cout << "DEAD\n";
        else {
            if(a[i].len > 0) cout << a[i].cards[1];
            for(int j = 2; j <= a[i].len; j++) cout << ' ' << a[i].cards[j];
            cout << '\n';
        }
    }
    exit(0);
}
void change_link(int i)
{
    for(int pre = 1; pre <= n; pre++)
        if(a[pre].live && a[pre].nxt == i) { a[pre].nxt = a[i].nxt; break; }
    return;
}
bool enemy(Pig& now)
{
    auto& nxt = a[now.nxt];
    if(nxt.perf == 0) return 0;
    else if(nxt.perf == 1) return diff[now.type][nxt.type];
    else return now.type == 0;
}
int find(Pig& now, char ch)
{
    for(int i = 1; i <= now.len; i++)
        if(now.cards[i] == ch) return i;
    return 0;
}
void Modify(Pig& now, int l)
{
    for(int i = l; i < now.len; i++)
        now.cards[i] = now.cards[i + 1];
    --now.len;
}
bool respond_Shan(Pig& now)
{
    int p = find(now, 'D');
    if(p) Modify(now, p);
    return p;
}
void respond_Peach(Pig& now, Pig& user)
{
    // cout << "Wow" << '\n';
    if(&now == &user)
    {
        int p = 0;
        for(int i = 1; i <= now.len; i++)
            if(used[i] != t && now.cards[i] == 'P') { p = i; break; }
        if(p) { used[p] = t; ++now.health; }
        return;
    }
    int p = find(now, 'P'); if(p) { Modify(now, p); ++now.health; }
}
void lose_health(Pig& now, Pig& user)
{
    --now.health; // cout << now.type << ' ' << now.health << '\n';
    if(now.health < 1) respond_Peach(now, user);
}
void getcard(Pig& now)
{
    now.cards[++now.len] = cards.front();
    if(cards.size() > 1) cards.pop();
}
void pend(Pig& x, Pig& y)
{
    if(x.type == 0 && y.type == 1) {
        for(int i = 1; i <= x.len; i++) { used[i] = t, x.Zhuge = 0; }
    }
    else if(y.type == 2) { getcard(x); getcard(x); getcard(x); }
}
void Sha(Pig& now)
{
    auto& nxt = a[now.nxt];
    now.perf = 1;
    if(!respond_Shan(nxt))
    {
        lose_health(nxt, now);
        if(nxt.health < 1)
        {
            cnt -= (nxt.type == 2);
            nxt.live = false; change_link(now.nxt);
        }
        if(cnt == 0 || !a[1].live) return;
        if(nxt.health < 1) pend(now, nxt);
    }
}
int Aim(Pig& now)
{
    if(now.type == 2) return true;
    for(int p = now.nxt; p != now.id; p = a[p].nxt)
        if(a[p].live) {
            if((a[p].type == 2 && a[p].perf == 1) || (now.type == 0 && a[p].perf == 2)) return p;
        }
    return -1;
}
bool respond_Sha(Pig& now, Pig& user)
{
    if(&now == &user)
    {
        int p = 0;
        for(int i = 1; i <= now.len; i++)
            if(used[i] != t && now.cards[i] == 'K') { p = i; break; }
        if(p) { used[p] = t; }
        return p;
    }
    int p = find(now, 'K'); if(p) { Modify(now, p); }
    return p;
}
bool respond_Wuxie(Pig& now, Pig& user)
{
    if(now.id == user.id)
    {
        int p = 0;
        for(int i = 1; i <= now.len; i++)
            if(used[i] != t && now.cards[i] == 'J') { p = i; break; }
        if(p) { used[p] = t; }
        return p;
    }
    int p = find(now, 'J'); if(p) { Modify(now, p); }
    return p;
}
bool Wuxie(Pig& user, Pig& now, int aim, int type)
{
    bool res = type;
    for(int p = now.id; ; ) if(a[p].live)
    {
        if(!type)
        {
            if(!diff[a[p].type][a[aim].type])
                if(respond_Wuxie(a[p], user)) { 
                    a[p].perf = 1; return Wuxie(user, a[p], aim, 1 - type);
                }
        }else
        {
            if(diff[a[p].type][a[aim].type]) {
                if(respond_Wuxie(a[p], user)) {
                    a[p].perf = 1; return Wuxie(user, a[p], aim, 1 - type);
                }
            }
        }
        p = a[p].nxt; if(p == now.id) break;
    }
    return res;
}
void Juedou(Pig& now, int aim, Pig& user, int i)
{
    now.perf = 1;
    if(a[aim].perf == 1) {
        if(Wuxie(now, now, aim, 0)) return;
    }
    while(true)
    {
        if((now.type == 0 && a[aim].type == 1) || !respond_Sha(a[aim], user))
        {
            lose_health(a[aim], user);
            if(a[aim].health < 1)
            {
                cnt -= (a[aim].type == 2);
                a[aim].live = false; change_link(aim);
            }
            if(cnt == 0 || !a[1].live) return;
            if(a[aim].health < 1) pend(now, a[aim]);
            return;
        }
        if (!respond_Sha(now, user))
        {
            lose_health(now, user);
            if(now.health < 1)
            {
                cnt -= (now.type == 2);
                now.live = false; change_link(i);
            }
            if(cnt == 0 || !a[1].live) return;
            if(now.health < 1) pend(a[aim], now);
            return;
        }
    }
}
void Nanman(Pig& now)
{
    for(int p = now.nxt; p != now.id; p = a[p].nxt) if(a[p].live)
    {
        if(a[p].perf == 1) {
            if(Wuxie(now, now, p, 0)) continue;
        }
        if(!respond_Sha(a[p], now))
        {
            lose_health(a[p], now); if(p == 1 && now.perf == 0) now.perf = 2;
            if(a[p].health < 1)
            {
                cnt -= (a[p].type == 2);
                a[p].live = false; change_link(p);
            }
            if(cnt == 0 || !a[1].live) return;
            if(a[p].health < 1) pend(now, a[p]);
        }
    }
}
void Wanjian(Pig& now)
{
    for(int p = now.nxt; p != now.id; p = a[p].nxt) if(a[p].live)
    {
        if(a[p].perf == 1) {
            if(Wuxie(now, now, p, 0)) continue;
        }
        if(!respond_Shan(a[p]))
        {
            lose_health(a[p], now); if(p == 1 && now.perf == 0) now.perf = 2;
            if(a[p].health < 1)
            {
                cnt -= (a[p].type == 2);
                a[p].live = false; change_link(p);
            }
            if(cnt == 0 || !a[1].live) return;
            if(a[p].health < 1) pend(now, a[p]);
        }
    }
}
bool work(int i)
{
    auto& now = a[i]; static char tmp[M];
    getcard(now); getcard(now);
    memset(used, 0, sizeof(used));
    int use = 0, tot = 0, aim, ck = -1; bool sha = false;
    for(t = 1; ; t++)
    {
        use = 0; tot = 0;
        for(int l = 1; l <= now.len; l++)
        {
            if(used[l] == t) continue;
            char card = now.cards[l];
            // cout << card << '\n';
            switch(card)
            {
                case 'P':
                    if(now.health < 4) { 
                        ++now.health; used[l] = t; ++use; l = now.len;
                    }
                    break;
                case 'K':
                    // cout << enemy(now) << '\n';
                    if((!sha || now.Zhuge) && enemy(now)) {
                        Sha(now); used[l] = t; ++use; sha = true; l = now.len;
                    }
                    break;
                case 'F':
                    aim = Aim(now);
                    if(aim != -1) {
                        Juedou(now, aim, now, i); used[l] = t; ++use; l = now.len;
                    }
                    break;
                case 'N':
                    Nanman(now); used[l] = t; ++use; l = now.len;
                    break;
                case 'W':
                    Wanjian(now); used[l] = t; ++use; l = now.len;
                    break;
                case 'Z':
                    now.Zhuge = true; used[l] = t; ++use; l = now.len;
                    break;
                case 'D':
                    break;
                case 'J':
                    break;
                default:
                    cout << "Fxxking Great.\n"; break;
            }
            if(cnt == 0 || !a[1].live) { ck = 1; break; }
            if(!now.live) { ck = 0; break; }
        }
        for(int l = 1; l <= now.len; l++) 
            if(used[l] != t) tmp[++tot] = now.cards[l];
        for(int l = 1; l <= tot; l++) now.cards[l] = tmp[l];
        now.len = tot;
        if(!use && ck != 1) ck = 0;
        if(ck > -1) return ck;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        static char tmp[5]; cin >> tmp; a[i].id = i;
        if(tmp[0] == 'M') { a[i].type = 0; a[i].perf = 1; }
        else if(tmp[0] == 'Z') { a[i].type = 1; }
        else if(tmp[0] == 'F') { ++cnt, a[i].type = 2; }
        a[i].nxt = i % n + 1; 
        for(int j = 1; j <= 4; j++) cin >> tmp, a[i].cards[j] = tmp[0];
    }
    for(int i = 1; i <= m; i++) {
        static char tmp; cin >> tmp; cards.push(tmp);
    }
    for(int i = 1, ck = 0; !ck && cnt > 0; i = a[i].nxt)
        if(a[i].live) ck = work(i);
    output();
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/hfamqzbp

---

题外话：

精神状态良好。