## 公平合影（fairphoto）
#前缀和
首先按照位置从小到大排序。对于站在一段同样类型的同学，我们可以通过一个 $\mathcal O(n)$ 的双指针处理轻松解决。对于 $\texttt G$ 和 $\texttt H$ 类型数量相同的一段同学，我们可以令 $\texttt G$ 的值为 $1$、$\texttt H$ 的值为 $-1$，那么一段区间满足条件就等价于和为 $0$。
连续区间和考虑前缀和。令 $p_i=\sum\limits_{j=1}^i a_j$，那么如果一个区间 $[l,r]$ 满足条件就有 $p_r-p_{l-1}=0$，也就是 $p_r=p_{l-1}$。当我们枚举 $r$ 时，所有配对的 $l$ 中当然是越小越好，因此我们开一个桶记录最前面一个 $p_i$ 相同的 $i$。
时间复杂度 $\mathcal O(n)$。注意负数下标需要通过偏移或者 map 处理。
```cpp
#include <fstream>
#include <algorithm>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("fairphoto.in");
ofstream cout("fairphoto.out");
struct Node {
LL x;
char c;
} a[kMaxN];
LL p[kMaxN], lst[2 * kMaxN], n, ans;
LL &at(LL x) {
return lst[x + kMaxN];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].c;
}
sort(a + 1, a + n + 1, [](auto a, auto b) {
return a.x < b.x;
});
for (LL i = 1, j; i <= n; ) {
for (j = i; j <= n && a[i].c == a[j].c; j++) { }
ans = max(ans, a[j - 1].x - a[i].x);
i = j;
}
for (LL i = 1; i <= n; i++) {
p[i] = p[i - 1] + (a[i].c == 'G') - (a[i].c == 'H');
}
fill(begin(lst), end(lst), -1);
at(p[0]) = 0;
for (LL i = 1; i <= n; i++) {
if (at(p[i]) != -1) {
ans = max(ans, a[i].x - a[at(p[i]) + 1].x);
}
if (at(p[i]) == -1) {
at(p[i]) = i;
}
}
cout << ans << '\n';
return 0;
}
```
## 暗号解码（cipher）
#结论
首先字符集大小达到了 $26$，状压很难处理，我们需要找规律。通过猜测，可以找到规律：对于询问字符串 $r$ 中的任意一对字符 $(i,j)$，如果只保留 $s$ 和 $t$ 中 $(i,j)$ 的这两种字符仍然都相等，那么答案就是 $\texttt{Yes}$。
可以这样子感性证明，就是如果 $(\texttt a,\texttt b)$ 满足条件，且 $(\texttt b,\texttt c)$ 满足条件，且 $(\texttt a,\texttt c)$ 满足条件，那么 $\texttt a$ 相对于 $\texttt b$ 的位置和 $\texttt c$ 相对于 $\texttt b$ 的位置在 $s$ 和 $t$ 中都是一样的，$a$ 相对于 $c$ 的位置在 $s$ 和 $t$ 中也是一样的，所以 $(\texttt a,\texttt b,\texttt c)$ 的相对位置在 $s$ 和 $t$ 中也是一样的。
所以预处理 $(i,j)$ 是否满足条件就行了。时间复杂度 $\mathcal O(26^2(n + q))$。
```cpp
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
const int kMaxN = 1e5 + 5;
ifstream cin("cipher.in");
ofstream cout("cipher.out");
int a[kMaxN], b[kMaxN], f[26][26], n, m, q;
char s[kMaxN], t[kMaxN], d[kMaxN];
int main() {
cin.tie(0)->sync_with_stdio(0);
// 以下已更改，非赛事代码
string temp_s, temp_t;
cin >> temp_s >> temp_t;
strcpy(s + 1, temp_s.c_str());
strcpy(t + 1, temp_t.c_str());
// 更改结束。为解决 C++17 编译错误
n = strlen(s + 1);
m = strlen(t + 1);
for (int i = 0; i < 26; i++) {
for (int j = i; j < 26; j++) {
int c1 = 0, c2 = 0;
for (int k = 1; k <= n || k <= m; k++) {
if (k <= n) {
if (s[k] == i + 'a') {
a[++c1] = i;
} else if (s[k] == j + 'a') {
a[++c1] = j;
}
}
if (k <= m) {
if (t[k] == i + 'a') {
b[++c2] = i;
} else if (t[k] == j + 'a') {
b[++c2] = j;
}
}
}
f[i][j] = c1 == c2 && equal(a + 1, a + c1 + 1, b + 1);
}
}
for (cin >> q; q; q--) {
string temp_d;
cin >> temp_d;
strcpy(d + 1, temp_d.c_str());
int k = strlen(d + 1), ans = 1;
for (int i = 1; i <= k && ans; i++) {
for (int j = i; j <= k && ans; j++) {
ans &= f[d[i] - 'a'][d[j] - 'a'];
}
}
cout << (ans ? 'Y' : 'N');
}
return 0;
}
```
## 分组（grouping）
#CDQ #树状数组 #线段树 #前缀和
首先对于这种中位数的题目我们已经很有经验了，当然是把大于等于 $x$ 的数变成 $1$，小于 $x$ 的数变成 $-1$。至于和是要大于 $0$ 还是大于等于 $0$ 满足要求要看题目中对于中位数的定义，本题是大于等于 $x$ 的数不比小于 $x$ 的数少，因此是大于等于 $0$。
对处理后的数组做前缀和，枚举右端点 $r$，我们需要找出有多少个左端点 $l$ 满足 $p_{r}-p_{l-1}\ge 0$，也就是找寻二元组 $(i,j)$ 的数量，满足 $i<j$ 且 $p_i\le p_j$。这是典型的二维偏序，可以使用 CDQ 分治或者树状数组求解。我脑抽了写了个线段树，但是跑得也不慢。注意负数下标，需要通过离散化或者偏移来处理（其实写线段树可以不处理的）。
时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <fstream>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("grouping.in");
ofstream cout("grouping.out");
LL a[kMaxN], p[kMaxN], tr[8 * kMaxN], n, x, ans;
void modify(LL p, LL l, LL r, LL x) {
tr[p]++;
if (l == r) {
return;
}
LL m = (l + r) / 2;
if (x <= m) {
modify(2 * p, l, m, x);
} else {
modify(2 * p + 1, m + 1, r, x);
}
}
LL query(LL p, LL l, LL r, LL s, LL t) {
if (s <= l && r <= t) {
return tr[p];
}
LL m = (l + r) / 2, res = 0;
if (s <= m) {
res += query(2 * p, l, m, s, t);
}
if (m < t) {
res += query(2 * p + 1, m + 1, r, s, t);
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> x;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + (a[i] >= x) - (a[i] < x);
}
modify(1, 0, 2e5, p[0] + 1e5);
for (LL i = 1; i <= n; i++) {
ans += query(1, 0, 2e5, 0, p[i] + 1e5);
modify(1, 0, 2e5, p[i] + 1e5);
}
cout << ans << '\n';
return 0;
}
```
## 平衡小径（balance）
#点分治 #前缀和 #分治
本题我采用的是暴力。
首先枚举 $i$ 作为路径的起点，让后把 $i$ 当作根来统计就不用管复杂的带 LCA 的路径了。把黑色变成 $1$，白色变成 $-1$，那么一条路径如果和为 $0$ 就满足黑色数量等于白色的数量。做从 $i$ 开始的树上前缀和。对于一条路径，如果它最底下的前缀和值为 $0$，并且路径上有一个不同于端点的点前缀和值也为 $0$，那么这条路径就满足条件。
时间复杂度 $\mathcal O(n^2)$。注意答案最后要除以 $2$。成功获得 $50$ 分。
```cpp
#include <fstream>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("balance.in");
ofstream cout("balance.out");
LL p[kMaxN], n, ans;
vector<pair<LL, LL>> e[kMaxN];
void dfs(LL x, LL f) {
for (auto i : e[x]) {
if (i.first == f) {
continue;
}
p[i.first] = p[x] + (i.second == 1) - (i.second == 0);
dfs(i.first, x);
}
}
void solve(LL x, LL f, LL cnt) {
ans += cnt >= 2 && !p[x];
for (auto i : e[x]) {
if (i.first == f) {
continue;
}
solve(i.first, x, cnt + !p[i.first]);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
for (LL i = 1; i <= n; i++) {
p[i] = 0;
dfs(i, 0);
solve(i, 0, 0);
}
cout << ans / 2 << '\n';
return 0;
}
```
本题正解是点分治，每次找重心统计过重心的路径，然后把重心删了拆分成多棵树递归求解。最难的是统计路径数量，有点复杂，这里讲不下了。
## 总结
总分：$100+100+100+50=350$。
今天的比赛还是比较简单的，前三题都非常轻松地写出来了，第一题和第三题都是一眼题，第二题需要猜一下结论（应该也能证明的）。最后一题写出了 $50$ 分的 $\mathcal O(n^2)$ 暴力（虽然 $\mathcal O(n^3)$ 也能过 $50$ 分，因为随机树高期望 $\log_2 n$ 路径长最多 $2\log_2 n$），但是迫于不会点分治导致无法 AC。所以还是太菜了，高级算法涉及少了。