标签：882 vampires sum Codeforces number test groups each div.2

Smiling & Weeping

　　　　　　　　　　　　　　----玫瑰花你拿才好看，风景要和你看才浪漫--<-<-<@ B. Hamon Odyssey time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Jonathan is fighting against DIO's Vampire minions. There are n� of them with strengths a1,a2,…,an�1,�2,…,��. 

Denote (l,r)(�,�) as the group consisting of the vampires with indices from l� to r�. Jonathan realizes that the strength of any such group is in its weakest link, that is, the bitwise AND. More formally, the strength level of the group (l,r)(�,�) is defined as

f(l,r)=al&al+1&al+2&…&ar.�(�,�)=��&��+1&��+2&…&��. Here, && denotes the bitwise AND operation.

 

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 n� vampires, find the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

Input

The first line contains a single integer t� (1≤t≤104)(1≤�≤104) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer n� (1≤n≤2⋅1051≤�≤2⋅105) — the number of vampires.

The second line of each test case contains n� integers a1,a2,…,an�1,�2,…,�� (0≤ai≤1090≤��≤109) — the individual strength of each vampire.

The sum of n� over all test cases does not exceed 2⋅1052⋅105.

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 }

 

没有长亭古道，没有劝君更尽一杯酒，和所有文章的结尾一样，我们下次再见

ヾ(￣▽￣)Bye~Bye~

 

标签：882,vampires,sum,Codeforces,number,test,groups,each,div.2
From： https://www.cnblogs.com/smiling-weeping-zhr/p/17569655.html