洛谷P2482 [SDOI2010]猪国杀

28 August 2019 | duanyll | Tags: 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,打着也不费事。

// 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;
}