Problem - 1946DBirthday Gift
题面:
分析:
对于区间位运算容易想到拆位,对x进行从高位到低位拆位分析:
1.当位为0时如果数组所有元素的第i位一共有奇数个1,那么无论怎么分配,总有一个段内有奇数个1,异或后结果为1,显然导致整体大于x。
2.当i位为0时如果有偶数个1,此时只能就近两两一组去保证异或为0还有组数最多,同时。
3.当i位为1时如果有奇数个1,此时不做任何处理,只能一段一个1.
4.当i位为1时如果有偶数个1,那么两两一组既能保证异或为0,还能保证组数最多,并且此时分组个数可以直接作为答案的一种取max,当然如果每个单独一组不做处理那么数组间异或结果为1,虽然此时不能当作答案,但是之后的数组的分配可能有更多的答案个数,所以也要把不做处理的情况传递下取去。
因为在第4个情况的时候,我们总是不做处理传递下去,并没有真正的处理x当前位相等的情况。所以我们对x进行+1,那么即使传递下去相等情况,那么也可以取答案。
代码: