51nod 1204 Parity (并查集)

你的朋友写下一串包含1和0的串让你猜,你可以从中选择一个连续的子串(例如其中的第3到第5个数字)问他,该子串中包含了奇数个还是偶数个1,他会回答你的问题,然后你可以继续提问……你怀疑朋友的答案可能有错,或说同他之前的答案相互矛盾,例如:1 – 2 奇数,3 – 4 奇数,那么可以确定1 – 4 一定是偶数,如果你的朋友回答是奇数,就产生了矛盾。给出所有你朋友的答案,请你找出第一个出现矛盾的答案。

其实我们可以用前缀和的观点来看着提,我们将每个点拆成两个点,例如将i拆成:1. i的前缀和是偶数个1;2. i的前缀和是奇数个1。这样我们对于even的就将l – 1的奇数点和r的奇数点以及l – 1的偶数点和r的偶数点合并集合,odd同理。

 

LEAVE A COMMENT