Vijos 1112 小胖的奇偶 解题报告

挺有意思的一题，题目给出的信息实际上可以得到一些进一步的信息，显然如果a-b有偶数个1则1-(a-1)与1-b的1的个数的奇偶性相同，而如果a-b有奇数个1则1-(a-1)与1-b的1的个数的奇偶性必定不同。

用same[i]表示与i奇偶性相同的集合，用dif[i]表示与i奇偶性不同的集合，则对于a-b有偶数个1的信息，合并same[a-1]与same[b]的集合以及合并dif[a-1]与dif[b]的集合。若合并后same[a-1]=dif[b]或same[b]=dif[a-1]则可判定该信息不可能被满足。类似的，对于a-b有奇数个1的信息，合并same[a-1]与dif[b]的集合以及合并same[b]与dif[a-1]的集合，若合并后same[a-1]=same[b]则可判定该信息不可能被满足。但我们可以发现，经过集合合并，以上判定信息可以用same[a-1]=dif[a-1]或same[b]=dif[b]中的任意一条表示。

由于本题的区间范围很大但询问数很小，需要用离散化或hash来对区间的起点和终点进行处理。

R1188765 Accepted 100 From IwfWcf－ P1112 FPC Vivid Puppy 2009-3-27 0:27:09