当前位置: 代码迷 >> 综合 >> 『并查集·奇偶性判定』Parity game
  详细解决方案

『并查集·奇偶性判定』Parity game

热度:1   发布时间:2023-12-17 11:22:05.0

Description

有一个01序列,长度<=1000000000,现在有n条信息,每条信息的形式是-a b even/odd。表示第a位到第b位元素之间的元素总和是偶数/奇数。 你的任务是对于这些给定的信息,输出第一个不正确的信息所在位置-1。信息的数目不超过5000。 如果信息全部正确,即可以找到一个满足要求的01序列,那么输出n。

Solution1

l到r是偶数,想到与1到l-1的奇偶性和1-r的奇偶性相同。l到r是奇数,说明1到l-1的奇偶性和1-r的奇偶性不同。根据这一个特性,我们可以使用并查集来维护这个关系。

我们可以构造一棵树,使得这一棵树任意两点间有且只有一条路径,且我们在边上设置0或1的边权,则任意两点之间的奇偶性就是边权的异或和,若异或和为0表示偶数,1表示奇数。

对于每一次操作的任意两点l-1和r来说,如果l-1和r如果已经存在路径,我们就看l到祖先的路径异或上r到祖先的路径的异或和是否符合当前的奇偶性,如果不符合就直接退出。

在并查集d[i]表示节点i到其祖先节点的xor和,每当l-1和r不在同一个并查集是,如果将fa[l-1]作为fa[r]的子节点,一定满足 d [ l ? 1 ]   x o r   d [ f a [ l ? 1 ] ]   x o r   d [ r ]   =   a n s d[l-1]\ xor\ d[fa[l-1]]\ xor\ d[r]\ =\ ans d[l?1] xor d[fa[l?1]] xor d[r] = ans当两边同时乘上异或值 a n s     d [ f a [ l ? 1 ] ] ans\ ^\ d[fa[l-1]] ans  d[fa[l?1]],即可得到等式: d [ f a [ l ? 1 ] ] = d [ l ? 1 ]   x o r   d [ r

  相关解决方案