题解归档 - P2482

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：P2482
• 本地来源：problems/P2482/idea.md
• 原始标题：P2482 猪国杀

思路

P2482 猪国杀

大模拟，核心是把“真实身份”和“当前公开身份”分开：

• role 是真实身份：MP / ZP / FP。
• seen 是公开阵营：未知 / 跳忠 / 跳反，主猪初始视为跳忠。
• suspect 是主猪眼里的“类反猪”：隐藏身份者用 N/W 实际伤害主猪后标记；一旦跳身份就清掉。

出牌阶段不能只线性扫一次。每次使用后都要从左到右重新寻找“当前最左可用牌”，因为装备连弩、摸奖励、主猪杀忠惩罚、死亡都会改变后续可用性。

无懈可击用递归奇偶链：

1. 对某个锦囊即将作用到 target 时，从锦囊使用者开始找第一张愿意“献殷勤”的 J。
2. 若有人出了 J，这个 J 又可以被敌对 J 抵消，于是递归查找相反立场。
3. 当前 J 是否生效等于“没有被下一层抵消”。

死亡处理顺序：

1. 掉血后先自动吃桃救到 hp >= 1。
2. 救不回则死亡，弃手牌和装备。
3. 立即检查胜利；若已胜利，不再执行摸三张或主猪弃牌惩罚。
4. 否则反猪死亡给伤害来源摸三张；忠猪被主猪杀死则主猪弃所有手牌和装备。

复杂度主要来自手牌扫描和无懈递归。n <= 10, m <= 2000，直接 vector<char> 维护手牌足够。

代码

来源：problems/P2482/solution.cpp

#include <bits/stdc++.h>
using namespace std;

struct Player {
    string role;
    int hp = 4;
    bool alive = true;
    bool weapon = false;
    vector<char> hand;
    int seen = 0;        // 0 unknown, 1 loyal side, -1 rebel side
    bool suspect = false; // only used by MP: damaged MP by N/W while hidden
};

int n, m;
vector<Player> pig;
vector<char> deck;
int deck_pos;
int rebel_alive;
bool finished;
string winner;

char draw_card() {
    if (deck_pos < (int)deck.size()) {
        return deck[deck_pos++];
    }
    return deck.back();
}

void draw_cards(int u, int cnt) {
    while (cnt--) {
        pig[u].hand.push_back(draw_card());
    }
}

int next_alive(int u) {
    int v = u;
    do {
        v = (v + 1) % n;
    } while (!pig[v].alive);
    return v;
}

bool has_card(int u, char c) {
    for (char x : pig[u].hand) {
        if (x == c) {
            return true;
        }
    }
    return false;
}

bool erase_first(int u, char c) {
    auto &h = pig[u].hand;
    for (auto it = h.begin(); it != h.end(); ++it) {
        if (*it == c) {
            h.erase(it);
            return true;
        }
    }
    return false;
}

void check_winner() {
    if (!pig[0].alive) {
        finished = true;
        winner = "FP";
    } else if (rebel_alive == 0) {
        finished = true;
        winner = "MP";
    }
}

void reveal_loyal(int u) {
    if (u == 0 || pig[u].role == "ZP") {
        pig[u].seen = 1;
        pig[u].suspect = false;
    }
}

void reveal_rebel(int u) {
    if (pig[u].role == "FP") {
        pig[u].seen = -1;
        pig[u].suspect = false;
    }
}

void express_kindness(int u, int target) {
    if (pig[u].role == "ZP" && (target == 0 || pig[target].seen == 1)) {
        reveal_loyal(u);
    } else if (pig[u].role == "FP" && pig[target].seen == -1) {
        reveal_rebel(u);
    }
}

void express_hostility(int u, int target) {
    if (pig[u].role == "ZP" && pig[target].seen == -1) {
        reveal_loyal(u);
    } else if (pig[u].role == "FP" && (target == 0 || pig[target].seen == 1)) {
        reveal_rebel(u);
    }
}

bool can_kind(int u, int target) {
    if (!has_card(u, 'J')) {
        return false;
    }
    if (pig[u].role == "MP") {
        return target == 0 || pig[target].seen == 1;
    }
    if (pig[u].role == "ZP") {
        return target == 0 || pig[target].seen == 1;
    }
    return pig[target].seen == -1;
}

bool can_hostile(int u, int target) {
    if (!has_card(u, 'J')) {
        return false;
    }
    if (pig[u].role == "MP") {
        return pig[target].seen == -1;
    }
    if (pig[u].role == "ZP") {
        return pig[target].seen == -1;
    }
    return target == 0 || pig[target].seen == 1;
}

bool nullify(int source, int target, bool kind) {
    for (int step = 0; step < n; ++step) {
        int u = (source + step) % n;
        if (!pig[u].alive) {
            continue;
        }
        bool ok = kind ? can_kind(u, target) : can_hostile(u, target);
        if (!ok) {
            continue;
        }
        erase_first(u, 'J');
        if (kind) {
            express_kindness(u, target);
        } else {
            express_hostility(u, target);
        }
        bool countered = nullify(u, target, !kind);
        return !countered;
    }
    return false;
}

void try_save_with_peach(int u) {
    while (pig[u].hp <= 0 && erase_first(u, 'P')) {
        ++pig[u].hp;
    }
}

