| rank | solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 102 | 7 | O | Ø | . | . | Ø | O | . | Ø | Ø | O |
A
Solved by XLor (01:39:24, +2).
注意到字符集只有 $2$。
考虑重载两个后缀的比较函数。显然每个后缀必然以 aa...ab 或 bb...ba 开头，如果开头重复的字符数量不同，那么必然有一个出现了 $0$ 可以直接比较；否则，对两个的剩余后缀进行比较，此时两个后缀的同构串就是原串的同构串，因此只需要对原串的同构串后缀排序即可。
B
UpSolved by ytriayggg and XLor.
定义一棵无穷的树，点 $x$ 的父亲为 $x \over \text{mindivsor}(x)$。
给定 $1!, 2!, \dots, n!$ 这些关键点，求一个点使得它关键点的带权距离和最小。
注意到目标点应该在关键点的虚树上，建出这棵虚树后，求一下带权重心。
可以观察到根 $1$ 到每个点的路径上途径乘的质数是不断减小的，树上两个点的 LCA 就是两个点很多公共的最大质因子，从某个位置开始质因子出现不同导致结点的分叉。
对 $1!, 2!, \dots, n!$ 这些关键点建立虚树，需要知道 $i!$ 和 $(i-1)!$ 的 LCA（深度），那么必然是从 $i$ 的最大质因子开始变化。维护 $(i-1)!$ 每个质数位置的个数，深度就是 $i$ 的最大质因子到最大值这个区间内的个数和，类似地构建出虚树。
构建出虚树后，求带权重心，可以先计算根结点的答案然后贪心地往下走。
E
UpSolved by miaojie.
F
Solved by XLor (00:23:55, +2).
比较一下长度为 $n+m-\gcd(n,m)$ 的无穷串即可。
H
UpSolved by XLor (-24).
注意到所有边的容量相同，因此在求最大流时，每轮增广必定就是切除掉一些边。
第一次，就是原图的最短路，切除这个最短路后，依此类推。
询问，设置每条边容量为 $u \over v$，跑出流量为 $1$ 的最小费用，那么只需要知道需要增广几次，最后一次增广时，多用了多少流量，容易计算。
注意：计算答案时可能爆整数范围，建议小心谨慎。
I
UpSolved by miaojie (-1).
一般图匹配，带花树算法。
J
Solved by ytriayggg (00:20:55).
OEIS。