2021 ICPC 昆明站--搓麻将？？（模拟）

57 阅读 0 评论 38 点赞

我是靠谱客的博主鲤鱼云朵，最近开发中收集的这篇文章主要介绍2021 ICPC 昆明站--搓麻将？？（模拟），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2021 ICPC 昆明站–搓麻将？？

题意： 给你 $14$ 张牌，判断当前是否已经胡了，或者当前的牌出掉哪一张牌可以进入听牌，还要求得听牌时，哪些牌可以胡。（因简化了问题，这里所有种类的牌都无限的）

思路：

思路很简单，就是怎么判断胡牌我卡了半天。

我判断胡牌的规则：先枚举当前的牌中数量大于等于2的牌，去掉这一对，剩下的 $12$ 张牌要满足三张三张凑成对。直接判断不好判断，所以我先爆搜将所有能胡牌的情况（已经去掉对子的情况）记录下来，并用 $13$ 进制存下来放入 $s e t$ 。这样只需要将当前牌的状态转换成数就能判断是否胡牌了。

~~模拟题还卡常，难写的一批。。。~~

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
char s[N];
map<int, char> mp1;
map<char, int> mp2;
set<ll> stt;
int vis[4][15];
int v[4][15];

//预处例所有解的情况
int step[10];
void dfs(int dep) {
    if (dep == 5) {
        return;
    }
    for (int i = 1; i <= 16; i++) {
        step[dep] = i;
        vector<int> q(10, 0);
        for (int i = 1; i <= dep; i++) {
            int xp = step[i];
            if (xp <= 7) {
                for (int j = xp; j < xp + 3; j++) q[j]++;
            }
            else {
                xp -= 7; q[xp] += 3;
            }
        }
        ll tmp = 0;
        for (int i = 9; i > 0; i--) {
            tmp = tmp * 13 + q[i];
        }
        stt.insert(tmp);
        dfs(dep + 1);
    }
}

//该牌的状态
struct pile{
    int num, id;
    pile() {}
    pile(int _num, int _id) {
        num = _num; id = _id;
    }
    void output() {
        printf("%d%c", num, mp1[id]);
    }
    bool operator==(const pile& o) const {
        return id == o.id && num == o.num;
    }
    bool operator<(const pile& o) const {
        return id < o.id || (id == o.id && num < o.num);
    }
}p[20];

void deg() {
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= 9; j++) {
            printf("%d ", vis[i][j]);
        }
        printf("n");
    }
    for (int j = 1; j <= 7; j++)
        printf("%d ", vis[3][j]);
    printf("n");
}

void init() {
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 10; j++)
            vis[i][j] = 0;

    for (int i = 1; i <= 14; i++) {
        int id = p[i].id, num = p[i].num;
        vis[id][num]++;
    }
}

bool is_ok() {
    for (int i = 0; i < 4; i++)
        for (int j = 0; j <= 9; j++)
            v[i][j] = vis[i][j];
    for (int j = 1; j <= 7; j++)
        if (vis[3][j] % 3 != 0) return false;
    for (int i = 0; i < 3; i++) {
        ll tmp = 0;
        for (int j = 9; j > 0; j--) {
            tmp = tmp * 13 + vis[i][j];
        }
        auto it = stt.find(tmp);
        if (it == stt.end()) return false;
    }
    return true;
}

bool is_win() {
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= 9; j++) {
            if (vis[i][j] >= 2) {
                vis[i][j] -= 2;
                bool f = is_ok();
                vis[i][j] += 2;
                if (f) return true;
            }
        }
    }
    for (int j = 1; j <= 7; j++) {
        if (vis[3][j] >= 2) {
            vis[3][j] -= 2;
            bool f = is_ok();
            vis[3][j] += 2;
            if (f) return true;
        }
    }
    return false;
}

pile del[50];
vector<pile> res[50];
int solve() {
    int cnt = 0;
    for (int i = 1; i <= 14; i++) {
        if (i != 1 && p[i] == p[i - 1]) continue;
        int id = p[i].id, num = p[i].num;
        vis[id][num]--;
        cnt++; res[cnt].clear();
        del[cnt] = p[i];
        for (int i = 0; i < 3; i++) {
            for (int j = 1; j <= 9; j++) {
                vis[i][j]++;
                if (is_win()) res[cnt].push_back(pile(j, i));
                vis[i][j]--;
            }
        }
        for (int j = 1; j <= 7; j++) {
            vis[3][j]++;
            if (is_win()) res[cnt].push_back(pile(j, 3));
            vis[3][j]--;
        }
        if (res[cnt].size() == 0) --cnt;
        vis[id][num]++;
    }
    return cnt;
}

int main() {
    mp1[0] = 'w'; mp1[1] = 'b';
    mp1[2] = 's'; mp1[3] = 'z';

    mp2['w'] = 0; mp2['b'] = 1;
    mp2['s'] = 2; mp2['z'] = 3;

    dfs(1); //预处例所有结果
    stt.insert(0);
//    cout << stt.size() << "n";
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%s", s + 1);
        for (int i = 1; i <= 14; i++) {
            int id = mp2[s[2 * i]];
            int num = s[2 * i - 1] - '0';
            p[i] = pile(num, id);
        }
        sort(p + 1, p + 1 + 14);
//        for (int i = 1; i <= 14; i++) {
//            printf("%d  %cn", p[i].num, mp1[p[i].id]);
//        }
        init();
//        deg();
        if (is_win()) {
            printf("Tsumo!n");
            continue;
        }
        int cnt = solve();
        printf("%dn", cnt);
        for (int i = 1; i <= cnt; i++) {
            del[i].output(); printf(" ");
            for (pile now : res[i])
                now.output();
            printf("n");
        }
    }
    return 0;
}