2025.8.6 比赛记录
__vector__
·
·
个人记录
Contest link
很遗憾没有 AK 比赛，原因在于 T4 我把 vector 当成了 set 用（排序是算法正确的基础之一），以及忘了处理取余结果为负数。
不过两位 hdu 队友以及 Cubber 都 AK 了，膜拜！！！！
T1
签到题。
注意到，推导最需要的信息包括 a 的最大值和 b 的总和，想要得到的信息是选择方案数。
首先，将所有 (a_i,b_i) 按照 a 升序排列。
令 f_{i,j} 表示最大值不超过 a_i，且总和为 j 的方案数。
然后，最大值确定为 $i$，总和为 $j$ 的方案数则是 $f_{i,j}-f_{i-1,j}$。
然后暴力枚举最大值，总和，算出对应方案数总和。
时间复杂度 $O(n^2)$。
### T2
和 T1 难度近似，但是存在一些误区会把一些比较幸运的人（比如我）引进去。
注意到，这实际上和括号匹配是类似的。
令 $f_{l,r}$ 表示 $[l,r]$ 区间内部完成匹配的操作方案数。
转移的话，则可以枚举 $r$ 匹配哪个位置，假设 $r$ 匹配位置 $x$，那么分别求解 $[l,x-1],[x+1,r-1]$ 的答案，然后将两个区间的答案合并。
两个区间的答案并不能简单的相乘，因为两个区间的操作顺序是互相独立的，每种不同的归并顺序都是一种新的方案。
两个区间实际上分别有 $\frac{x-l}{2},\frac{r-x}{2}$ 个元素，假设分别已经确定了顺序，每次可以在两个区间中任意选一个删掉，现在想要知道删完两个序列的方案数。
这个也是可以预处理的，$g_{i,j}$ 表示两个长度分别为 $i,j$ 的序列的归并方案数，$O(n^2)$ 暴力递推可以得到答案。
最终解法总复杂度为区间 DP $O(n^3)$ 加上预处理 $g$ 的 $O(n^2)$，即 $O(n^3)$。
### T3
考虑一下什么时候最短路才会变化。
注意到，如果删除的边不在最短路上，那么一定不会改变最短路，可以直接跳过。
但是实际上可能有多条最短路，最短路上的边的数量同样可能到达 $O(n^2)$ 量级。
但是，注意到其实，只选择一条最短路，~~按住~~钦定其上的边为最短路上的边就可以了，因为只要有一条最短路仍然没断开，那么最短路长度仍然不会变化。
此时，只有 $O(n)$ 条边断开可能产生影响，每次 BFS $O(n^2)$ 计算新的最短路，可以通过。
### T4
首先，观察一下最终走过的点的坐标形式都是什么。
令前 $n-1$ 次移动到达的点的位置集合（包括一开始的 $(0,0)$）为 $S$，第 $n$ 次移动后的点的位置为 $(dx,dy)$。
那么，对于所有 $Kn$ 次移动中到达过的点 $(x,y)$，必然满足以下两种情况至少一个：
- 存在一个非负整数 $k \lt K$，以及 $(sx,sy) \in S$，使得 $(sx+k\cdot dx,sy+k\cdot dy) = (x,y)
- 存在一个非负整数 k \le K，使得 (x,y) = (k\cdot dx,k\cdot dy)
换个理解方式，就是对于任意 (x,y) \in S,0 \le k \lt K，(x+k\cdot dx,y + k \cdot dy) 必然存在于最终经过的路径里，对于任意 k \le K，(k\cdot dx,k \cdot dy) 也必然存在于最终经过的路径里。
首先，由于我不喜欢比较重要的地方出现负数，所以，如果 dx,dy 某一个小于 0，那么就将整个的对应的横向或纵向翻转（比如说，U 换成 D，L 换成 R）。
答案一定不会改变，因为是对称的，然后，就能保证 dx,dy \ge 0。
然后，考虑按照顺序遍历 S 中的每个元素，依次考虑遍历到的新元素，事实上对答案新增了多少个位置的贡献。
此时，就需要分析怎么计算当前的元素产生的位置里面，有哪些是和之前遍历过的元素产生的位置重复了。
回想一下判定条件。
假设当前扫描到了 S 中的元素 (x_1,y_1)，然后需要知道其与 S 中另一个元素 (x_2,y_2) 有哪些位置重合。
- 首先，需要满足 \frac{x_1-x_2}{dx} = \frac{y_1-y_2}{dy}
本条件的原因是，加上的 dx,dy 分别乘上的倍数都是相等的。
本条件可以转化为 x_1\cdot dy - y_1 \cdot dx = x_2 \cdot dy - dx \cdot y_2，这样等式两边分别都只包含来自同一个元素的值，以及差不多相当于常量的 dx,dy。
- 其次，需要满足 x_1 \equiv x_2 \pmod {dx},y_1 \equiv y_2 \pmod {dy}
如果不满足这个，那么当然是不能相等的，因为不能有小数。
- 然后，需要满足 |\frac{x_1-x_2}{d_x}| \lt k + [(x_2,y_2) = (0,0)]。
综上，定义一个 S 中的元素 (x,y) 的类别属性为 (x \cdot d_y - y \cdot d_x,x \bmod {d_x},y \bmod {d_y})，只有两个 S 中的元素的类别属性相同，它们才可能产生相同的位置。
考虑开一个 map，存储每一种类别属性的所有元素。
回到原来问题，此时可以发现，和 (x_1,y_1) 处于同一种类别属性的元素中，有价值的仅包括 x 方向，y 方向上分别最接近的两个元素（总共 4 个元素）。
当前元素产生的新位置的形式为 (x_1 + k\cdot dx,y_1 + k\cdot dy)，而原本情况下 0 \le k \lt K + [(x_1,y_1)=(0,0)]。
这些邻居元素，实际的影响就是使得一段前缀或者后缀的 k 不合法，分类讨论一下就可以了。
map 里面开两个 set，分奇偶分别存储所有的位置就可以了。
对于 (0,0) 这个特殊的点，它有一个 k 可以等于 K 的特权，为了简单处理这种情况，可以额外建立一个节点 (dx,dy)。
T5
先预处理 f_u 表示 u 到所有子树内节点的距离，以及 siz_u 表示 u 子树大小。
然后，再次 dfs 整颗树，并且搜索到每个节点时，都记录其子树外的节点到其距离总和，从父节点到子节点递归的时候，实时更新就可以。