Vexoben
May 5, 2019
其实是道很清蒸的题，大家觉得它毒瘤大概主要是因为[斗地主][100]？
题目链接：[PKUSC2018 主斗地][101]
题意就免了吧……
题解
因为去掉了三和××网友的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;
}
}
大致估计一下
456789TJQKA456789
应该是九莲的可能牌型数较多的一种输入，而这种九莲的可能牌型也只有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;
}
}
[100] : https://loj.ac/problem/2539
[101] : https://loj.ac/problem/6434