在高铁上加训！
A – Same (abc324 A)题目大意
给定\(n\)个数，问是否都相等。
解题思路
判断是不是全部数属于第一个数即可。或者直接拿set去重。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (auto& i : a) cin >> i; cout << (set(a.begin(), a.end()).size() == 1 ? "Yes" : "No") << '\n'; return 0;}B – 3-smooth Numbers (abc324 B)题目大意
给定一个数\(N\)，问是否能表示成 \(2^x3^y\)。
解题思路
指数范围不会超过\(64\)，花 \(O(64^2)\)枚举判断即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); LL n; cin >> n; auto check = [&]() { for (int i = 0; i < 64; ++i) { LL x = (1ll << i); for (int j = 0; j n) break; if (x == n) return true; x *= 3; } } return false; }; if (check()) cout << "Yes" << '\n'; else cout << "No" << '\n'; return 0;}C – Error Correction (abc324 C)题目大意
给定一个字符串\(t\)和若干个字符串 \(s\)。问有哪些 \(s\)，满足以下四个条件中的一个：
- \(s = t\)
- \(s\)在某处增加一个字母得到 \(t\)
- \(s\)在某处删除一个字母得到 \(t\)
- \(s\)在某处修改一个字母得到 \(t\)
解题思路
第一个就判断是否逐位相等。
第二个和第三个其实是一样的，就是两者长度是否差\(1\)，且较小串是较大串的一个子序列。用子序列贪心逐位匹配即可。
第四个就判断是否只有一位不相等，
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; string s; cin >> n >> s; vector ans; auto check2 = [](const string& l, const string& r) { if (r.size() - l.size() != 1) return false; int x = 0, y = 0; while (x < l.size()) { while (y < r.size() && r[y] != l[x]) ++y; if (y < r.size()) { ++x; ++y; } else break; } return x == l.size(); }; auto check = [&](const string& t) { if (s.size() == t.size()) { int cnt = 0; for (int i = 0; i < s.size(); ++i) cnt += (s[i] != t[i]); return cnt <= 1; } if (s.size() < t.size()) return check2(s, t); else return check2(t, s); }; for (int i = 1; i > t; if (check(t)) ans.push_back(i); } cout << ans.size() << '\n'; for (auto& i : ans) cout << i << ' '; cout << '\n'; return 0;}D – Square Permutation (abc324 D)题目大意
给定一个数字串\(s\)，将每一个数位排序，问能排出多少种数，其为平方数。
解题思路
注意到串长度只有\(13\)，我们可以枚举每一个平方数\(x\)，只有 \(\sqrt{10^{13}\)个，然后判断数字串 \(s\)能否表示出这个数\(x\)即可。
因为数字串 \(s\)可以排列，因此问数字串能否表示出这个数 \(x\)，其实就是问这两个的每个数位数字的个数是否相等。
注意计算\(x\)的数位数字时要把前导零补上去。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; string s; cin >> n >> s; vector cnt(10, 0); for (auto& i : s) cnt[i - '0']++; LL ans = 0; int up = ceil(sqrt(9999999999999ll)); auto solve = [&](LL x) { vector num(10, 0); int sz = 0; while (x) { num[x % 10]++; x /= 10; ++sz; } if (sz > n) return 0; num[0] += (n - sz); return int(num == cnt); }; for (int i = 0; i < up; ++i) { ans += solve(1ll * i * i); } cout << ans << '\n'; return 0;}E – Joint Two Strings (abc324 E)题目大意
给定\(n\)个字符串 \(s_i\)和一个字符串 \(t\)，长度为\(m\)，问有多少组 \((i, j)\)，使得拼接串 \(s_is_j\)包含 \(t\)这个子序列。
解题思路
我们先枚举\(s_i\)，贪心匹配这个子序列 \(t\)，它可能不能完全匹配上，但能匹配 \(t\)的前 \(x\)位。
那剩下的\(m-x\)位就交给 \(s_j\)匹配，如果 \(s_j\)能至少匹配 \(t\)的后面\(m-x\)位，则拼接串\(s_is_j\) 就包含\(t\)这个子序列。
因此对于字符串\(s_i\)，它能匹配串 \(t\)的前 \(x\)位，我们要找出串 \(s_j\)的数量，可以匹配串 \(t\)的至少后\(m-x\)位，这个数量就是当前串\(s_i\)的贡献。即 \((i,*)\)的数量。
而对于字符串\(s_j\)能匹配 \(t\)的后面多少位，其实把它们反串一下贪心匹配即可。
因此就预处理每个串能匹配串\(t\)的 前缀位数和后缀位数，然后枚举每个串的匹配的前缀位数，找到要完全匹配\(t\)需要的后缀位数，大于该位数的都可以作为\(j\)的候选，累计数量即可。因此把后缀位数的个数预处理一下即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; string t; cin >> n >> t; int len = t.size() + 1; vector cnt(len, 0), invcnt(len, 0); string invt = t; reverse(invt.begin(), invt.end()); auto check = [](const string& s, const string& t, vector& cnt) { int l = 0, r = 0; while (l < s.size()) { while (r < t.size() && s[l] != t[r]) ++r; if (r < t.size()) { ++l; ++r; } else break; } cnt[l]++; }; for (int i = 0; i > s; check(t, s, cnt); reverse(s.begin(), s.end()); check(invt, s, invcnt); } LL ans = 0; reverse(invcnt.begin(), invcnt.end()); partial_sum(invcnt.begin(), invcnt.end(), invcnt.begin()); for (int i = 0; i < len; ++i) { ans += 1ll * cnt[i] * invcnt[i]; } cout << ans << '\n'; return 0;}F – Beautiful Path (abc324 F)题目大意
给定一张有向无环图，边有两种边权\(b,c\)，求一条从 \(1\)到 \(n\)的路径，使得 \(\frac{\sum b}{\sum c}\) 最大。
解题思路
初想时发现最短路的想法不太行，即时刻保留比值最大的往后扩展并不会最优的，比如此时同样是\(\frac{4}{2}, \frac{8}{4}\) ，后者值的变化的程度不如前者，又比如\(\frac{100}{99},\frac{1}{2}\)，后者受\(b\)的权值影响更大 ，万一下一条边权是\((100,0)\)，显然原先较小的权值会变得更大。
注意到这是一个分式形式，属于典型的\(0/1\)规划问题。我们可以二分答案\(l\)，判断是否可行，即 \(\frac{\sum b}{\sum c} \geq l\)，即\(\sum b – l\sum c \geq 0\)，即边权为 \(b – lc\)，问是否有条 \(1 \to n\)的路径，其边权和非负。
因为是有向无环图，设\(dp[i]\)表示到达 点\(i\)时的最大边权和 ，拓扑排序\(dp\)即可。
神奇的代码
#include using namespace std;using LL = long long;const int inf = 2e9;const double eps = 1e-10;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<array> edges; vector<vector> G(n); vector du(n); vector inque(n); for (int i = 0; i > u >> v >> b >> c; --u, --v; G[u].push_back(edges.size()); edges.push_back({u, v, b, c}); } queue team; team.push(0); inque[0] = 0; while (!team.empty()) { int u = team.front(); team.pop(); for (auto& i : G[u]) { int v = edges[i][1]; du[v]++; if (!inque[v]) team.push(v); inque[v] = 1; } } auto check = [&](double x) { vector dp(n, -inf); dp[0] = 0; team.push(0); auto dd = du; auto B = [](int b) { return b; }; auto C = [&x](int c) { return c * x; }; while (!team.empty()) { int u = team.front(); team.pop(); for (auto& i : G[u]) { auto [_, v, b, c] = edges[i]; dp[v] = max(dp[v], dp[u] + B(b) - C(c)); --dd[v]; if (dd[v] == 0) team.push(v); } } return dp[n - 1] >= -eps; }; double l = 0, r = 2e9; while (l + eps < r) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } cout << fixed << setprecision(12) << l << '\n'; return 0;}G – Generate Arrays (abc324 G)题目大意
给定一个关于\(n\)的排列，视为序列\(0\)，依次执行 \(m\)次操作，分两种：
- \(1 s x\)，将序列\(s\)的第 \(x\)个元素之后的元素（不包括第 \(x\)个）删除，放到一个新序列，相对位置不变。
- \(2 s x\)，将序列\(s\)中比\(x\)大的元素删除，放到一个新序列，相对位置不变。
问每次操作后，新生成的序列的个数。
解题思路
神奇的代码