【VP 记录】EDU078

KSCD_ · 2024-06-10 14:54:41 · 个人记录

记录

只会 ABC，C 还卡了很久。D 题赛后发现是用 set，以后要多练练 map/set。

题解

A. Shuffle Hashing

处理各个字母前缀的出现次数，枚举每个区间作为 S 判断即可。

B. A and B

发现要求就是依次加 1,2,3\cdots 给某个数，最终使两数差为 k=\left|a-b\right|

所以先求和直到 i 时 sum\ge k，然后分讨：

• 若 sum=k，则答案为 i

• 若 sum\neq k，设差值 x=sum-k，若 x 为偶数可直接从前面的数中选出 x 的一半放给另一个数，否则需要 i+1 或 i+2 中为奇数的一个来确保奇偶性。

  C. Berry Jam

  问题可以看成要选 a 数组的一段前缀和 b 数组的一段后缀，发现要两者数量相等，也就是两段中 1 和 2 的数量差互为相反数，因此设 f_i 和 g_i 分别表示两种的数量差为 i 在 a 和 b 中的最大长度。

用前缀和后缀处理 f_i 和 g_i，由于数组下标非负，可以加上常量 n。最后枚举 i 并计算 f_i+g_{-i} 的最大值，用 2n 减去即为答案。

D. Segment Tree

发现 i,j 两点间有边当且仅当 l_j<l_i<r_j<r_i，所以用树状数组可以统计边数，若边数不为 n-1 则一定不是树。

之后用 set 维护所有的线段，每次在 set 上二分，把所有边加进去，最后并查集判断连通即可。

E. Tests for problem D

首先发现如果 x,y 两点都与 u 有边相连，则 x,y 之间必定无边，所以需要两点分别在 l_u 和 r_u 或两点的线段有包含关系，因此想到每个点的左边连接所有子树，右边只连接它的父亲。

所以进行树形 dp，每次先递归下去处理完子树的左端点，接着确定根的左端点，最后逆序确定所有子节点的右端点，这样所有子节点是逐个包含的，保证不会有边。