[2016清华推研]麻将猜猜猜–简单游戏AI行为树模拟–顶级折磨题

我很喜欢我学弟去年的时候说过的一句话：

这题是真nm顶级折磨，不是一次次试错对着评测数据看错哪了，能一次直接拿下满分几乎是不可能的事情。

题意

两个人玩猜麻将的游戏（原型是达芬奇密码桌游），给定了两个最简单的AI行为树的模拟方式，以此模拟并输出最终局面。

具体的模拟流程给的很有限，只说了双方从左到右推算所有未知牌的最小值/从右往左推算所有未知牌的最大值。这部分直接可以看题面。

具体解析

那么我们在模拟的时候，需要记录以下内容：

• 当前自己抽到了什么
• 已经明牌的有哪些

在猜的时候，由于对称性，我们只以从右 往左推算所有未知牌的最大值为例（反过来是一样的）。

右面的牌要么是已经公开的牌，要么就是自己猜的最大值。那么如果当前牌的牌型比右边的小，那自己的数字一定严格小于右边的，反之则是不大于右边的。

但是这还没完，还需要注意：当前卡已经被猜过、且猜错的数字是不能重复猜的，此时只能比所有原先猜错的数字还要小。

根据这个我们就可以写出一版模拟出来了。此时可以获得 $92$ 分。

剩下 $8$ 分是差在哪里呢？

我对着自己其中错的一个数据点看了一下，大概的行为是这样的：

• 晨晨在第 $11$ 轮抽到了”三万”($3W$) （璐璐只知道抽到了万牌）猜了”三饼”($3B$)
• 小璐在第 $12$ 轮正常猜测
• 晨晨在第 $13$ 轮抽到了”三条”($3T$) （璐璐只知道抽到了条牌）猜了”二饼”($2B$)
• 小璐在第 $14$ 轮要猜的是晨晨手中的”四饼”($4B$)，正常的情况为：小璐猜对了四饼。

按照题目给的信息，如果仅推算双方手上手牌的值和自己猜过的值，在这一轮是推不出是三饼还是四饼的（因为四饼的后面跟着一个五万($5W$)） ，但是对方在猜过三饼之后没再抽到过饼牌，此时可以判断晨晨手上一定没有三饼的。

所以最后 $8$ 分在于，对方在没抽到某牌型前，对这个牌型的猜测记录，可以用于判断对方手上一定没有这张牌！

所以双方还需要记录从对方猜牌记录可以猜出，对方一定没有哪一张牌。加上这一步才能得 $100$ 分。

完整代码

顶级折磨，我反正码风注释写的尽力了，尽量看就好…

#include <assert.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int debug = 1;
enum type { WAN, TIAO, BING };
struct card
{
    type t;  // 牌型
    int num; // 牌号

    bool guessed_num[10]; // 被对方猜过的牌号情况，1到9是否有被猜过

    bool is_open;
    card(const string &in = "1W") // 利用字符串构造卡牌
    {
        assert(in.size() == 2); // 其他情况非法
        if (in[1] == 'W')
            t = WAN;
        else if (in[1] == 'T')
            t = TIAO;
        else if (in[1] == 'B')
            t = BING;
        num = in[0] ^ '0';                           // 转换数字
        is_open = false;                             // 初试状态默认没有打开
        memset(guessed_num, 0, sizeof(guessed_num)); // 默认所有都没有被猜过
    }
    int number() const
    {
        if (t == WAN)
            return num;
        else if (t == TIAO)
            return 9 + num;
        else
            return 18 + num;
    }
    bool operator==(const card &o) const { return (t == o.t) && (num == o.num); }
    bool type_less(const card &o) const
    {
        bool i = (t == WAN) && ((o.t == TIAO) || (o.t == BING));
        bool j = (t == TIAO) && (o.t == BING);
        return i || j;
    }
    bool operator<(const card &o) const
    {
        if (num != o.num)
            return num < o.num;
        else
            return type_less(o);
    }
};
// 玩家
struct player
{
    vector<card> cards;
    bool cannot_guess[28]; // 已经在自己手上的和明牌的不能猜

    bool guessed_before[28]; // 自己在抽到新的同类型手牌之前，猜过什么，对方可以以此断定对方目前没有这张卡

