Parity

题面翻译 给定一个长度为 \(n\) 的数组，你可以对它进行不超过 \(n\) 次操作。 对于每次操作： 选择两个下标 \(l, r\)，满足 \(1\leq l<r\leq n\)； 若 \(a_l + a_r\) 为奇数，将 \(a_r\) 赋值为 \(a_l\)，否则将 \(a_l\) 赋值为 ......

Kuro and Topological Parity 我们考虑在一张染色完成的图里，我们连上了一条边，会有何影响？ \(\bullet\) 在同色节点间连边——明显不会有任何影响。 \(\bullet\) 在异色节点间连边，但是出发点是个偶点（即有偶数条路径以其为终点的节点），终点的路径数增加了， ......

​ 洛谷P5937 [CEOI1999]Parity Game ​ 本来是想练习一下离散化的，结果看到这道又有并查集又有离散化的题，于是就逝了逝，在阅读题解后， 发现自己对并查集和离散化认识有点问题，于是写下这篇笔记总结一下。 看到这种给出几个条件判断矛盾的题，便想到了两种常见思路，一种是拓扑排序， ......