A – Tomorrow (abc331 A)题目大意
给定一年的月数和一月的天数，以及当天日期，问次日的日期。
解题思路
一个简单的进制加法运算，超出进制数则向前加一。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int m, d; int Y, M, D; cin >> m >> d >> Y >> M >> D; ++D; if (D > d) { D = 1; ++M; } if (M > m) { M = 1; ++Y; } cout << Y << ' ' << M << ' ' << D << '\n'; return 0;}B – Buy One Carton of Milk (abc331 B)题目大意
给定\(6,8,12\)根胡萝卜的价格。
问买至少\(n\)根胡萝卜的最小花费。
解题思路
由于\(n\)只有\(100\)，花\(O(n^3)\)枚举这三类胡萝卜的购买次数，取花费最小值即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m, s, l; cin >> n >> m >> s >> l; int ans = 1e9 + 7; for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k = n) ans = min(ans, i * m + j * s + k * l); } cout << ans << '\n'; return 0;}C – Sum of Numbers Greater Than Me (abc331 C)题目大意
给定\(n\)个数，对于每个数，问比它大的数字的和。
解题思路
将这些数字排序，那么比这个数字大的数都在这个数字的一边，预处理前缀和，二分找到比这个数字大的位置，前缀和结果即为答案。
代码是找比这个数字小的。
神奇的代码
#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; vector b = a; ranges::sort(b); vector sum(n); partial_sum(b.begin(), b.end(), sum.begin()); LL all = accumulate(a.begin(), a.end(), 0ll); for (auto& i : a) { auto l = ranges::upper_bound(b, i); LL ans = all; if (l != b.begin()) ans -= (sum[l - b.begin() - 1]); cout << ans << ' '; } cout << '\n'; return 0;}D – Tile Pattern (abc331 D)题目大意
给定一个\(n \times n\)的包含 BW的二维网格，将这个网格平移复制平铺在无限大的平面上。
\(q\)次询问，每次询问 \([a,b] \to [c,d]\) 的矩形区域的B的数量。
解题思路
直接计算该区域的B数量会有很多边界条件考虑，考虑二维前缀和，设 \(sum(a,b)\)表示 \([0,0] \to [a,b]\)的矩形区域的 B数量，则\([a,b] \to [c,d] = sum(c,d) – sum(a – 1, d) – sum(c, b – 1) + sum(a – 1, b – 1)\) 。
对于\(sum(a,b)\)的计算， 分三部分考虑：
- 完整的\(n \times n\)的矩形数量，有 \(\lfloor \frac{a}{n} \rfloor \times \lfloor \frac{b}{n} \rfloor\)个这样的完整矩形，再乘以这个矩形的
B数量。 - \((a \% n) \times n\)的矩形数量，有 \(\lfloor \frac{b}{n} \rfloor\) 个，再乘以这个矩形的
B数量。 - \(n \times (b \% n)\)的矩形数量，有 \(\lfloor \frac{a}{n} \rfloor\) 个，再乘以这个矩形的
B数量。 - \((a \% n) \times (b \% n)\) 的矩形的
B数量。
求上述矩形的B的数量可以通过预处理关于B的二维前缀和\(O(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, q; cin >> n >> q; vector s(n); for (auto& i : s) cin >> i; vector<vector> sum(n, vector(n, 0)); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { sum[i][j] += (s[i][j] == 'B'); if (i) sum[i][j] += sum[i - 1][j]; if (j) sum[i][j] += sum[i][j - 1]; if (i && j) sum[i][j] -= sum[i - 1][j - 1]; } auto solve = [&](int x, int y) { if (x < 0 || y > a >> b >> c >> d; cout << solve(c, d) - solve(a - 1, d) - solve(c, b - 1) + solve(a - 1, b - 1) << '\n'; } return 0;}E – Set Meal (abc331 E)题目大意
给定数组\(a\)和数组 \(b\)，以及\(l\)个二元组\((a_i, b_j)\)，要求从中各选一个数出来，但不能是\((a_i, b_j)\)。问最大的和是多少。
解题思路
考虑求第\(k\)大和的做法，用优先队列维护当前的候选答案，当第\(k\)大被禁止时，就看第 \(k+1\)大，最坏情况下相当于求第 \(l+1\)大，复杂度是 \(O(l\log nm)\)
关于用优先队列求第\(K\)大的做法，先对两个数组降序排序，然后放入\((a_0 + b_0, 0, 0)\)。考虑我们取出的元素是 \((a_i + b_j, i, j)\)，当这个元素被禁止时，我们考虑它的后续答案，即 \((a_{i+1} + b_j, i + 1, j)\)和 \((a_i + b_{j + 1}, i, j + 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, m, l; cin >> n >> m >> l; vector a(n), b(m); for (auto& i : a) cin >> i; for (auto& i : b) cin >> i; set<array> forbid, used; for (int i = 0; i > x >> y; --x, --y; forbid.insert({x, y}); } priority_queue<array> team; vector ida(n), idb(m); iota(ida.begin(), ida.end(), 0); iota(idb.begin(), idb.end(), 0); ranges::sort(ida, [&](int x, int y) { return a[x] > a[y]; }); ranges::sort(idb, [&](int x, int y) { return b[x] > b[y]; }); team.push({a[ida[0]] + b[idb[0]], 0, 0}); used.insert({0, 0}); int ans = 0; while (!team.empty()) { auto [sum, x, y] = team.top(); team.pop(); if (forbid.find({ida[x], idb[y]}) == forbid.end()) { ans = sum; break; } if (x + 1 < n) { int X = x + 1, Y = y; if (used.find({X, Y}) == used.end()) { team.push({a[ida[X]] + b[idb[Y]], X, Y}); used.insert({X, Y}); } } if (y + 1 < m) { int X = x, Y = y + 1; if (used.find({X, Y}) == used.end()) { team.push({a[ida[X]] + b[idb[Y]], X, Y}); used.insert({X, Y}); } } } cout << ans << '\n'; return 0;}也可以线性的求法，对数组\(b\)降序排序，然后对于每个 \(a_i\)，找到第一个 未被禁止的 \((a_i, b_j)\)，作为一个候选答案。因为\(b\)是降序的，后续的 \(b\)一定是不优的。
对所有的 \(a_i\)的候选答案取最大值即为答案。这样的时间复杂度是 \(O(n + l)\)。
F – Palindrome Query (abc331 F)题目大意
给定一个字符串\(s\)，进行以下两种操作：
1 x c将\(s_x = c\)2 L R问\(s[l..r]\)是否是回文串。
解题思路
判断一个串是否是回文串，可以通过比较原串和反串（即reverse，翻转）是否一致。
对原串和反串分别进行字符串hash，可以\(O(1)\)获取某一子串的hash值，通过比较原串和反串的hash是否一致，即可知道是否是回文串。
考虑到操作一的修改，由于字符串hash是可合并的，用线段树维护字符串hash值即可。
线段树某一节点\(root\)，其信息为，该 \(root\)对应的子串的 hash值。两个相邻子串的hash值可以合并，得到整个串的hash值。
神奇的代码
#include using namespace std;using LL = long long;const LL mo = 998244353;const LL base = 13331;const int N = 1e6 + 8;LL p[N];class segment {#define lson root << 1#define rson root << 1 | 1 LL hash[N <> 1; build(lson, l, mid, s); build(rson, mid + 1, r, s); hash[root] = hash[lson] * p[r - mid] % mo + hash[rson]; if (hash[root] >= mo) hash[root] -= mo; } void update(int root, int l, int r, int pos, int val) { if (l == r) { hash[root] = val; return; } int mid = (l + r) >> 1; if (pos = mo) hash[root] -= mo; } LL get(int root, int l, int r, int L, int R) { if (L <= l && r > 1; LL lval = 0, rval = 0; if (L mid) rval = get(rson, mid + 1, r, L, R); return (lval * p[min(r - mid, max(0, R - mid))] % mo + rval) % mo; }} pre, suf;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); p[0] = 1; for (int i = 1; i > n >> q >> s; pre.build(1, 1, n, s); reverse(s.begin(), s.end()); suf.build(1, 1, n, s); while (q--) { int op; cin >> op; if (op == 1) { int pos; string c; cin >> pos >> c; pre.update(1, 1, n, pos, c[0] - 'a'); suf.update(1, 1, n, n - pos + 1, c[0] - 'a'); } else { int l, r; cin >> l >> r; LL L = pre.get(1, 1, n, l, r); LL R = suf.get(1, 1, n, (n - r + 1), (n - l + 1)); if (L == R) cout << "Yes" << '\n'; else cout << "No" << '\n'; } } return 0;}G – Collect Them All (abc331 G)题目大意
给定\(n\)张卡牌，每张卡牌写的数字 \(\in [1, m]\) 。
每次抽取一张，记录卡的数字，然后放回。
问记录了这\(m\)个数字的期望抽取次数。
解题思路
神奇的代码