ABC339 题解（A~G） - adam01 - 博客园 (2024)

A

从后向前找到第一个 . 就行了。

B

按照题意模拟，设当前位置 \(x, y\) 移动方向 \(dx, dy\)。那么下一步为 \((x+dx,y+dy)\)

设新的移动方向为 \(dx',dy'\)

如果顺时针旋转，则有 \(dy'\gets -dx, dx'\gets dy\)；

如果逆时针，则有 \(dx'\gets -dy, dy'\gets dx\)。

C

鉴定为除 A 以外第一简单。

设原来没有乘客，按题意模拟找到乘客人数 \(x\) 的最小值 \(x_{min}\)，最后乘客个数 \(x_n\)。

当然，开始时的乘客不能是负数。

于是有 \(ans=x_n+max(0,-x_{min})\)

D

比 EFG 难（

注意到状态数最多只有 \(60^4\)，每次转移代价是 1，每个状态可以向另外 4 个状态转移，于是直接 bfs，复杂度为 \(O(n^4)\)。

但是一开始以为最终情况只能是棋子被移到边界处才能重合，喜提一发法师。

可以考虑把两个棋子四个坐标压成一个整数储存，然后就是普通 bfs。

E

显然有基础的 dp：\(f_i=\max\limits_{1\le j\le n,a_j\in[a_i-d,a_i+d]}f_j+1\)。但是复杂度 \(O(n^2)\)，过不了。

考虑线段树优化 dp。

表示 \([l,r]\) 的结点存 \(\max\limits_{a_i\in[l,r]}f_i\)。修改和查询显然。

时间复杂度为 \(O(n\log n)\)。

F

最简单想法是枚举 \(i,j\)，用 map 存储 \(A_k\) 的值，实现 \(O(n^2)\) 或 \(O(n^2\log n)\)。

但是注意到 \(A_i\le 10^{1000}\)。高精度乘法 \(O(n\log n)\)（最快）复杂度也要上天（\(O(n^3\log n)\)） 考虑能不能把数变小。考虑取模。

把这串数 \(A_i\) 分别模大质数 \(p_j\)，得到 \(a_{i,j}\)。

因为 \(A_i\times A_j = A_k \Rightarrow \forall o,a_{i,o}\times a_{j,o} \equiv a_{k,o} \bmod p_j\)。

但是 \(\exists A_i\times A_j \neq A_k, a_{i,o}\times a_{j,o} \equiv a_{k,o} \bmod p_j\)？

毕竟概率很小。

因为 Atcoder 不卡模数 只要模两到三个大质数，错误率就会很低，所以使用 pair<long long, long long> 或 tuple<int, int, int> 存储一个数模 2 或 3 个大质数后的值。

然后就用一开始的方法愉快过题。复杂度还是 \(O(n^2)\) 或 \(O(n^2\log n)\)。

G

板，太板了。二维数点板子。

先过 Luogu P3834。

注意到，这题 比 P3834 简单 和 P3834 的区别在于一个求第 \(k\) 小，一个是求小于某个数的数的和。

于是稍作修改即可（指将计数改为加上代表的值，然后查询和普通线段树差不多）。

upd: G 题解用的是 merge-sort tree，长见识了（但是好像用处不大？）。

upd2: F 可以 python 暴力？？？

代码

A

#include<bits/stdc++.h>using namespace std;typedef long long ll;signed main(){ ios::sync_with_stdio(0);cin.tie(0); string s; cin >> s; reverse(s.begin(), s.end()); string ans; for(char c : s) { if(c == '.') break; ans += c; } reverse(ans.begin(), ans.end()); cout << ans; return 0;}

B

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 105;int col[N][N], n, m, q;signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin >> n >> m >> q; int x = 1, y = 1, dx = -1, dy = 0; while(q --) { if(!col[x][y]) { col[x][y] = 1; int nx = dy, ny = -dx; dx = nx, dy = ny; } else { col[x][y] = 0; int nx = -dy, ny = dx; dx = nx, dy = ny; } x = (x + dx + n - 1) % n + 1; y = (y + dy + m - 1) % m + 1; } for(int i = 1; i <= n; i ++, cout << "\n") for(int j = 1; j <= m; j ++) { if(col[i][j]) cout << "#"; else cout << "."; } return 0;}

C

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define int llconst int N = 2e5 + 5;int a[N], mn = 0, n;signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin >> n; int now = 0; for(int i = 1; i <= n; i ++) { cin >> a[i]; now += a[i]; mn = min(mn, now); } cout << -mn + now; return 0;}

D