    player() { memset(cannot_guess, 0, sizeof(cannot_guess)), memset(guessed_before, 0, sizeof(guessed_before)); }
    // 还没公开的牌数
    int unpublic_size() const
    {
        int ret = 0;
        for (int i = 0; i < cards.size(); ++i)
            if (!cards[i].is_open)
                ++ret;
        return ret;
    }
    // 玩家抽卡
    void draw_card(const card &c)
    {
        // 该牌摸到了，就不能猜对方的这张牌了
        cannot_guess[c.number()] = true;

        // 而且自己曾经猜过的同牌型的消息需要被抹除, 对方无法判断自己一定还没有抽到哪些牌了
        int offset = c.t == WAN ? 0 : c.t == TIAO ? 9 : 18;
        for (int i = 1; i <= 9; ++i)
            guessed_before[offset + i] = false;

        cards.push_back(c);
        sort(cards.begin(), cards.end());
    }
    // 指定牌型要亮出来
    void set_open(const card &c)
    {
        for (int i = 0; i < cards.size(); ++i)
            if (cards[i] == c)
                cards[i].is_open = true;
    }
};

player chen, lu; // 晨晨和小璐
queue<card> pub; // 公共牌堆
bool turn;       // true : 晨晨的回合 false : 小璐的回合

// 游戏开始
void init_game()
{
    turn = true; // 设置为晨晨先手

    string s;                // 读入的字符串
    getline(cin, s);         // 读入晨晨的手牌
    while (s.back() == '\r') // 去掉末尾回车符
        s.pop_back();
    for (int i = 0; i < s.size(); i += 2)
        chen.draw_card(card(s.substr(i, 2)));
    getline(cin, s); // 读入小璐的手牌
    while (s.back() == '\r')
        s.pop_back();
    for (int i = 0; i < s.size(); i += 2)
        lu.draw_card(card(s.substr(i, 2)));
    getline(cin, s);
    while (s.back() == '\r')
        s.pop_back();
    for (int i = 0; i < s.size(); i += 2)
        pub.push(card(s.substr(i, 2))); // 公共排队从左到右是从堆顶到底
}
// 一方全亮出来了即为结束
bool is_finished() { return (chen.unpublic_size() == 0) || (lu.unpublic_size() == 0); }

