[Ural 1003]Parity
本文在署名-非商业性使用-相同方式共享 3.0版权协议下发布, 转载请注明出自aifreedom.com
这题做了很久才最终AC, NOIP前就写过, 但当时没能通过自己写的样例. 后来很久没有做题, 直到最近才把这题做掉. 但做的过程中很郁闷, 所以来写个简单的解题报告.(Ural 1003)
题目意思很好理解, 没有什么歧义, 思路也很容易想到. 首先, 用N(i)表示1..i的01序列中, 1的个数, 那么”a b even”表示N(a-1)和N(b)同奇偶, “a b odd”表示N(a-1)和N(b)不同奇偶. 那么很自然的会想到用并查集, 但怎么用就有学问了. 而且题中序列的长度太长, 且远大于询问次数, 要用到hash或者离散化(我一开始居然用离散化.. 硬是把O(n)的算法弄到了O(nlogn).. 晕..).
最初朴素的想法是将同奇偶的归到一个集合中, 并且在每个集合的根处记录下与这个集合奇偶性相反的集合标号. yuhch大牛也是这样做的, 但我在编程实现的过程中遇到了不少麻烦. 想找yuhch要来他的程序看看, 但他说他N年前AC的, 程序早就不在了.. 改换思路, 在使用并查集的时候记录每个节点和它的父亲的奇偶性是否相同. 并且用到了xor运算的一些性质: xor的逆运算还是xor, 而xor运算的真值表有正好和整数奇偶性相同. 于是可以很好地降低编程复杂度.
你可以点击这里下载我已AC的源程序.
