A - Tomorrow (abc331 A)
题目大意
给定一年的月数和一月的天数，以及当天日期，问次日的日期。
解题思路
一个简单的进制加法运算，超出进制数则向前加一。
神奇的代码
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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; ++k) {
if (i * 6 + j * 8 + k * 12 >= 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 <bits/stdc++.h>
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<LL> a(n);
for (auto& i : a)
cin >> i;
vector<LL> b = a;
ranges::sort(b);
vector<LL> 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 <bits/stdc++.h>
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<string> s(n);
for (auto& i : s)
cin >> i;
vector<vector<int>> sum(n, vector<int>(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 < 0)
return 0ll;
int row = x / n, col = y / n;
LL ans = 1ll * row * col * sum[n - 1][n - 1];
x %= n, y %= n;
ans += sum[x][y];
ans += 1ll * sum[n - 1][y] * row;
ans += 1ll * sum[x][n - 1] * col;
return ans;
};
while (q--) {
int a, b, c, d;
cin >> 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 <bits/stdc++.h>
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<int> a(n), b(m);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
set<array<int, 2>> forbid, used;
for (int i = 0; i < l; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
forbid.insert({x, y});
}
priority_queue<array<int, 3>> team;
vector<int> 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 <bits/stdc++.h>
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 << 2];
public:
void build(int root, int l, int r, string& s) {
if (l == r) {
hash[root] = (s[l - 1] - 'a');
return;
}
int mid = (l + r) >> 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 <= mid)
update(lson, l, mid, pos, val);
else
update(rson, mid + 1, r, pos, val);
hash[root] = hash[lson] * p[r - mid] % mo + hash[rson];
if (hash[root] >= mo)
hash[root] -= mo;
}
LL get(int root, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return hash[root];
}
int mid = (l + r) >> 1;
LL lval = 0, rval = 0;
if (L <= mid)
lval = get(lson, l, mid, L, R);
if (R > 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; ++i)
p[i] = p[i - 1] * base % mo;
int n, q;
string s;
cin >> 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\)个数字的期望抽取次数。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 331beginner atcoder contest 331 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327