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;
}