A6463. Welcome24ever 与吸血鬼
编程题
普及-
知识点
题目描述
有 $n$ 个吸血鬼，它们的强度为 $a_1,a_2,\dots,a_n$。把一段连续区间记作 $(l,r)$。该组的“强度”定义为
$$ f(l,r)=a_l\ \&\ a_{l+1}\ \&\ \cdots\ \&\ a_r, $$
其中 $\&$ 为按位与。
Welcome24ever 想把这 $n$ 个吸血鬼分成**若干个不相交的连续组**（每个吸血鬼恰好属于一个组），使得**所有组强度之和尽量小**；在所有能达到最小和的划分中，她还想让**组的个数尽量多**。求这个“组数最多”的值。
$$ f(l,r)=a_l\ \&\ a_{l+1}\ \&\ \cdots\ \&\ a_r, $$
其中 $\&$ 为按位与。
Welcome24ever 想把这 $n$ 个吸血鬼分成**若干个不相交的连续组**（每个吸血鬼恰好属于一个组），使得**所有组强度之和尽量小**；在所有能达到最小和的划分中，她还想让**组的个数尽量多**。求这个“组数最多”的值。
输入格式
- 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。
- 对于每个测试用例：
- 第一行一个整数 $n$（$1\le n\le 2\times 10^5$）。
- 第二行 $n$ 个整数 $a_1,\dots,a_n$（$0\le a_i\le 10^9$）。
- 保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。
- 对于每个测试用例：
- 第一行一个整数 $n$（$1\le n\le 2\times 10^5$）。
- 第二行 $n$ 个整数 $a_1,\dots,a_n$（$0\le a_i\le 10^9$）。
- 保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。
输出格式
- 对每个测试用例，输出一个整数，表示在“强度和最小”的前提下，**组数的最大值**。
输入输出样例
输入 #1
3 3 1 2 3 5 2 3 1 5 2 4 5 7 12 6
输出 #1
1 2 1
说明/提示
在第一个测试用例中，最优的方式是将所有的吸血鬼作为一组。
所以 $f(1,3) = 1 \ \& \ 2 \ \& \ 3 = 0$。
在第二个测试用例中，最优的方式是分成两组，$(2,3,1)$ 和 $(5,2)$。所以 $f(1,3) + f(4,5) = (2 \ \& \ 3 \ \& \ 1) + (5 \ \& \ 2) = 0 + 0 = 0$。
所以 $f(1,3) = 1 \ \& \ 2 \ \& \ 3 = 0$。
在第二个测试用例中，最优的方式是分成两组，$(2,3,1)$ 和 $(5,2)$。所以 $f(1,3) + f(4,5) = (2 \ \& \ 3 \ \& \ 1) + (5 \ \& \ 2) = 0 + 0 = 0$。