// 每次推算的话, 其实需要整个卡组推算了, 才能得到实际结果, 因为不只单一颜色的牌会有影响, 其他颜色的卡牌信息也会影响最终决策
vector<card> chen_guess_lu()
{
    vector<card> guess_lu(lu.cards.size());
    for (int guess_idx = lu.cards.size() - 1; guess_idx >= 0; --guess_idx)
    {
        if (lu.cards[guess_idx].is_open)
        {
            guess_lu[guess_idx] = lu.cards[guess_idx];
            continue;
        }
        // 根据右侧的牌 根据其情况判断
        int max_num = 9;
        if (guess_idx < lu.cards.size() - 1)
        {
            if (lu.cards[guess_idx].type_less(guess_lu[guess_idx + 1]))
                max_num = guess_lu[guess_idx + 1].num;
            else
                max_num = guess_lu[guess_idx + 1].num - 1;
        }
        type target = lu.cards[guess_idx].t; // 要猜测的牌型是已知的
        // 根据牌型找出实际型号
        int offset = (target == WAN) ? 0 : (target == TIAO) ? 9 : 18;
        // 不是有手上已知, 不能猜的序号, 在此条件下找最大的
        while (max_num > 1 && (chen.cannot_guess[offset + max_num] || lu.cards[guess_idx].guessed_num[max_num] || lu.guessed_before[offset + max_num]))
            --max_num;
        // 猜测结果
        guess_lu[guess_idx].num = max_num, guess_lu[guess_idx].t = lu.cards[guess_idx].t;
    }
    return guess_lu;
}
vector<card> lu_guess_chen()
{
    vector<card> guess_chen(chen.cards.size());
    for (int guess_idx = 0; guess_idx < chen.cards.size(); ++guess_idx)
    {
        if (chen.cards[guess_idx].is_open)
        {
            guess_chen[guess_idx] = chen.cards[guess_idx];
            continue;
        }
        // 根据左侧的牌 根据其情况判断
        int min_num = 1;
        if (guess_idx > 0)
        {
            if (guess_chen[guess_idx - 1].type_less(chen.cards[guess_idx]))
                min_num = guess_chen[guess_idx - 1].num;
            else
                min_num = guess_chen[guess_idx - 1].num + 1;
        }
        type target = chen.cards[guess_idx].t; // 要猜测的牌型是已知的
        // 根据牌型找出实际型号
        int offset = (target == WAN) ? 0 : (target == TIAO) ? 9 : 18;
        // 不是有手上已知, 不能猜的序号, 还不能是对面目前一定没有的牌, 在此条件下找最大的
        while (min_num < 9 && (lu.cannot_guess[offset + min_num] || chen.cards[guess_idx].guessed_num[min_num] || chen.guessed_before[offset + min_num]))
            ++min_num;
        // 猜测结果
        guess_chen[guess_idx].num = min_num, guess_chen[guess_idx].t = chen.cards[guess_idx].t;
    }
    return guess_chen;
}
// 晨晨的回合
void chen_turn()
{
    bool need_draw = !pub.empty(); // 是否需要抽卡
    bool success = false;          // 是否猜对对面的牌 初始化为false
    card c;
    if (need_draw) // 需要抽卡，就抽一下
    {
        c = pub.front();
        pub.pop();
        chen.draw_card(c);
    }
    int guess_idx = -1; // 先寻找小璐未亮出的最小牌序号
    for (int i = 0; i < lu.cards.size() && guess_idx < 0; ++i)
        if (!lu.cards[i].is_open)
            guess_idx = i;
    vector<card> guess = chen_guess_lu();
    // 强制修正, 如果这个猜过了只能猜更小的值
    while (guess[guess_idx].num > 1 && lu.cards[guess_idx].guessed_num[guess[guess_idx].num])
        guess[guess_idx].num--;

    // 更新一下，自己猜过这个数了，在抽中下一次同牌型的牌之前，对方知道自己一定没有这张牌
    chen.guessed_before[guess[guess_idx].number()] = true;
    if (guess[guess_idx].number() == lu.cards[guess_idx].number())
        success = true;
    if (success)
        lu.set_open(lu.cards[guess_idx]); // 猜中的话，对面要把这张牌亮出来
    else
    {
        // 对面这个牌还没有被猜中，下次猜的时候不能猜这个号码
        lu.cards[guess_idx].guessed_num[guess[guess_idx].num] = true; 
        if (need_draw) // 没猜中且抽卡了 就要把这张卡亮出来                                     
            chen.set_open(c);
    }
    // 更新 : 如果已经有亮的牌，双方以后都不能猜这些牌了
    for (int i = 0; i < chen.cards.size(); ++i)
        if (chen.cards[i].is_open)
            chen.cannot_guess[chen.cards[i].number()] = lu.cannot_guess[chen.cards[i].number()] = true;
    for (int i = 0; i < lu.cards.size(); ++i)
        if (lu.cards[i].is_open)
            chen.cannot_guess[lu.cards[i].number()] = lu.cannot_guess[lu.cards[i].number()] = true;
}
// 小璐的回合
// 具体和晨晨的处理方式类似，不再赘述
void lu_turn()
{
    bool need_draw = !pub.empty(); // 是否需要抽卡
    bool success = false;          // 是否猜对对面的牌 初始化为false
    card c;
    if (need_draw) // 需要抽卡，就抽一下
    {
        c = pub.front();
        pub.pop();
        lu.draw_card(c);
    }

    int guess_idx = chen.cards.size(); // 先寻找晨晨未亮出的最大牌序号
    for (int i = chen.cards.size() - 1; i >= 0 && guess_idx >= chen.cards.size(); --i)
        if (!chen.cards[i].is_open)
            guess_idx = i;

    vector<card> guess = lu_guess_chen();

    // 强制修正, 如果这个猜过了只能猜更大的值
    while (guess[guess_idx].num < 9 && chen.cards[guess_idx].guessed_num[guess[guess_idx].num])
        guess[guess_idx].num++;

    // 更新一下，自己猜过这个数了，在抽中下一次同牌型的牌之前，对方知道自己一定没有这张牌
    lu.guessed_before[guess[guess_idx].number()] = true;
    if (guess[guess_idx].number() == chen.cards[guess_idx].number())
        success = true;
    if (success)
        chen.set_open(chen.cards[guess_idx]); // 猜中的话，对面要把这张牌亮出来
    else
    {
        // 对面这个牌还没有被猜中，下次猜的时候不能猜这个号码
        chen.cards[guess_idx].guessed_num[guess[guess_idx].num] = true; 
        if (need_draw) // 没猜中且抽卡了 就要把这张卡亮出来                                     
            lu.set_open(c);
    }
    // 更新 : 如果已经有亮的牌，双方以后都不能猜这些牌了
    for (int i = 0; i < chen.cards.size(); ++i)
        if (chen.cards[i].is_open)
            chen.cannot_guess[chen.cards[i].number()] = lu.cannot_guess[chen.cards[i].number()] = true;
    for (int i = 0; i < lu.cards.size(); ++i)
        if (lu.cards[i].is_open)
            chen.cannot_guess[lu.cards[i].number()] = lu.cannot_guess[lu.cards[i].number()] = true;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    init_game(); // 初始化输入 设置为晨晨先手
    while (!is_finished())
    {
        if (turn)
            chen_turn();
        else
            lu_turn();
        turn = !turn; // 回合轮换
    }
    if (chen.unpublic_size())
        printf("C\n%d", chen.unpublic_size());
    else
        printf("L\n%d", lu.unpublic_size());
}