传送门
tricks from
- 对多元组的哈希，先使用布隆过滤器判断其中某个元素是否存在，可大大加快代码速度。
A（布隆过滤器）
直接预处理出 \(n^2\) 对点的距离，将三元组塞进 map 然后查询即可。喜提最劣解
发现查询个数远小于点对数，考虑改用 umap 记录查询的三元组再枚举点对，哈希函数自己写。同时用两个布隆过滤器判断 \(c\) 有没有出现过，减少 umap 访问次数。跑的极快且码量增加不大。快了 100 倍的 code
E
行进方式一定是走一段再回头，走一段再回头的形式。考虑 DP，转移时枚举上一段的结束位置，贡献提前计算，对当前段的数取来时治与回头再治两种形式的 min。倒序枚举可以 \(o(n^2)\)。code
F
矩阵乘法。code
G
大胆猜测只有长为 \(1\) 的链 Alice 才赢。由 sg 定理答案即为选奇数个 \(1\) 的方案数。[code]https://qoj.ac/submission/2042266)
证明：设链长为 \(n\)。若 \(n\) 为偶数，Alice 放 \(k\)，Bob 就放 \(n-k+1\)，Bob 必胜。
若 \(n\) 为 \(>1\) 的奇数：
- Alice 放 \(k \neq \frac{n+1}{2}\)。同上，Bob 放 \(n+1-k\)。
- Alice 放 \(k =\frac{n+1}{2}\)，\(k-2\) 和 \(k+2\) 均放不了（已被放或不存在），Bob 从 \(k-1\) 和 \(k+1\) 中选一个能放的（显然一定存在），则 Alice 一定放不了另一个。然后重复 1。
- Alice 放 \(k =\frac{n+1}{2}\)，\(k-2\) 和 \(k+2\) 可以放（显然如果为空就一定可放），就放那个能放的位置。然后重复 1，2。（若 Alice 放了 \((k-2,k+2)\) 中另一个位置，则重复 2）
H
code
I
先考虑只有 \(1\) 和 \(2\) 怎么做，把 \(1\) 在前缀堆着，\(2\) 在后缀堆着即可。
考虑加了 \(3\) 之后把 \(3\) 在后缀堆着，\(2\) 在中间单独一段。我们可以用一次移动让 \(2\) 的块向左/右平移 \(2\) 个长度，如果需要加一个 \(3\) 最多两次移动。由于最多有 \(n-1\) 个格子是满的，正确性可以保证。code
J
固定右端点，字母种类数一定单调不降。记录每个字母最后依次出现的位置，排序后即可求出每个极长左端点减 \(1\)，答案最后统计。使用基数排序可以做到 \(O(n|\Sigma|)\)（还真有人写)，但即使普通排序也比大常数的 set/map 做法快很多。STL sort code