AC题解

思路说明
题目要求：将数组分成若干连续组，每组强度为组内所有数的按位与（&）。需要在所有组强度之和最小的前提下，最大化组数。

关键性质
按位与的非增性：对一个数不断进行按位与运算，结果只会减小或不变（二进制位只会从1变0，不会从0变1）。

整体按位与的影响：

设整个数组的按位与为 total_and（即所有数的 &）。

对于任意一个子数组，其按位与结果一定 ≥ total_and（因为子数组是整体的子集，包含更多数的 & 可能更小，但这里注意：子数组的 & 不一定 ≥ total_and？例如整体 & 是 0，子数组 & 可能 >0。实际上，整体 & 是所有数的公共位，子数组的 & 至少包含这些公共位，所以子数组 & 一定是整体 & 的超集（即二进制位上，整体 & 为1的位，子数组 & 也一定为1）。因此 子数组 & ≥ total_and（按数值比较）。

所以每组的强度至少为 total_and。
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        
        // 计算整个数组的按位与
        long long all_and = a[0];
        for (int i = 1; i < n; ++i) {
            all_and &= a[i];
        }
        
        if (all_and != 0) {
            // 整体与不为0时，只能分成一组
            cout << "1\n";
        } else {
            // 贪心分割：每段按位与为0
            int cnt = 0;
            long long cur = ~0LL; // 全1
            for (int i = 0; i < n; ++i) {
                cur &= a[i];
                if (cur == 0) {
                    ++cnt;
                    cur = ~0LL; // 重置
                }
            }
            cout << cnt << "\n";
        }
    }
    return 0;
}