void damage(int target, int source) {
    if (finished || !pig[target].alive) {
        return;
    }
    --pig[target].hp;
    if (pig[target].hp <= 0) {
        try_save_with_peach(target);
    }
    if (pig[target].hp > 0) {
        return;
    }

    pig[target].alive = false;
    pig[target].weapon = false;
    pig[target].hand.clear();
    if (pig[target].role == "FP") {
        --rebel_alive;
    }

    check_winner();
    if (finished) {
        return;
    }

    if (pig[target].role == "FP" && source != -1 && pig[source].alive) {
        draw_cards(source, 3);
    }
    if (pig[target].role == "ZP" && source == 0 && pig[0].alive) {
        pig[0].hand.clear();
        pig[0].weapon = false;
    }
}

bool duel_discard_kill(int u, int opponent) {
    if (pig[u].role == "ZP" && opponent == 0) {
        return false;
    }
    return erase_first(u, 'K');
}

void slash(int source, int target) {
    express_hostility(source, target);
    if (erase_first(target, 'D')) {
        return;
    }
    damage(target, source);
}

void duel(int source, int target) {
    express_hostility(source, target);
    if (nullify(source, target, true)) {
        return;
    }

    int cur = target;
    int other = source;
    while (!finished) {
        if (duel_discard_kill(cur, other)) {
            swap(cur, other);
        } else {
            damage(cur, other);
            return;
        }
    }
}

void aoe(int source, char need) {
    int u = next_alive(source);
    while (u != source && !finished) {
        int cur = u;
        u = next_alive(u);

        if (nullify(source, cur, true)) {
            continue;
        }
        if (!erase_first(cur, need)) {
            damage(cur, source);
            if (!finished && cur == 0 && pig[source].seen == 0) {
                pig[source].suspect = true;
            }
        }
    }
}

bool attackable_by_mp(int target) {
    return pig[target].seen == -1 || (pig[target].seen == 0 && pig[target].suspect);
}

int first_target(int source, function<bool(int)> ok) {
    int u = next_alive(source);
    while (u != source) {
        if (ok(u)) {
            return u;
        }
        u = next_alive(u);
    }
    return -1;
}

int kill_target(int source) {
    int target = next_alive(source);
    if (target == source) {
        return -1;
    }
    if (pig[source].role == "MP") {
        return attackable_by_mp(target) ? target : -1;
    }
    if (pig[source].role == "ZP") {
        return pig[target].seen == -1 ? target : -1;
    }
    return (target == 0 || pig[target].seen == 1) ? target : -1;
}

int duel_target(int source) {
    if (pig[source].role == "MP") {
        return first_target(source, [](int u) {
            return attackable_by_mp(u);
        });
    }
    if (pig[source].role == "ZP") {
        return first_target(source, [](int u) {
            return pig[u].seen == -1;
        });
    }
    return pig[0].alive ? 0 : -1;
}

bool try_use_card(int u, int pos, bool &used_kill) {
    char c = pig[u].hand[pos];

    if (c == 'P') {
        if (pig[u].hp == 4) {
            return false;
        }
        pig[u].hand.erase(pig[u].hand.begin() + pos);
        ++pig[u].hp;
        return true;
    }

    if (c == 'K') {
        if (!pig[u].weapon && used_kill) {
            return false;
        }
        int target = kill_target(u);
        if (target == -1) {
            return false;
        }
        pig[u].hand.erase(pig[u].hand.begin() + pos);
        used_kill = true;
        slash(u, target);
        return true;
    }

    if (c == 'F') {
        int target = duel_target(u);
        if (target == -1) {
            return false;
        }
        pig[u].hand.erase(pig[u].hand.begin() + pos);
        duel(u, target);
        return true;
    }

    if (c == 'N') {
        pig[u].hand.erase(pig[u].hand.begin() + pos);
        aoe(u, 'K');
        return true;
    }

    if (c == 'W') {
        pig[u].hand.erase(pig[u].hand.begin() + pos);
        aoe(u, 'D');
        return true;
    }

    if (c == 'Z') {
        pig[u].hand.erase(pig[u].hand.begin() + pos);
        pig[u].weapon = true;
        return true;
    }

    return false;
}

void play_turn(int u) {
    draw_cards(u, 2);

    bool used_kill = false;
    while (!finished && pig[u].alive) {
        bool used = false;
        for (int i = 0; i < (int)pig[u].hand.size(); ++i) {
            if (try_use_card(u, i, used_kill)) {
                used = true;
                break;
            }
        }
        if (!used) {
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    pig.assign(n, Player());
    deck.clear();
    deck.reserve(m);
    deck_pos = 0;
    rebel_alive = 0;
    finished = false;

    for (int i = 0; i < n; ++i) {
        cin >> pig[i].role;
        if (pig[i].role == "FP") {
            ++rebel_alive;
        }
        for (int j = 0; j < 4; ++j) {
            string s;
            cin >> s;
            pig[i].hand.push_back(s[0]);
        }
    }
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        deck.push_back(s[0]);
    }

    pig[0].seen = 1;
    check_winner();

    int cur = 0;
    while (!finished) {
        if (pig[cur].alive) {
            play_turn(cur);
        }
        if (!finished) {
            cur = next_alive(cur);
        }
    }

    cout << winner << '\n';
    for (int i = 0; i < n; ++i) {
        if (!pig[i].alive) {
            cout << "DEAD\n";
            continue;
        }
        for (int j = 0; j < (int)pig[i].hand.size(); ++j) {
            if (j) {
                cout << ' ';
            }
            cout << pig[i].hand[j];
        }
        cout << '\n';
    }
    return 0;
}