题解：P7147 [THUPC2021 初赛] 麻将模拟器

myster1ous · 2024-11-26 16:14:30 · 题解

题目描述

细节非常多，大意就是给定一个麻将规则，给定牌山，让你模拟四个人机的游戏过程。

默认读者已经知道吃、碰、和牌的定义。

一些细节的规则：

• 没有杠，这为我们大大简化了题目；
• 没有特殊的牌型，所有和牌都符合最基本的麻将规则；
• 增加了跳过、翻转和双重回合三种特殊牌；
• 特殊牌不可碰，更不能吃，有特殊牌的情况下无法和牌；
• 没有一炮双响，如果两个人同时荣和，只有从上一名出牌玩家开始，沿回合进行顺序的第一名能荣和的玩家才能荣和。

题面定义了和牌距离，这个定义是所有人机操作的基础：

• 如果手牌和副露共有 13 张，那么和牌距离就是最小的 x 使得存在一种在手牌中加入 x 张牌，去掉 x - 1 张牌后就能和牌且每种牌不超过四个（不包括副露）的方案。
• 如果手牌和副露共有 13 张，那么和牌距离就是最小的 x 使得存在一种在手牌中加入 x 张牌，去掉 x 张牌后就能和牌且每种牌不超过四个（不包括副露）的方案。

人机们的吃、碰都只会在和牌距离严格减小的时候进行。\ 人机们每回合出的牌都是能使和牌距离减少最多的牌。

人机出牌的小细节：

• 有特殊牌先打特殊牌，按照跳过 PASS、反转 REVERSE、双重回合 DOUBLE 的顺序打，PASS 一定指定下家。
• 如果有多重吃法都可以使得和牌距离严格减小，那么只会优先选取数字较大的吃法。
• 如果既能吃，也能碰，那么优先碰，如果碰不能使和牌距离减小，再考虑吃。
• 如果每回合出牌的时候有多重方案都可以使和牌距离减小得最多，那么以红中 Z、发财 F、白板 B、北风 N、西风 W、南风 S、东风 E、九条 9S 到一条 1S、九饼 9P 到一饼 1P、九万 9M 到一万 1M 的优先顺序出牌。

题目分析

首先，这道题的细节非常的多，我们可以考虑分而治之，把庞大的题目分解成几个小的部分逐个击破。

我们先将整个流程分为三步：

• 读入牌山。
• 分发初始手牌。
• 开始游戏。

其中前两个都没有任何细节，而第三个还是有些复杂，因此我们再将第三个步骤分解：

• 循环进入每个人的回合
• 摸牌。
• 如果有特殊牌，优先打出。
• 否则，对打出每一张牌的情况都计算和牌距离，选择最合适的那一张打出。
• 判断荣和。
• 判断碰。注意荣和优先级大于碰，碰优先级大于吃。
• 判断吃。注意吃只能下家吃本家的牌，本家只能吃上家的牌。

这样整个问题就被我们成功的分解成了很多个小的步骤，可是还剩下一个最大的问题：

如何计算和牌距离？

这道题的重要难点就是这点，使用动态规划就可以解决。

我们定义 dp[i][j][k][x][y]：

• 第一维 i(0 \leqslant i < 34) 表示当前处理到了第 i 种牌；
• 第二维 j(0 \leqslant j \leqslant 4) 表示当前已经有了 j 个面子（刻字和顺子）；
• 第三维 k(0 \leqslant k \leqslant 1) 表示当前是否已经有雀头（对子）；
• 第四维 x(0 \leqslant x \leqslant 2) 表示当前已经有 x 个已经组成形如 3M 4M 的半顺子；
• 第五维 y(0 \leqslant y \leqslant 2) 表示当前已经有 y 个单牌，正准备形成“半顺子”。

注：因为如果一个牌有三个相同的顺子那么不如直接定义为三个刻子，所以 x,y 最高到 2（一杯口）。

注：同时每一个 x,y,j 都是独立的面子，所以 x+y+j \leqslant 4。

初始条件：dp[0][0][0][0][0] = 0。

对于状态转移，我们枚举 c 表示对于这第 i 种牌我们取多少个，c 必须至少为 x + y 因为这些 x + y 单牌和半顺子都需要靠第 i 种牌来形成下一阶段的顺子，而这些都是从第 i - 1 种牌和（对于半顺子）第 i - 2 种牌组合而成的。

然后如果还有空余的第 i 种牌，那么就考虑让它们成为雀头、刻子。

转移的代价就是 c 减去当前的手牌中第 i 种牌的个数（非负，和 0 取 \max）。

伪代码：

有了这个函数之后，整个过程中还剩下一个略微难的步骤：判断吃牌，不难发现吃牌一共就三种情况：

• 形如打出 4M，被 3M ~ 5M 吃。
• 形如打出 4M，被 2M 3M ~ 吃。
• 形如打出 4M，被 ~ 5M 6M 吃。

由于吃优先吃大的，所以第三种优先于第一种，第一种优先于第二种。

判断吃的伪代码：