#include<bits/stdc++.h>using namespace std;typedef long long ll;struct node {int x[2], y[2];};const int B = 60, N = 65;int n; char a[N][N];node decode(int o) { int x, y, u, v; v = o % B; o /= B; u = o % B; o /= B; y = o % B; o /= B; x = o % B; return {{x, u}, {y, v}};}inline int encode(int x, int y, int u, int v){ return ((x * B + y) * B + u) * B + v;}int dis[B * B * B * B];int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};inline bool chk(int x, int y){ return x >= 0 && x < n && y >= 0 && y < n && a[x][y] != '#';}void bfs(int f){ memset(dis, 0x3f, sizeof dis); dis[f] = 0; queue<int> q; q.push(f); while(q.size()) { int t = q.front(); q.pop(); node o = decode(t); for(int i = 0; i < 4; i ++) { int x = o.x[0], y = o.y[0], u = o.x[1], v = o.y[1]; if(chk(x + dx[i], y + dy[i])) x += dx[i], y += dy[i]; if(chk(u + dx[i], v + dy[i])) u += dx[i], v += dy[i]; int id = encode(x, y, u, v); if(dis[id] > dis[t] + 1) { dis[id] = dis[t] + 1; q.push(id); } } }}signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin >> n; int x, y, u, v, cnt = 0; for(int i = 0; i < n; i ++) { cin >> a[i]; for(int j = 0; j < n; j ++) { if(a[i][j] == 'P') { if(cnt == 1) u = i, v = j; else x = i, y = j, cnt ++; } } } bfs(encode(x, y, u, v)); int ans = 2e9; for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) { ans = min(ans, dis[encode(i, j, i, j)]); } if(ans > 1e9) cout << -1; else cout << ans; return 0;}

E

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define int llconst int N = 5e5 + 5;struct sgt{ int a[N << 2]; void pu(int x) {a[x] = max(a[x << 1], a[x << 1 | 1]);} void upd(int q, int l, int r, int x, int v) { if(l == r) return a[x] = max(a[x], v), void(); int mid = l + r >> 1; if(mid >= q) upd(q, l, mid, x << 1, v); else upd(q, mid + 1, r, x << 1 | 1, v); pu(x); } int qry(int ql, int qr, int l, int r, int x) { if(ql <= l && r <= qr) return a[x]; int mid = l + r >> 1, ans = 0; if(mid >= ql) ans = max(ans, qry(ql, qr, l, mid, x << 1)); if(mid < qr) ans = max(ans, qry(ql, qr, mid + 1, r, x << 1 | 1)); return ans; }}t;int f[N], n, a[N], d;const int V = 5e5;signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin >> n >> d; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++) { f[i] = t.qry(max(1ll, a[i] - d), min(V, a[i] + d), 1, V, 1) + 1; t.upd(a[i], 1, V, 1, f[i]); } int ans = 0; for(int i = 1; i <= n; i ++) ans = max(ans, f[i]); cout << ans; return 0;}

F

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define int llconst int N = 1005;int p[2] = {100000000001423ll,100000000001467ll};map<pair<int, int>, int> mp;int n, a[N][2];int getnum(string &s, int p){ int x = 0; for(char c : s) x = (x * 10 + c - '0') % p; return x;}signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin >> n; for(int i = 1; i <= n; i ++) { string s; cin >> s; a[i][0] = getnum(s, p[0]); a[i][1] = getnum(s, p[1]); mp[{a[i][0], a[i][1]}] ++; } int ans = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { int x = (__int128) a[i][0] * a[j][0] % p[0]; int y = (__int128) a[i][1] * a[j][1] % p[1]; if(mp.count({x, y})) ans += mp[{x, y}]; } } cout << ans; return 0;}

G

#include<bits/stdc++.h>using namespace std;typedef long long ll;#define int llconst int N = 2e5 + 5;struct sgt{ int idx, a[N << 5], ls[N << 5], rs[N << 5], rt[N]; void pup(int x) {a[x] = a[ls[x]] + a[rs[x]];} int nw(int &x) {return x ? x : x = ++idx;} int upd(int q, int l, int r, int x) { int u = ++idx; a[u] = a[x]; ls[u] = ls[x], rs[u] = rs[x]; if(l == r) return a[u] += l, u; int mid = l + r >> 1; if(mid >= q) ls[u] = upd(q, l, mid, ls[x]); else rs[u] = upd(q, mid + 1, r, rs[x]); pup(u);return u; } int qry(int ql, int qr, int l, int r, int xl, int xr) { if(ql <= l && r <= qr) return a[xr] - a[xl]; int mid = l + r >> 1, ans = 0; if(mid >= ql) ans += qry(ql, qr, l, mid, ls[xl], ls[xr]); if(mid < qr) ans += qry(ql, qr, mid + 1, r, rs[xl], rs[xr]); return ans; }}t;int n, q, a[N];const int V = 1e9;signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin >> n; for(int i = 1; i <= n; i ++) { cin >> a[i]; t.rt[i] = t.upd(a[i], 0, V, t.rt[i - 1]); } cin >> q; int la = 0; while(q --) { int l, r, k;cin >> l >> r >> k; l ^= la, r ^= la, k ^= la; cout << (la = t.qry(0, k, 0, V, t.rt[l - 1], t.rt[r])) << "\n"; } return 0;}