补题 Hamon Odyssey

题目描述

乔纳森正在与迪奥的吸血鬼手下战斗。其中有 $n$ 个吸血鬼，它们的强度分别为 $a_1, a_2,\cdots, a_n$。

将 $(l,r)$ 表示由索引 $l$ 到 $r$ 的吸血鬼组成的一组。乔纳森意识到每个这样的组的强度取决于它们的最弱环节，即按位与操作。更具体地说，组 $(l,r)$ 的强度等于 $f(l,r) =$ $a_l \ \& \ a_{l+1} \ \& \ a_{l+2} \ \& \cdots \& \ a_r$。

这里，$\&$ 表示按位与操作。

乔纳森希望能快速击败这些吸血鬼手下，因此他会将吸血鬼分成连续的组，使得每个吸血鬼正好属于一组，并且这些组的强度之和尽量小。在所有可能的分组方式中，他希望找到组数最多的方式。 给定每个吸血鬼的强度，找出在所有可能的分组方式中，拥有最小强度之和的组的最大数量。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$，表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 2⋅10^5)$，表示吸血鬼的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ $(0 \le a_i \le 10^9)$，表示每个吸血鬼的个体强度。 所有测试用例中 $n$ 的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，输出一个整数，表示在所有可能的分组方式中，拥有最小强度之和的组的最大数量。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
3
3
1 2 3
5
2 3 1 5 2
4
5 7 12 6

样例输出 #1

1
2
3
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$。

题解

题目解析

按位且运算有以下性质：

根据这条性质，我们知道此时的最小值一定是 $a_1\wedge a_2\wedge \cdots \wedge a_n$ .

然后又因为只有 $a=0$ 或 $b=0$ 时：才有 $a\wedge b=a+b$ .

所以就是找可以拆成且值等于 $0$ 的区间的最大数量。

当最后一段的与不是 $0$ 的时候, 那么可以将其并入之前的一段. 当最后一段的与是 $0$ 的时候则单独分成一段.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(2e5);
int a[MAXN];

signed main(){
	T_{
		int n,ans=INT_MAX;
		cin >> n;
		fa(i,1,n){
			cin >> a[i];
			ans &= a[i];
		}
		if(ans != 0){
			cout << 1 << endl;
		}else{
			int cunt = 0,now = INT_MAX;
			fa(i,1,n){
				now &= a[i];
				if(now == 0){
					cunt++;
					now = INT_MAX;
				}
			}
			cout << cunt << endl;
		}
	}
	return 0;
}