题意
具体的不翻译了,简单地说就问你当前的手牌,能不能直接获胜,如果不能,就输出所有可行的获胜方案。
获胜方案就是打出某张牌,再摸一张就获胜(不考虑牌池,所有牌都无限可取),对每种打出方案同一行后面输出,可摸哪张牌赢(可能也是多选的)。
思路
按照花色把手牌分成四类,每一类内部独例分析。比赛的时候,我们队没理清楚,时间也不多了,没写出来。仔细一想抛去花色,同花色内部的问题会是一个互通的问题。
对于一个14张牌的格局,我的获胜检查算法这样设计:
记一个cnt桶数组,对每种牌面计数。
- 用for34的复杂度去枚举雀首,对拿去雀首后的12张牌进行校验
- 用for4的复杂度枚举花色
- 对每一种花色内部,从小到大进行推理检查:
- 枚举到一种牌,优先拿去3的倍数的同种牌
- 假如这不是字面牌,再按照需要拿去顺子所需的三种牌,注意当前的牌必须取尽。
按照如上操作可以设计两个函数,注意判掉各种不合法的情况即可。到这里分复杂度是。
对于题目给的格局,先判断是不是本身就是获胜,然后用for34的复杂度去枚举哪种牌打出1张,再用for34的复杂度去枚举哪种牌摸入1张,同时按照如上的步骤检查这个格局是否是获胜的。保存答案。
如果枚举顺序能保证就按照题目要求的顺序,最后答案就不需要排序。
这样做单组样例的复杂度看似是,稍加思索其实很少,也有很多可以剪枝的细节,是可以过的(我的代码在牛客跑了200~400ms差不多,喜欢用数组的人应该会比我更快)。
代码
代码里有一些过度利用STL的地方,大家请自行优化。
using namespace std; using pii = pair<int, int>; using vint = vector<int>; const map<char, int> CI = { {'w', 0}, {'b', 1}, {'s', 2}, {'z', 3} }; const vector<char> IC = {'w', 'b', 's', 'z'}; bool check_valid(const vector<vint> &cnt) { static vector<vint> c; // 似乎静态对象的浅拷贝比堆栈区反复创建函数参数要快许多。 c = cnt; for (auto &ci : c) { for (size_t j = 0; j < ci.size(); ++j) { if (ci[j] >= 3) ci[j] %= 3; if (ci[j] == 0) continue; // ci[j] == 1 or 2 if (&ci == &c.back()) return false; // i < 3 if (j + 2 >= 9 || ci[j] > min(ci[j + 1], ci[j + 2])) return false; ci[j + 2] -= ci[j]; ci[j + 1] -= ci[j]; ci[j] -= ci[j]; } } return true; } bool check_Tsumo(vector<vint> &cnt) { for (auto &ci : cnt) { if (accumulate(ci.begin(), ci.end(), 0) % 3 == 1) { return false; //sum % 3 != 0 && sum % 3 != 2 } } for (auto &ci : cnt) { for (auto &cij : ci) { if (cij < 2) continue; cij -= 2; bool res{check_valid(cnt)}; cij += 2; if (res) return true; } } return false; } void solve(int kaseId = -1) { vector<vint> cnt{ vint(9, 0), vint(9, 0), vint(9, 0), vint(7, 0) }; string s; cin >> s; for (int i = 0, j = 1; j < 28; i += 2, j += 2) { int id = s[i] - '1'; // 0 ~ 8 cnt[CI.at(s[j])][id]++; } if (check_Tsumo(cnt)) { cout << "Tsumo!" << endl; return; } vector<pair<string, string>> ans; for (auto &ci: cnt) { for (auto &cij: ci) { if (cij == 0) continue; cij--; string str; for (size_t i = 0; i < 4; ++i) { for (size_t j = 0; j < cnt[i].size(); ++j) { if (&cij == &cnt[i][j]) continue; cnt[i][j]++; if (check_Tsumo(cnt)) { str.append(to_string(j + 1) + IC[i]); } cnt[i][j]--; } } cij++; if (!str.empty()) { ans.emplace_back( to_string(&cij - &ci.front() + 1) + IC[&ci - &cnt.front()], move(str)); } } } cout << ans.size() << endl; for (auto ai : ans) { cout << ai.first << " " << ai.second << endl; } }