2022 ICPC合肥 M Mahjong

Mahjong

爆搜

先搜索出所有胡牌的情况，然后根据胡牌的情况，随便丢掉一张牌，则肯定是听牌状态

然后枚举所有的听牌状态，计算其听牌集合，存起来即可

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <map>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
map<ll, ll>mp, ans, tag;
int vis[10];

void solve()
{
    ll now = 0;
    for(int j=1; j<10; j++)
    {
        for(int k=0; k<vis[j]; k++)
        {
            now *= 10;
            now += j;
        }
    }
    if(tag[now]) return;
    tag[now] = 1;
    ll last = 0;
    for(int i=1; i<10; i++)
    {
        if(vis[i] == 4) continue;
        vis[i]++;
        ll tot = 0;
        for(int j=1; j<10; j++)
        {
            for(int k=0; k<vis[j]; k++)
            {
                tot *= 10;
                tot += j;
            }
        }
        if(mp.count(tot))
        {
            last *= 10;
            last += i;
        }
        vis[i]--;
    }
    ans[last] = now;
}

void dfs(int now, int cnt, int sum)
{
    if(vis[now] == 4) now++;
    if(cnt == 5)
    {
        if(sum != 14) return;
        ll tot = 0;
        for(int i=1; i<=9; i++)
        {
            for(int j=0; j<vis[i]; j++)
            {
                tot *= 10;
                tot += i;
            }
        }
        mp[tot] = 1;
        return;
    }
    if(now >= 10) return;

    if(vis[now] <= 2 && sum % 3 == 0)
    {
        vis[now] += 2;
        dfs(now, cnt + 1, sum + 2);
        vis[now] -= 2;
    }
    if(vis[now] <= 1)
    {
        vis[now] += 3;
        dfs(now, cnt + 1, sum + 3);
        vis[now] -= 3;
    }
    if(now <= 7 && vis[now] <= 3 && vis[now + 1] <= 3 && vis[now + 2] <= 3)
    {
        vis[now]++;
        vis[now + 1]++;
        vis[now + 2]++;
        dfs(now, cnt + 1, sum + 3);
        vis[now]--;
        vis[now + 1]--;
        vis[now + 2]--;
    }
    dfs(now + 1, cnt, sum);
}

int main()
{
    dfs(1, 0, 0);
    for(auto [x, y] : mp)
    {
        ll xx = x;
        while(xx)
        {
            vis[xx % 10]++;
            xx /= 10;
        }
        for(int i=1; i<=9; i++)
        {
            if(vis[i] == 0) continue;
            vis[i]--;
            solve();
            vis[i]++;
        }
        for(int i=1; i<10; i++) vis[i] = 0;
    }
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        if(s == "0") {cout << "3677788889999" << "\n"; continue;}
        sort(s.begin(), s.end());
        ll tot = 0;
        for(int now : s) tot = tot * 10 + (now - '0');
        if(ans.count(tot))
            cout << ans[tot] << "\n";
        else
            cout << "impossible\n";
    }
    return 0;
}