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\) 小，一个是求小于某个数的数的和。
于是稍作修改即可（指将计数改为加上代表的值，然后查询和普通线段树差不多）。
代码
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 ll
const 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 ll
const 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 ll
const 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 ll
const 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;
}