A - TLD (abc339 A)
题目大意
给一个网址，问它的后缀是多少。
解题思路
找到最后的'.'的位置，然后输出后面的字符串即可。
python可以一行。
神奇的代码
print(input().split('.')[-1])B - Langton's Takahashi (abc339 B)
题目大意
二维网格，上下左右相连，左上原点。初始全部为白色，位于原点，面朝上。
进行\(n\)次操作，每次操作，将当前格子颜色黑白反转，然后
- 如果原来是白色，则顺时针旋转\(90\)度，前进一个格子。
- 如果原来是黑色，则逆时针旋转\(90\)度，前进一个格子。
解题思路
网格大小只有\(100 \times 100\)， \(n\)为 \(1000\)，每步模拟的复杂度是 \(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 h, w, n; cin >> h >> w >> n; vector<vector<int>> tu(h, vector<int>(w)); int x = 0, y = 0, dir = 0; array<int, 4> dx = {-1, 0, 1, 0}; array<int, 4> dy = {0, 1, 0, -1}; while (n--) { tu[x][y] ^= 1; if (tu[x][y] == 0) { dir = (dir - 1 + 4) % 4; } else { dir = (dir + 1 + 4) % 4; } x = (x + dx[dir] + h) % h; y = (y + dy[dir] + w) % w; } for (auto& i : tu) { for (auto& j : i) cout << ".#"[j]; cout << '\n'; } return 0;}C - Perfect Bus (abc339 C)
题目大意
公交车，经过很多公交站，依次给定每个公交站时公交车的变化人数，由于初始时公交车人数不知道，问最后公交车可能人数的最小值。注意途中不能有负数的人。
解题思路
最小化最终的人数相当于最小化最开始的公交车人数。
可以先假设一开始\(0\)人，然后模拟经过这些公交站的上下人数变化，维护最小值。
如果最小值\(min < 0\)，说明期间有公交车人数小于 \(0\)，即假定开始人数\(0\)不合法，太少了，需要更多的人，多多少呢？就是多\(-min\)人就足够了，这样最小值就是\(0\)，符合题目要求了。
如果\(min> 0\)，说明开始\(0\)人已经足够了，但又不能更小，因此最后的结果即为答案了。
神奇的代码
#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; LL minn = 0; LL sum = 0; while (n--) { int x; cin >> x; sum += x; minn = min(minn, sum); } LL ans = sum - minn; cout << ans << '\n'; return 0;}D - Synchronized Players (abc339 D)
题目大意
二维网格，有障碍物，两个人。
问最小的操作数，使得两人位于同一个格子。
操作为：选定上下左右一个方向，使两人均往同方向移动一格。如果目的地是障碍物或出界，则不动。
解题思路
网格大小只有\(60 \times 60\)，两人所处位置的状态数只有 \(60^4 = 10^7 < 5e8\)，此即为朴素搜索的复杂度上限，因此直接\(BFS\)即可。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;const int inf = 1e9 + 7;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<string> tu(n); for (auto& i : tu) cin >> i; array<int, 4> dx = {0, 0, 1, -1}; array<int, 4> dy = {1, -1, 0, 0}; typedef array<int, 4> s; queue<s> q; vector<int> dis(n * n * n * n, inf); s st; int cnt = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (tu[i][j] == 'P') { st[0 + cnt * 2] = i; st[1 + cnt * 2] = j; tu[i][j] = '.'; ++cnt; } } q.push(st); auto tr = [&](s x) { return x[0] * n * n * n + x[1] * n * n + x[2] * n + x[3]; }; dis[tr(st)] = 0; int ans = -1; auto ok = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && tu[x][y] != '#'; }; while (!q.empty()) { auto u = q.front(); int w = dis[tr(u)]; auto [x1, y1, x2, y2] = u; q.pop(); for (int i = 0; i < 4; ++i) { int nx1 = x1 + dx[i]; int ny1 = y1 + dy[i]; int nx2 = x2 + dx[i]; int ny2 = y2 + dy[i]; if (!ok(nx1, ny1)) { nx1 = x1; ny1 = y1; } if (!ok(nx2, ny2)) { nx2 = x2; ny2 = y2; } int v = tr({nx1, ny1, nx2, ny2}); if (dis[v] > w + 1) { dis[v] = w + 1; q.push({nx1, ny1, nx2, ny2}); } if (nx1 == nx2 && ny1 == ny2) { ans = dis[v]; break; } } if (ans != -1) break; } cout << ans << '\n'; return 0;}E - Smooth Subsequence (abc339 E)
题目大意
给定一个数组\(a\)和一个数\(D\)，删去若干个数，使得剩余数俩俩差不超过\(D\)。
问删去个数的最小值。
解题思路
考虑当前这个数\(a_r\)，如果要保留它，我们则要找到左边也保留的数\(a_l\)，且它们的差值不超过\(D\)，且 \([l+1,...,r-1]\)都要删去。
发现只用考虑上一个保留数在哪，这是个非常简洁的状态，且具有递归性，所以一个朴素的 \(dp[i] = \max_{j < i \& |a_j - a_i| \leq D}(dp[j]) + 1\)
朴素转移是\(O(n^2)\)，其中转移复杂度是 \(O(n)\)。
考虑优化转移。
注意到转移条件是一个经典的二维偏序问题，因此用线段树维护转移即可。下标是\(a_j\)，值是\(dp[j]\)。
即当前\(dp[j]\)求出来后，将 \(dp[j]\)插入到线段树里，即将 \(a_j\)位置的值赋予 \(dp[j]\)。
这样在求\(dp[i]\)时，线段树里的值都是 \(j < i\)的 \(dp[i]\)的值，自然满足第一个 \(j < i\)的条件，因为线段树的下标是 \(a_j\)，而 \(|a_j - a_i| \leq D\)相当于一个区间 \([a_i - D, a_i + D]\)，要求的就是这个区间的\(dp\)最大值，因为线段树维护的就是\(dp[j]\)，故区间查询最大值、单点修改即可。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;const int N = 5e5 + 10;class segment {#define lson (root << 1)#define rson (root << 1 | 1) public: int maxx[N << 2]; void build(int root, int l, int r) { if (l == r) { maxx[root] = 0; return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); maxx[root] = max(maxx[lson], maxx[rson]); } void update(int root, int l, int r, int pos, int val) { if (l == r) { maxx[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); maxx[root] = max(maxx[lson], maxx[rson]); } int query(int root, int l, int r, int ll, int rr) { if (ll > rr) return 0; if (ll <= l && r <= rr) { return maxx[root]; } int mid = (l + r) >> 1; int ans = 0; if (ll <= mid) ans = max(ans, query(lson, l, mid, ll, rr)); if (rr > mid) ans = max(ans, query(rson, mid + 1, r, ll, rr)); return ans; }} sg;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, d; cin >> n >> d; vector<int> a(n); for (auto& x : a) cin >> x; int maxa = ranges::max(a); sg.build(1, 1, maxa); int ans = 0; for (int i = 0; i < n; ++i) { int L = max(1, a[i] - d), R = min(a[i] + d, maxa); int dp = sg.query(1, 1, maxa, L, R) + 1; sg.update(1, 1, maxa, a[i], dp); ans = max(ans, dp); } cout << ans << '\n'; return 0;}F - Product Equality (abc339 F)
题目大意
给定\(n\)个数 \(a_i\)，问 \((i,j,k)\)的数量，使得 \(a_i \times a_j = a_k\)。
注意 \(a_i \leq 10^{1000}\)
解题思路
因为\(n \leq 1000\)，不考虑\(a_i\)大小的话，可以先统计\(cnt[i]\)表示值为 \(i\)的数量，然后 花 \(O(n^2)\)枚举 \(i,j\)，计算 \(a_i \times a_j\)，则对应的 \(k\)的数量即为 \(cnt[a_i \times a_j]\)。
而由于 \(a_i\)很大， \(a_i \times a_j\)的计算比较棘手，就算用 FFT也有\(1000\)的常数， \(O(n^3)\)过不了。
怎么办呢？考虑如何避免大数的计算，一个常用的手法就是取模。
如果\(a_i \times a_j = a_k\)，那么也有 \((a_i \% mo \times a_j \% mo) \% mo = a_k \% mo\)。
如果我们将模数 \(mo=1e9 + 7\)之类的数，那么取模后的结果就完全可以进行相乘，然后用上述的 \(O(n^2)\)枚举。
但是有可能原本不同的值取模后变成相同的值，注意相乘的结果个数是 \(O(10^6)\)，模数\(O(1e9)\)的话， 可能会出现的概率有点高，因此可以取两个模数，即双hash的方式。
这个想法跟\(2021ICPC\)济南的一题，给了行列式的绝对值，问其符号是正是负的解决方法是一样的，同样数很大不能直接算出，但由于正负的取模结果是不一样的，因此也是取模后计算比较。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;const LL mo1 = 954169327;const LL mo2 = 906097321;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<string> a(n); for (auto& i : a) cin >> i; auto mod1 = [&](string s) { LL ret = 0; for (auto& i : s) { ret = ret * 10 + (i - '0'); ret %= mo1; } return ret; }; auto mod2 = [&](string s) { LL ret = 0; for (auto& i : s) { ret = ret * 10 + (i - '0'); ret %= mo2; } return ret; }; vector<LL> b1(n), b2(n); map<LL, int> cnt1; map<LL, int> cnt2; for (int i = 0; i < n; ++i) { b1[i] = mod1(a[i]); cnt1[b1[i]]++; b2[i] = mod2(a[i]); cnt2[b2[i]]++; } LL ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { LL k1 = (b1[i] * b1[j]) % mo1; LL k2 = (b2[i] * b2[j]) % mo2; LL t1 = 0, t2 = 0; if (cnt1.count(k1)) { t1 = cnt1[k1]; } if (cnt2.count(k2)) { t2 = cnt2[k2]; } ans += min(t1, t2); } cout << ans << '\n'; return 0;}G - Smaller Sum (abc339 G)
题目大意
给定\(n\)个数 \(a_i\)，回答 \(q\)个询问。
每次询问给定 \(l, r, x\)，求\(\sum_{l \leq i \leq r \& a_i \leq x} a_i\)
强制在线。
解题思路
如果可以离线的话，莫队可以解决。
但这里强制在线，注意到求和式子同样是一个二维偏序问题。
我们可以先把上式拆成两式相减:
\[\sum_{i \leq r \& a_i \leq x} a_i - \sum_{i \leq l - 1 \& a_i \leq x} a_i\]
这个的形式就跟\(E\)题的转移式一模一样，只是这里是求和，E题的求最大值。
因此可以用线段树求解，下标是\(a_i\)，值也是 \(a_i\)。
但这里需要保存，维护了\([1,l-1]\)状态的线段树和\([1,r]\)状态的线段树 ，因此需要可持久化线段树，即主席树维护即可。
每次询问就两棵历史版本的线段树的一个区间查询的差就是答案。
时间复杂度是\(O(q\log \max a_i)\)
主席树板子是贴的，贴贴快乐
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;const int M = 1e6 + 8;const int ls = 1e9;namespace tree {#define mid ((l + r) >> 1)#define lson l, mid#define rson mid + 1, rconst int MAGIC = M * 30;struct P { LL sum; int ls, rs;} tr[MAGIC] = {{0, 0, 0}};int sz = 1;int N(LL sum, int ls, int rs) { if (sz == MAGIC) assert(0); tr[sz] = {sum, ls, rs}; return sz++;}int ins(int o, int x, LL v, int l = 1, int r = ls) { if (x < l || x > r) return o; const P& t = tr[o]; if (l == r) return N(t.sum + v, 0, 0); return N(t.sum + v, ins(t.ls, x, v, lson), ins(t.rs, x, v, rson));}LL query(int o, int ql, int qr, int l = 1, int r = ls) { if (ql > r || l > qr) return 0; const P& t = tr[o]; if (ql <= l && r <= qr) return t.sum; return query(t.ls, ql, qr, lson) + query(t.rs, ql, qr, rson);}} // namespace treeint main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> a(n); for (auto& x : a) cin >> x; vector<int> root(n); for (int i = 0; i < n; ++i) { root[i] = tree::ins(i ? root[i - 1] : 0, a[i], a[i]); } int q; cin >> q; LL ans = 0; while (q--) { LL l, r, x; cin >> l >> r >> x; l ^= ans; r ^= ans; x ^= ans; --l, --r; ans = tree::query(root[r], 1, x); if (l) ans -= tree::query(root[l - 1], 1, x); cout << ans << '\n'; } return 0;}