CSP-S2022模拟赛1 10.04
CSP-S2022模拟赛1 10.04
A
相当于每次可以将一个数加上 [C,D]，或者减去 [C,D]。
次，因此最后的值域区间为：
62428
B P3147[USACO16OPEN]262144 P
的右端点。
88502520
C [ARC097D] Monochrome Cat
需要遍历的点一定是在最小的包含白点的连通块内。
剩余的树上每个点都必须经过。因此除了起点与终点之间路径上的边会被经过恰好一次以外，其余所有边都会被经过恰好两次。
不妨先设所有边都经过了两次，若无修改每个点颜色即为初始颜色异或度数奇偶性，只需在其为白时进行一次修改操作。
然后考虑起点与终点之间的路径，它的影响是让路径上的点（包含起点但不包含终点）都被少经过一次。
容易发现，原本为白操作次数减 2，原本为黑色操作次数不变。
于是类似找树的直径即可。
D [USACO18JAN]Cow at Large P
设 g_i 为 i 到最近叶子的距离。
如果 u 为根，d_i\ge g_i 则 i 子树内仅需贡献 1 即可拦截 u，注意到如果 i 的父节点 f_i 能拦截 u 则没必要动用 i，所以我们令 d_i\ge g_i \land d_{f_i}< g_{f_i}
考虑点分治，根据分治重心我们可以划分成一个点及若干子树。
考虑每个子树对子树外的贡献，以及分治重心对所有子树的贡献。
注意一下一开始钦定的限制条件，不然可能重复计算。
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-04
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录