Codeforces Round 882 div.2 B-526互联

Jonathan is fighting against DIO's Vampire minions. There are

Denote

f (l, r) = a l

Here,

Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in exactly one group, and the sum of strengths of the groups is minimized. Among all ways to divide the vampires, he would like to find the way with the maximum number of groups.

Given the strengths of each of the

Input

The first line contains a single integer

The first line of each test case contains a single integer

The second line of each test case contains

The sum of

Output

For each test case, output a single integer — the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

题目链接：Problem - B - Codeforces

思路：咱们找一下规律，主要分为两个情况：

1.所有数的&值非零：

&到最后一个数仍旧非零，虽然分组为一但能保证最小，多&一个（新值） <= (旧值) ，即使等于，值+旧值 > 新值，并不能保证最小

所以分组只能为1，才能保证所有值的&最小

2.所有数的&值为零：

　　贪心算法：向前运算 if(an == 0) ans++ , an = num[i]; 最后判断一下an的值是否为0

现在是代码时间欢迎━(*｀∀´*)ノ亻!

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t , n;
 4 int main()
 5 {
 6     scanf("%d",&t);
 7     while(t--)
 8     {
 9         scanf("%d",&n);
10         vector<int> num(n+10);
11         int sum = 0;
12         for(int i = 1; i <= n; i++)
13             scanf("%d",&num[i]);
14         sum = num[1];
15         for(int i = 1; i <= n; i++)
16             sum &= num[i];
17         if(sum != 0) { printf("1\n");  continue; }
18         int an = num[1] , ans = 0;
19         for(int i = 2; i <= n; i++)
20         {
21             if(an == 0)
22                 an = num[i] , ans++;
23             else
24                 an &= num[i];
25         }
26         if(an == 0 || ans == 0) ans++;
27         printf("%d\n",ans);
28     }
29     return 0;
30 }