[pkusc2018] 主斗地

其实是道很清蒸的题，大家觉得它毒瘤大概主要是因为[斗地主][https://loj.ac/problem/2539]？

题目链接：[PKUSC2018 主斗地][https://loj.ac/problem/6434]

题意就免了吧……

题解

因为去掉了三和××网友的17张牌，我们写个代码爆搜一下九莲可能的牌有多少种。

#include<bits/stdc++.h>
using namespace std;

int ans;
int a[20], res[20];
char s[20];

int get(char c) {
    if (c == 'T') return 10;
    if (c == 'J') return 11;
    if (c == 'Q') return 12;
    if (c == 'K') return 13;
    if (c == 'A') return 14;
    if (c == '2') return 15;
    if (c == 'w') return 16;
    if (c == 'W') return 17;
    return c - '0';
}

void dfs(int x, int now) {
    if (now > 17) return;
    if (x == 18) {
        if (now == 17) ++ans;
        return;
    }
    for (int i = 0; i <= res[x]; ++i) {
        dfs(x + 1, now + i);
    }
}

int main() {
    while (~scanf("%s", s + 1)) {
        ans = 0;
        memset(a, 0, sizeof a);
        for (int i = 4; i <= 15; ++i) {
            res[i] = 4;
        }
        res[16] = res[17] = 1;
        for (int i = 1; i <= 17; ++i) {
            int x = get(s[i]);
            ++a[x];
            --res[x];
        }
        dfs(4, 0);
        cout << ans << endl;
    }
}

大致估计一下

应该是九莲的可能牌型数较多的一种输入，而这种九莲的可能牌型也只有1626841种。

我们先搜出九莲的牌，暴力check是否可行。

第一档部分分：输入数据中每种牌只出现最多只出现两次。这种情况下显然只有单牌是有用的，其余顺子对子都可以当做单牌打出。直接扫一下就OK。

第二档部分分：每种牌最多出现三次。有用牌型只能是单牌，三带一，三带二。先爆搜出九莲哪些牌三张一起打出，以及对应的××网友用什么牌接，然后枚举这里面带了多少对子和单张，把九莲最大的牌和××网友最小的牌贪心带掉就好了。

正解：还需要考虑四带二，和上一种本质相同，直接看代码吧。

#include<bits/stdc++.h>
using namespace std;

char s[20];
int ans, flag, a[20], b[20];
int res[20];

int get(char c) {
    if (c == 'T') return 10;
    if (c == 'J') return 11;
    if (c == 'Q') return 12;
    if (c == 'K') return 13;
    if (c == 'A') return 14;
    if (c == '2') return 15;
    if (c == 'w') return 16;
    if (c == 'W') return 17;
    return c - '0';
}

void check2(int sg, int db) {
    static int c[20], d[20];
    for (int i = 4; i <= 17; ++i) {
        c[i] = b[i];
        d[i] = a[i];
    }
    for (int i = 4, j = 17; i <= 17 && db; ++i) {
        while (d[i] >= 2 && db) {
            while (j && c[j] < 2) --j;
            if (c[j] >= 2) {
                --db;
                d[i] -= 2;
                c[j] -= 2;
            }
            else break;
        }
    }
    for (int i = 4, j = 17; i <= 17 && sg; ++i) {
        while (d[i] >= 1 && sg) {
            while (j && c[j] < 1) --j;
            if (c[j] >= 1) {
                --sg;
                d[i] -= 1;
                c[j] -= 1;
            }
            else break;
        }
    }
    for (int i = 4, j = 4; i <= 17; ++i) {
        while (c[i] > 0) {
            while (d[j] == 0 && j <= 17) ++j;
            if (d[j] > 0 && j > i) {
                --c[i];
                --d[j];
            }
            else return;
        }
    }
    flag = 1;
}

void dfs2(int x, int tr, int fr, int A, int B) {
    if (flag) return;
    if (A < 0 || B < 0) return;
    if (x == 18) {
        if (A == 0 && B == 0) {
            for (int i = 0; i <= tr; ++i) {
                check2(i + fr * 2, tr - i);
            }
        }
        return;
    }
    dfs2(x + 1, tr, fr, A, B);
    if (b[x] >= 3) {
        b[x] -= 3;
        dfs2(x + 1, tr + 1, fr, A + 1, B);
        b[x] += 3;
    }
    if (b[x] >= 4) {
        b[x] -= 4;
        dfs2(x + 1, tr, fr + 1, A, B + 1);
        b[x] += 4;
    }
    if (a[x] >= 3) {
        a[x] -= 3;
        dfs2(x + 1, tr, fr, A - 1, B);
        a[x] += 3;
    }
    if (a[x] >= 4) {
        a[x] -= 4;
        dfs2(x + 1, tr, fr, A, B - 1);
        a[x] += 4;
    }
}

void check() {
    flag = 0;
    dfs2(4, 0, 0, 0, 0);
    ans += flag;
}

void dfs(int x, int now) {
    if (now > 17) return;
    if (x == 18) {
        if (now == 17) check();
        return;
    }
    for (int i = 0; i <= res[x]; ++i) {
        b[x] = i;
        dfs(x + 1, now + i);
        b[x] = 0;
    }
}

int main() {
    while (~scanf("%s", s + 1)) {
        ans = 0;
        memset(a, 0, sizeof a);
        for (int i = 4; i <= 15; ++i) {
            res[i] = 4;
        }
        res[16] = res[17] = 1;
        for (int i = 1; i <= 17; ++i) {
            int x = get(s[i]);
            ++a[x];
            --res[x];
        }
        dfs(4, 0);
        cout << ans << endl;
    }
}