剩下的都不太难，直接上完整代码：

#include <bits/stdc++.h>
#define int long long
std::deque<std::string> allcard({
    "1M", "2M", "3M", "4M", "5M", "6M", "7M", "8M", "9M",
    "1P", "2P", "3P", "4P", "5P", "6P", "7P", "8P", "9P",
    "1S", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S",
    "E", "S", "W", "N", "B", "F", "Z", "PASS", "REVERSE", "DOUBLE"
});
int mappings(std::string card) {
    for (int i = 0; i < allcard.size(); i++)
        if (allcard[i] == card) return i; return -1;
}
bool compare(std::string a, std::string b) { return mappings(a) < mappings(b); }
struct Simulator {
    struct Cardheap {
        Simulator* simulator;
        std::deque<std::string> deque;
        Cardheap(Simulator* sim) {deque.clear(); simulator = sim; }
        void addcard(std::string card) {deque.push_back(card); }
        std::string getcard() {
            if (deque.empty()) {
                std::cout << "DRAW\n";
                std::exit(0);
            }
            std::string ret = deque.front();
            deque.pop_front(); return ret;
        }
    } *heap;
    struct Player {
        struct Handcard {
            std::deque<std::string> hand;
            std::deque<std::tuple<std::string, std::string, std::string>> showns;
            Handcard() {hand.clear(); }
            void sort() { std::sort(hand.begin(), hand.end(), compare); }
            int windistance() {
                static int dp[40][5][2][5][5];
                memset(dp, 0x3f, sizeof(dp));
                dp[0][0][0][0][0] = 0;
                int xxx = hand.size() / 3;
                for (int i = 0; i < 34; i++) {
                    int has = 0;
                    for (auto j : hand) has += (mappings(j) == i);
                    for (int j = 0; j <= xxx; j++)
                        for (int k = 0; k < 2; k++)
                            for (int x = 0; x <= 2 && x + j <= xxx; x++) {
                                for (int y = 0; y <= 2 && x + j + y <= xxx; y++) {
                                    if (dp[i][j][k][x][y] <= 20)
                                        for (int choose = y + x; choose <= 4; choose++) {
                                            int l = choose - y - x;
                                            int nw = dp[i][j][k][x][y] + std::max(0ll, choose - has);
                                            if (l <= 2) dp[i + 1][j + x][k][y][l] = std::min(dp[i + 1][j + x][k][y][l], nw);
                                            if (l >= 2 && !k) dp[i + 1][j + x][1][y][l - 2] = std::min(dp[i + 1][j + x][1][y][l - 2], nw);
                                            if (l >= 3 && j + x < xxx) dp[i + 1][j + x + 1][k][y][l - 3] = std::min(dp[i + 1][j + x + 1][k][y][l - 3], nw);
                                        }
                                    if ((i) % 9 == 0 || (i) >= 27) break;
                                }
                                if ((i) % 9 == 0 || (i) >= 27) break;
                            }
                }
                return dp[34][xxx][1][0][0];
            }
            Handcard* outcard(std::string card) {
                Handcard *news = new Handcard();
                news->showns = showns;
                bool shown = false;
                for (auto i : hand)
                    if (i == card && !shown) shown = true;
                    else news->hand.push_back(i);
                return news; 
            }
            bool have(std::string card) {
                for (auto i : hand) if (i == card) return true;
                return false;
            }
            int count(std::string card) {
                int cnt = 0;
                for (auto i : hand) if (i == card) cnt += 1;
                return cnt;
            }
            // void printout() {
                // sort();
                // for (auto i : hand) std::cout << i << " "; std::cout << " | ";
                // for (auto [u, v, w] : showns) std::cout << "[" << u << ", " << v << ", " << w << "] ";
                // std::cout << windistance() << " (" << hand.size() << ")" << std::endl;
            // }
        } *handcard; 
        bool passed; int id;
        Simulator* simulator;
        Player(Simulator *sim, int idx): passed(0), simulator(sim), id(idx)
            { handcard = new Handcard(); }
        void getcard(std::string card) {
            handcard->hand.push_back(card); 
            std::cout << char('A' + id) << " IN " << card << std::endl;
        }    
        // void printout() {
            // handcard->sort();
            // std::cout << "Player " << char('A' + id) << ": ";
            // handcard->printout();
        // }
        bool canron(std::string card) {
            handcard->hand.push_back(card);
            if (handcard->windistance() == 0) {
                handcard->sort()/*handcard->printout()*/;
                return true;
            }
            handcard->hand.pop_back(); 
            return false;
        }
        bool canpong(std::string card) {
            if (handcard->count(card) >= 2) 
                if (handcard->outcard(card)->outcard(card)->windistance() < handcard->windistance()) {
                    handcard = handcard->outcard(card)->outcard(card);
                    handcard->showns.push_back(std::make_tuple(card, card, card));
                    simulator->now = ((id - simulator->dir) % 4 + 4) % 4; return true;
                }
            return false;
        }
        void trychow(std::string card) {
            if (mappings(card) >= 27) return;
            int map = mappings(card) % 9 + 1;
            char type = card[1];
            std::deque<std::string> num;
            num.push_back("114514");
            for (int i = 1; i <= 9; i++)
                num.push_back(std::to_string(i) + (type));
            if (map != 8 && map != 9)
                if (handcard->outcard(num[map + 2])->outcard(num[map + 1])->windistance() < handcard->windistance()) {
                    handcard = handcard->outcard(num[map + 1])->outcard(num[map + 2]);
                    handcard->showns.push_back(std::make_tuple(num[map + 2], num[map + 1], num[map]));
                    std::cout << char('A' + id) << " CHOW " << num[map] << " " << num[map + 1] << " " << num[map + 2] << "\n";
                    simulator->now = ((id - simulator->dir) % 4 + 4) % 4; 
                }
            if (map != 1 && map != 9)
                if (handcard->outcard(num[map - 1])->outcard(num[map + 1])->windistance() < handcard->windistance()) {
                    handcard = handcard->outcard(num[map - 1])->outcard(num[map + 1]);
                    handcard->showns.push_back(std::make_tuple(num[map - 1], num[map], num[map + 1]));
                    std::cout << char('A' + id) << " CHOW " << num[map - 1] << " " << num[map] << " " << num[map + 1] << "\n";
                    simulator->now = ((id - simulator->dir) % 4 + 4) % 4; 
                }
            if (map != 1 && map != 2)
                if (handcard->outcard(num[map - 2])->outcard(num[map - 1])->windistance() < handcard->windistance()) {
                    handcard = handcard->outcard(num[map - 1])->outcard(num[map - 2]);
                    handcard->showns.push_back(std::make_tuple(num[map - 2], num[map - 1], num[map]));
                    std::cout << char('A' + id) << " CHOW " << num[map - 2] << " " << num[map - 1] << " " << num[map] << "\n";
                    simulator->now = ((id - simulator->dir) % 4 + 4) % 4; 
                } 
        }
        void startround() {
            if (passed) return passed = false, void();
            if (handcard->hand.size() % 3 == 1) getcard(simulator->heap->getcard());
            // for (int i = 0; i < 4; i++) simulator->player[i]->printout();
            if (handcard->windistance() == 0) {
                std::cout << char('A' + id) << " SELFDRAWN\n";
                std::cout << char('A' + id) << " WIN\n";
                std::exit(0); 
            }
            handcard->sort();
            if (handcard->have("PASS")) {
                handcard = handcard->outcard("PASS");
                simulator->player[simulator->next()]->passed = true;
                std::cout << char('A' + id) << " OUT PASS " << char('A' + simulator->next()) << "\n"; 
            } else if (handcard->have("REVERSE")) {
                handcard = handcard->outcard("REVERSE");
                simulator->dir = -simulator->dir;
                std::cout << char('A' + id) << " OUT REVERSE\n";
            } else if (handcard->have("DOUBLE")) {
                handcard = handcard->outcard("DOUBLE");
                std::cout << char('A' + id) << " OUT DOUBLE\n";
                startround();
            } else {
                int mindistance = 114514;
                std::string mincard;
                for (auto i : handcard->hand) {
                    int wind = handcard->outcard(i)->windistance();
                    if (wind <= mindistance) {
                        mindistance = wind;
                        mincard = i;
                    } 
                }
                handcard = handcard->outcard(mincard);
                std::cout << char('A' + id) << " OUT " << mincard << "\n";
                for (int i = simulator->next(); i != id; i = ((i + simulator->dir) % 4 + 4) % 4)  
                    if (simulator->player[i]->canron(mincard)) {
                        std::cout << char('A' + i) << " RON\n";
                        std::cout << char('A' + i) << " WIN\n";
                        std::exit(0);
                    }
                bool ponged = false;
                for (int i = simulator->next(); i != id; i = ((i + simulator->dir) % 4 + 4) % 4)
                    if (simulator->player[i]->canpong(mincard)) 
                        std::cout << char('A' + i) << " PONG " << mincard << " " << mincard << " " << mincard << "\n", ponged = true;
                if (!ponged) simulator->player[simulator->next()]->trychow(mincard);
            }
        }
    } *player[4];
    int now, dir;
    int next() {return ((now + dir) % 4 + 4) % 4; }
    Simulator(): now(0), dir(0) {
        for (int j = 0; j < 4; j++) player[j] = new Player(this, j);
        heap = new Cardheap(this);
    }
    void inputheap() {
        for (int i = 1; i <= 148; i++) {
            std::string card;
            std::cin >> card;
            heap->addcard(card);
        }
    }
    void distributecard() {
        for (int i = 1; i <= 13; i++)   
            for (int j = 0; j < 4; j++)
                player[j]->getcard(heap->getcard());
    }
    void simulate() {
        dir = 1, now = 0;
        while (true) {
            player[now]->startround();
            now = next();
        }
    }
};
signed main() {
    Simulator* sim = new Simulator();
    sim->inputheap();
    sim->distributecard();
    sim->simulate();
    return 0;
}