LOADING

加载过慢请开启缓存 浏览器默认开启

D.Birthday Gift

Problem - 1946DBirthday Gift

题面:

分析:

对于区间位运算容易想到拆位,对x进行从高位到低位拆位分析:

1.当ii位为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,那么即使传递下去相等情况,那么也可以取答案。

代码: