思路说明
题目要求:将数组分成若干连续组,每组强度为组内所有数的按位与(&)。需要在所有组强度之和最小的前提下,最大化组数。
关键性质
按位与的非增性:对一个数不断进行按位与运算,结果只会减小或不变(二进制位只会从1变0,不会从0变1)。
整体按位与的影响:
设整个数组的按位与为 total_and(即所有数的 &)。
对于任意一个子数组,其按位与结果一定 ≥ total_and(因为子数组是整体的子集,包含更多数的 & 可能更小,但这里注意:子数组的 & 不一定 ≥ total_and?例如整体 & 是 0,子数组 & 可能 >0。实际上,整体 & 是所有数的公共位,子数组的 & 至少包含这些公共位,所以子数组 & 一定是整体 & 的超集(即二进制位上,整体 & 为1的位,子数组 & 也一定为1)。因此 子数组 & ≥ total_and(按数值比较)。