2022牛客多校（八）
文章目录
- 2022牛客多校（八）
- 一、牛客多校比赛小结
- 二、牛客多校题目分析及解法（基础题）
- D、牛客多校Poker Game: Decision
- F、牛客多校Longest Common Subsequence
- 三、牛客多校题目分析及解法（进阶题）
一、牛客多校比赛小结
比赛链接："蔚来杯"2022牛客暑期多校训练营8
二、牛客多校题目分析及解法（基础题）
D、牛客多校Poker Game: Decision
题目链接：D-Poker Game: Decision
题意：
德州扑克，牛客多校两人博弈
题解：
记忆化所有答案即可，牛客多校博弈部分简单，牛客多校判断牌型部分难写
代码：
#include using namespace std;using LL = long long;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); auto read = []() { static string ranks = "0123456789TJQKA"; static string suits = "SHCD"; string s; cin >>s; return (find(ranks.begin(),牛客多校 ranks.end(), s[0]) - ranks.begin()) * 4 + (find(suits.begin(), suits.end(), s[1]) - suits.begin()); }; mapmp; auto rank = [&](LL h) ->int { int res = 0; vectorr, s; while (h) { int t = __builtin_ctzll(h); r.push_back(t / 4); s.push_back(t % 4); h ^= 1LL << t; } int straight = 1; for (int i = 0; i < 3; i += 1) if (r[i] + 1 != r[i + 1]) straight = 0; if ((r[3] + 1 != r[4]) and (r[3] != 5 or r[4] != 14)) straight = 0; int flush = 1; for (int i = 0; i < 4; i += 1) if (s[i] != s[i + 1]) flush = 0; if (straight and flush) { if (r[3] + 1 == r[4]) return res = (9 << 20) | r[4]; return res = (9LL << 20) | r[3]; } if (r[0] == r[3]) return res = (8 << 20) | r[0]; if (r[1] == r[4]) return res = (8 << 20) | r[1]; if (r[0] == r[2] and r[3] == r[4]) return res = (7 << 20) | r[0]; if (r[0] == r[1] and r[2] == r[4]) return res = (7 << 20) | r[2]; if (flush) return (6 << 20) | (r[4] << 16) | (r[3] << 12) | (r[2] << 8) | (r[1] << 4) | r[0]; if (straight) { if (r[3] + 1 == r[4]) return (5 << 20) | r[4]; return (5 << 20) | r[3]; } if (r[0] == r[2]) return (4 << 20) | r[0]; if (r[1] == r[3]) return (4 << 20) | r[1]; if (r[2] == r[4]) return (4 << 20) | r[2]; if (r[0] == r[1] and r[2] == r[3]) return (3 << 20) | (r[2] << 8) | (r[0] << 4) | r[4]; if (r[0] == r[1] and r[3] == r[4]) return (3 << 20) | (r[3] << 8) | (r[0] << 4) | r[2]; if (r[1] == r[2] and r[3] == r[4]) return (3 << 20) | (r[3] << 8) | (r[1] << 4) | r[0]; if (r[0] == r[1]) return (2 << 20) | (r[0] << 12) | (r[4] << 8) | (r[3] << 4) | r[2]; if (r[1] == r[2]) return (2 << 20) | (r[1] << 12) | (r[4] << 8) | (r[3] << 4) | r[0]; if (r[2] == r[3]) return (2 << 20) | (r[2] << 12) | (r[4] << 8) | (r[1] << 4) | r[0]; if (r[3] == r[4]) return (2 << 20) | (r[3] << 12) | (r[2] << 8) | (r[1] << 4) | r[0]; return (1 << 20) | (r[4] << 16) | (r[3] << 12) | (r[2] << 8) | (r[1] << 4) | r[0]; }; int T; vector f(64, vector(64)); vector g(64, vector(64, INT_MAX)); vectorsc(1 << 6); vectorsci; vector ci(1 << 6, vector()); for (int i = 0; i < (1 << 6); i += 1) { if (__builtin_popcount(i) == 3) sci.push_back(i); for (int j = 0; j < 6; j += 1) if ((i >>j) & 1) ci[i].push_back(j); } for (cin >>T; T; T -= 1) { LL A = (1LL << read()) | (1LL << read()); LL B = (1LL << read()) | (1LL << read()); vectorc(6); for (int& ci : c) ci = read(); for (int i : sci) { sc[i] = 0; for (int j : ci[i]) sc[i] |= 1LL << c[j]; } functionDFS = [&](int a, int b, int c) ->int { if (g[a][b] == T) return f[a][b]; g[a][b] = T; int& res = f[a][b]; if (c == 0) { auto rA = rank(A | sc[a]), rB = rank(B | sc[b]); if (rA >rB) return res = 1; if (rA == rB) return res = 0; return res = -1; } if (__builtin_parity(c)) { res = 1; for (int i : ci[c]) { int pres = DFS(a, b ^ (1 << i), c ^ (1 << i)); res = min(res, pres); } return res; } res = -1; for (int i : ci[c]) { int pres = DFS(a ^ (1 << i), b, c ^ (1 << i)); res = max(res, pres); } return res; }; int res = DFS(0, 0, 63); if (res == 0) cout << "Draw\n"; else if (res >0) cout << "Alice\n"; else cout << "Bob\n"; }} F、Longest Common Subsequence
题目链接：F-Longest Common Subsequence
题意：
给出一个元素，牛客多校以及序列生成方式 a i + 1 = f ( a i ) a_{ i+1} = f(a_i) ai+1=f(ai) ，牛客多校求最长公共序列
题解：
如果两个序列中有相同数字，牛客多校那么后面的数字一定全一样. 对每个数字找到出现的最早位置.复杂度 O(n + m).
代码：
#include using namespace std;typedef long long ll;ll t, n, m, p, x, a, b, c, res;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >>t; while (t--) { cin >>n >>m >>p >>x >>a >>b >>c; res = 0; unordered_mapmp1, mp2; for (ll i = 1; i <= n; i++) { x = (a * x % p * x % p + b * x % p + c) % p; if (!mp1.count(x)) mp1[x] = i; } for (ll i = 1; i <= m; i++) { x = (a * x % p * x % p + b * x % p + c) % p; if (!mp2.count(x)) mp2[x] = i; if (mp1.count(x)) { res = max(res, min(n - mp1[x] + 1, m - mp2[x] + 1)); } } cout << res << endl; } return 0;} 三、题目分析及解法（进阶题）
这场摆大烂了X
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wgqSXLUC-1663914439439)(file://C:\Users\lenovo\AppData\Roaming\marktext\images\2022-09-23-14-26-37-image.png?msec=1663914397917)]
