区域赛有点赶，晚点会重制一下。
A 小红的正方形
知识点：距离
按顺时针给出的前两个顶点 $(x_1,y_1),(x_2,y_2)$ 是正方形上相邻的两点，它们连成一条平行于坐标轴的边，所以两个坐标里恰有一个相同，另一个之差就是边长。
时间复杂度 $\mathcal O(1)$。
void solve() {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << max(abs(x1 - x2), abs(y1 - y2)) << endl;
}B 小红的字符串压缩
知识点：模拟、哈希
前半部分是经典的字符串压缩，然后对结果串进行计数即可。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n;
string s;
cin >> n >> s;
string r;
char p = s[0];
int c = 1;
for (int i = 1; i < n; ++i) {
if (s[i] == p)
c++;
else
r += p + to_string(c), p = s[i], c = 1;
}
r += p + to_string(c);
array<int, 255> f{};
int mx = 0;
for (auto v : r) mx = max(mx, ++f[v]);
for (int i = 0; i < 255; ++i)
if (f[i] == mx) cout << (char)i;
cout << endl;
}C 小红的灯
知识点：调和数列、约数、模拟
法 $\tt 1$：
检查每一个 $i$，如果把所有的 $2$ 和 $3$ 的质因子都除掉，剩余的结果为 $1$，那么 $i$ 就是一个形如 $2^a3^b$ 的数字，进行更新就行了。
假设每一个 $i$ 都符合 $x = 2^a3^b$，更新时间复杂度是 $\sum \frac{n}{i} \approx n\ln n$，因此必然不会 $\tt TLE$，直接模拟即可。
时间复杂度 $\mathcal O(n(\log ^2n + \log n))$。
void solve() {
int n;
cin >> n;
vector<int> f(n + 1);
for (int i = 1; i <= n; ++i) {
int t = i;
while (t % 2 == 0) t /= 2;
while (t % 3 == 0) t /= 3;
if (t != 1) continue;
for (int j = i; j <= n; j += i) f[j] ^= 1;
}
cout << count(f.begin(), f.end(), 1) << endl;
}法 $\tt 2$：
我们考虑一个整数 $x=2^a3^bm, \gcd(m, 6) = 1$，那么它的形如 $2^x3^y$ 的因子有 $(a+1)(b+1)$ 个。如果这盏灯最后是亮着的，必然有 $(a+1)(b+1)$ 为奇数，也就是 $a,b$ 均为偶数。为了方便代码，我们不妨将 $x=2^a3^bt$ 写成 $x=4^p9^q$，此时 $p,q$ 可以取 $1,2,\dots$。
对于每一个可能的 $4^p9^q$，我们来计算符合要求的 $m$ 的数量，也就是求 $\le \lfloor\frac{n}{4^p9^q}\rfloor$ 中，与 $6$ 互质的数字个数。根据容斥原理，在 $n$ 以内符合要求的数字有 $t – \frac t 2 – \frac t 3 + \frac t 6$，其中 $t = \lfloor\frac{n}{4^p9^q}\rfloor$，枚举并进行求和即可。
时间复杂度 $\mathcal O(\log ^2 n)$。
void solve() {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i *= 4) {
for (int j = 1; i * j <= n; j *= 9) {
int t = n / (i * j);
ans += t - t / 2 - t / 3 + t / 6;
}
}
cout << ans << endl;
}D 小红跑步
知识点：模拟、图论
每个道路恰好有两个邻居，说明指定方向后道路是唯一的，所以难点只剩如何确定方向。
我们不妨取到路上最左上角的任意一个点，此时它只有下方和右方有相邻的道路，那么下方的一定是前一个点，右方的一定是后一个点。处理顺时针方向下，所有点到这个点的距离，然后取环上两点间距离即可。
时间复杂度 $\mathcal O(nm)$。
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void solve() {
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto &v : g) cin >> v;
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
--x1, --y1, --x2, --y2;
int x = 0, y = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (g[i][j] == '*') {
tie(x, y) = {i, j};
break;
}
auto check = [&](int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; };
auto next = [&](int x, int y, int px, int py) -> tuple<int, int, int, int> {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (check(nx, ny) && g[nx][ny] == '*' && !(nx == px && ny == py)) return {nx, ny, x, y};
}
return {-1, -1, -1, -1};
};
vector d(n, vector<int>(m));
auto [sx, sy] = pii{x, y};
int px, py;
tie(x, y, px, py) = next(x, y, x, y);
int L = 1;
while (!(x == sx && y == sy)) {
d[x][y] = L++;
tie(x, y, px, py) = next(x, y, px, py);
}
cout << (d[x2][y2] - d[x1][y1] + L) % L << endl;
}E 小红加边
知识点：树形 DP、计数
不难发现，如果在 $(u, v)$ 之间加了一条边，那么对应的基环树的环长为 $dist(u, v) + 1$，所以我们只需要求满足 $dist(u, v)\equiv 2\pmod 3$ 的无序点对 $(u, v)$ 的数量。
对于每一个节点，我们维护它的每一棵子树，$\equiv 2$ 的情况必然是从 $(0, 2),(1,1),(2,0)$ 的其中一种转移过来的，树形 $\tt dp$ 求解即可。用 $f[u][r]$ 表示子树内到 $u$ 距离模 $3$ 余 $r$ 的点数，初值 $(1,0,0)$。合并儿子 $v$ 时，$v$ 子树里的点到 $u$ 的距离都加了 $1$，桶要循环移位成 $(c_2,c_0,c_1)$；先与已合并的部分配对，余数和为 $2$ 即 $c_0f_2+c_1f_1+c_2f_0$，再并入 $f$。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 0;
auto dfs = [&](auto &&self, int u, int fa) -> array<int, 3> {
array<int, 3> f = {1, 0, 0};
for (auto v : g[u]) {
if (v == fa) continue;
auto c = self(self, v, u);
c = {c[2], c[0], c[1]};
ans += c[0] * f[2] + c[1] * f[1] + c[2] * f[0];
f[0] += c[0], f[1] += c[1], f[2] += c[2];
}
return f;
};
dfs(dfs, 1, 0);
cout << ans << endl;
}F 小红的排列构造
知识点：构造、贪心
$n$ 以内恰有 $\lfloor n/2\rfloor$ 个偶数，两个偶数的 $\gcd\ge2$，所以让偶数落在「$a_i$ 或 $b_i$ 是偶数」的位置上就能凑够达标数量。记这些位置为 $S$：$a$ 中 $a_i$ 为偶数的位置有 $\lfloor n/2\rfloor$ 个，$b$ 中同理，并集只会更多。剩余 $\lceil n/2\rceil$ 个位置用奇数填，只需要保证 $p_i \neq a_i && p_i \neq b_i$。
每个位置只禁两个值，按值从小到大贪心挑一个空闲位置 $v$，只要求 $a_v,b_v$ 都不等于当前值。当某个值 $i$ 的空位恰好是它在 $a$、$b$ 中出现的两个位置时，取最小空位 $f$，在已填位置里找一个 $v$，要求 $i$ 能放在 $v$、且 $p_v$ 能放到 $f$，把 $p_v$ 挪到 $f$、$i$ 放在 $v$。
无解的情况只发生在小数据下（没有空位了），所以 $n\le 9$ 的时候暴力枚举进行求解。
时间复杂度 $\mathcal O(n\log n)$。
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n), p(n);
for (auto &v : a) cin >> v;
for (auto &v : b) cin >> v;
auto check = [&]() {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == p[i] || b[i] == p[i]) return false;
cnt += __gcd(a[i], p[i]) > 1 || __gcd(b[i], p[i]) > 1;
}
return cnt >= n / 2;
};
if (n <= 9) {
iota(p.begin(), p.end(), 1);
do {
if (check()) {
for (auto v : p) cout << v << " ";
return cout << endl, void();
}
} while (next_permutation(p.begin(), p.end()));
return cout << -1 << endl, void();
}
vector<int> pa(n + 1), pb(n + 1);
for (int i = 0; i < n; ++i) pa[a[i]] = i, pb[b[i]] = i;
vector<int> S, R;
for (int i = 0; i < n; ++i)
if (a[i] % 2 == 0 || b[i] % 2 == 0) S.push_back(i);
auto fill = [&](const vector<int> &c, int s) {
set<int> F(c.begin(), c.end());
for (int i = s; i <= n; i += 2) {
int q = -1;
for (auto v : F)
if (v != pa[i] && v != pb[i]) {
q = v;
break;
}
if (q >= 0) {
p[q] = i, F.erase(q);
continue;
}
int f = *F.begin();
for (auto v : c)
if (p[v] && v != pa[i] && v != pb[i] && p[v] != a[f] && p[v] != b[f]) {
swap(p[f], p[v]), p[v] = i, F.erase(f);
break;
}
}
};
fill(S, 2);
for (int i = 0; i < n; ++i)
if (!p[i]) R.push_back(i);
fill(R, 1);
for (auto v : p) cout << v << " ";
cout << endl;
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}使用到的算法仓库见 $\tt Github$ 仓库 林月的XCPC模板库