做题记录 25.7.31

szt100309 · 2025-07-31 16:03:17 · 个人记录

\purple\odot CF1634E Fair Share

当存在至少一种数字出现次数为奇数时显然无解

否则 \sum n_i 个数分别建立一个点，对于一种数字，出现次数为偶数，两两匹配并对应位置连边，对于每一行，数字数量为偶数，两两匹配并对应位置连边，得到一张图，若这张图为二分图，对其黑白染色后取黑点为 \text L，白点为 \text R 显然合法（每行、每种数字 \text L,\text R 各占一半）

考虑证明对于所有数字出现次数都是偶数的情况，按上述方式建出的图必然为二分图

证明：

• 同一数字匹配的连边称为一类边，同一行匹配的连边称为二类边
• 若存在一个奇环，则环上一定存在相邻的一类边或相邻的二类边
• 然而两类边各自不共用顶点，因此不可能出现这一情况

时间复杂度 O(\sum n_i\log \sum n_i)（若用 unordered_map 则可去掉 \log）

代码

参考

\purple\odot CF1633F Perfect Matching

假设激活状态确定，从下往上做，对于一个点，若它上网匹配，则将它和它父亲匹配

对于树上包含根的连通块中的 x，点 x 与其父亲匹配当且仅当子树 x 内有奇数个点被激活（假定存在合法方案）

每个点维护一个 0/1 值，表示它是否与其父亲匹配，则加入一个点相当于翻转当前点到根的链上所有点的权值（根的权值需要特殊处理），设当前激活点数为 k，则存在合法方案当且仅当恰好 \frac k2 个点的权值为 1

对于操作 2 暴力实现即可

树剖维护即可做到 O(n\log^2n+wn)，其中 w 表示操作 2 的数量，用全局平衡二叉树可以做到 O(n\log n+wn)

代码

参考

\purple\odot CF1633E Spanning Tree Queries

对于 |w_i-q| 和 |w_j-q|，若 w_i\ne w_j，则两者相交于 \frac{w_i+w_j}2，若 w_i<w_j，将值域分为 (-\infty,w_i),[w_i,\frac{w_i+w_j}2),[\frac{w_i+w_j}2,w_j),[w_j,\infty) 四段，则每段内两者都是直线且不互相穿越

对于每组询问，二分出所在段后计算即可，这部分时间复杂度 O(k\log m)

总时间复杂度 O(m^3\log m+k\log m)

代码

参考