【做题记录】ABC155F + CF1994F

KSCD_ · 2024-07-20 22:31:22 · 个人记录

要看到题目之间的联系，更要看到联系之间的联系。

[ABC155F] Perils in Parallel

考虑把区间操作变成单点操作，那么区间 [l,r] 取反相当于在前缀异或值上取反 l 和 r+1。那么对整个序列求前缀异或值，可以同时修改某两个位置，求是否能够把序列变为全 0（原序列和前缀序列均是），l 和 r 可以离散化二分求出。

那么把 l 和 r+1 连边，生成一张无向图。考虑若要同时取反 x 和 y，只需任选图上一条 x,y 之间的路径，使用路径上的边操作即可。那么找一个生成森林即可进行操作。

考虑对于每个需要取反的点 x 都把 x 到所在树根 rt 路径上的边状态全部取反，那么两个点的路径即可由 rt 相连构成一整条路径从而实现取反。如此若 rt 最终的状态不符合题意则无解，否则求一下每条边是否被选即可。

[CF1994F] Stardew Valley

重要性质：一张图有欧拉回路当且仅当每个点的度均为偶数。

那么把重要边的对每个点的度数奇偶性记录下来，非重要边可以同时取反两个点的奇偶性，跟上一道题一样做，最后跑欧拉回路即可。

所以题目之间会有很多相似的部分，关键在于做过的题要理解每一部分并能运用，而不同的部分需要经验性质之类解决。