題面

Loj

題解

細(xì)節(jié)比較多的搜索題。

首先現(xiàn)將牌型暴力枚舉出來(lái)，大概是\(3^{16}\)吧。

然后再看能打什么，簡(jiǎn)化后無(wú)非就三種決策：單牌，\(3+x\)和\(4+x\)。

枚舉網(wǎng)友打了幾張\(3\)和\(4\)，然后再枚舉吉老師（\(\mathbf {orz}\)）打了幾張\(3\)和\(4\)。

接著枚舉\(3\)搭配了幾個(gè)\(2\)，然后貪心地從大到小去除吉老師手中大小為\(2\)的對(duì)子，從小到大去除網(wǎng)友手中大小為\(2\)的對(duì)子。之后就是檢查單牌是否合法了。

#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using std::min; using std::max; using std::swap; using std::sort; typedef long long ll;template<typename T> void read(T &x) {int flag = 1; x = 0; char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag; }const int _ = 20; char s[_]; int ans, cnt[_], a[_], orz[_]; int wy[_], jtkl[_], thr[_], fou[_], W[_], J[_], P[_];int code (char c){switch(c) {case 'T': return 7;case 'J': return 8;case 'Q': return 9;case 'K': return 10;case 'A': return 11;case '2': return 12;case 'w': return 13;case 'W': return 14;default: return c - '4' + 1;} }bool check(int f, int t) {for(int i = 0; i <= t; ++i) {memcpy(W, wy, sizeof wy), memcpy(J, jtkl, sizeof jtkl);if(2 * i + t - i + f * 2 + f * 4 + t * 3 > 17) break;int cnt = 0;for(int j = 1; j <= 14; ++j) {if(W[j] >= 2 && cnt < i) W[j] -= 2, ++cnt;if(W[j] >= 2 && cnt < i) W[j] -= 2, ++cnt;if(cnt == i) break;}if(cnt < i) break; cnt = 0;for(int j = 14; j >= 1; --j) {if(J[j] >= 2 && cnt < i) J[j] -= 2, ++cnt;if(J[j] >= 2 && cnt < i) J[j] -= 2, ++cnt;if(cnt == i) break;}if(cnt < i) break;memset(P, 0, sizeof P);cnt = 2 * f + t - i;for(int j = 14; j >= 1; --j) {int t = min(cnt, J[j]);J[j] -= t, cnt -= t;if(!cnt) break;}if(cnt) continue;cnt = 2 * f + t - i;for(int j = 1; j <= 14; ++j) {int t = min(cnt, W[j]);W[j] -= t, cnt -= t;if(!cnt) break;}if(J[14]) continue;for(int j = 1; j <= 14; ++j)P[j] += W[j], P[j + 1] -= J[j];cnt = 0;for(int j = 1; j <= 14; ++j) {cnt += P[j];if(cnt > 0) break;}if(!cnt) return true;} return false; }bool check_jtkl(int now, int four, int three, int f, int t, int q1, int q2) {if(four == f && three == t) return check(f, t);if(now >= 12) return false;q1 += thr[now], q2 += fou[now];if(q1 > 0 || q2 > 0) return false;if(jtkl[now] >= 3) {jtkl[now] -= 3;if(check_jtkl(now + 1, four, three, f, t + 1, q1 - 1, q2)) return true;jtkl[now] += 3;}if(jtkl[now] >= 4) {jtkl[now] -= 4;if(check_jtkl(now + 1, four, three, f + 1, t, q1, q2 - 1)) return true;jtkl[now] += 4;}return check_jtkl(now + 1, four, three, f, t, q1, q2); }bool check_wy (int now, int four, int three) {if(four * 6 + three * 4 > 17) return false;if(now > 12) return check_jtkl(1, four, three, 0, 0, 0, 0);if(wy[now] >= 3) {wy[now] -= 3, ++thr[now];if(check_wy(now + 1, four, three + 1)) return true;wy[now] += 3, --thr[now];}if(wy[now] >= 4) {wy[now] -= 4, ++fou[now];if(check_wy(now + 1, four + 1, three)) return true;wy[now] += 4, --fou[now];}return check_wy(now + 1, four, three); }void dfs(int now, int rest) {if(!rest) {memset(thr, 0, sizeof thr);memset(fou, 0, sizeof fou);memcpy(wy, a, sizeof a);memcpy(jtkl, orz, sizeof orz);if(check_wy(2, 0, 0)) ++ans;return ;}if(now > 14) return ;for(int i = 0; i <= cnt[now]; ++i) {if(i > rest) break;orz[now] = i, dfs(now + 1, rest - i), orz[now] = 0;} }int main () {while(scanf("%s", s + 1) != EOF) {memset(a, 0, sizeof a);for(int i = 1; i <= 12; ++i) cnt[i] = 4;cnt[13] = cnt[14] = 1, ans = 0;for(int i = 1; i <= 17; ++i)++a[code(s[i])], --cnt[code(s[i])];dfs(1, 17), printf("%d\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/water-mi/p/10289540.html

總結(jié)

以上是生活随笔為你收集整理的Loj#6434「PKUSC2018」主斗地（搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。