[2021 ICPC 昆明 K] Riichi!!

本文主要是介绍[2021 ICPC 昆明 K] Riichi!!，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://ac.nowcoder.com/acm/contest/12548/K

题意：
现有14张牌，现在进行一次舍张和进张，输出能胡牌的方案。

思路：
自己写了200多行只有5%的通过率，直接偷学了三个顶俩的做法重写了。

因为每种牌型都是相互独立的，所以我们可以先求出所有合法的情况。在存拥有的牌的情况时，由于数据很小，我们可以用二进制存储，大概长这样。

\(1\)(大小为\(1\)的牌的数量)\(1\)(大小为\(2\)的牌的数量)\(1\dots1\)(大小为\(9\)的牌的数量)

中间直接留对应数量的大小即可，完全不会太大。注意字牌没有顺子，额外处理下就行。

然后暴力枚举舍张和进张，连下答案即可。

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1 << 25;

bool vis[N];
char a[] = {"wbsz"};
int cur[11], num[37];
int id[303];
int tot, cnt;
string s;
string ans[37];

void add(int p, int v) {
    cur[p] += v;
    tot += v;
}

void addAns(int pos, int i) {
    int v = i % 9;
    if (v == 0) v = 9;
    ans[pos] += to_string(v);
    if (i <= 9) ans[pos] += "w";
    else if (i <= 18) ans[pos] += "b";
    else if (i <= 27) ans[pos] += "s";
    else ans[pos] += "z";
}

int getHash() {
    int res = 0;
    cnt = 0;
    for (int i = 1; i <= 9; ++i) {
        res <<= 1;
        res += 1;
        res <<= cur[i];
        cnt += cur[i];
    }
    return res;
}

void dfs(int p) {
    int now = getHash();
    if (vis[now]) return;
    vis[now] = true;
    while (p <= 9) {
        if (p <= 7 && tot <= 11) { // shunzi
            add(p, 1); add(p + 1, 1); add(p + 2, 1);
            dfs(p);
            add(p, -1); add(p + 1, -1); add(p + 2, -1);
        }
        if (tot <= 11) { // kezi
            add(p, 3);
            dfs(p);
            add(p, -3);
        }
        if (tot <= 12 && tot % 3 == 0) { // quetou
            add(p, 2);
            dfs(p);
            add(p, -2);
        }
        p++;
    }
}

bool check() {
    int quetou = 0;
    for (int i = 0; i <= 2; ++i) {
        memcpy(cur + 1, num + 9 * i + 1, sizeof(cur));
        if (!vis[getHash()]) return false;
        quetou += cnt % 3 == 2;
    }
    int d = 27;
    for (int i = 1; i <= 7; ++i) {
        if (num[d + i] % 3 == 1) return false;
        quetou += num[d + i] % 3 == 2;
    }
    return quetou == 1;
}

void solve() {
    memset(num, 0, sizeof(num));
    cin >> s;
    for (int i = 0; i < 14; ++i) {
        int n = s[i * 2] - '0';
        char c = s[i * 2 + 1];
        num[id[c] + n]++;
    }
    if (check()) {
        cout << "Tsumo!" << endl;
        return;
    }
    for (int i = 1; i <= 34; ++i) {
        ans[i] = "";
    }
    int ansNum = 0;
    for (int i = 1; i <= 34; ++i) {
        addAns(i, i);
        ans[i] += " ";
        if (num[i]) {
            int flag = 0;
            num[i]--;
            for (int j = 1; j <= 34; ++j) {
                num[j]++;
                if (check()) {
                    flag = 1;
                    addAns(i, j);
                }
                num[j]--;
            }
            ansNum += flag;
            num[i]++;
        }
    }
    cout << ansNum << endl;
    for (int i = 1; i <= 34; ++i) {
        if (ans[i].length() > 3) {
            cout << ans[i] << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
    for (int i = 0; i < 4; ++i) {
        id[ a[i] ] = i * 9;
    }
    dfs(1);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

这篇关于[2021 ICPC 昆明 K] Riichi!!的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！