A15983. Hamon Odyssey
编程题
普及/提高-
知识点
题目描述
Jonathan is fighting against DIO's Vampire minions. There are $n$ of them with strengths $a_1, a_2, \dots, a_n$ . $\def\and {{\,\texttt{&}\,}}$
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) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r. $$ Here, $\\and$ denotes the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>. </p><p>Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in <span class="tex-font-style-bf">exactly</span> one group, and the <span class="tex-font-style-bf">sum</span> of <span class="tex-font-style-it">strengths</span> of the groups is <span class="tex-font-style-bf">minimized</span>. Among all ways to divide the vampires, he would like to find the way with the <span class="tex-font-style-bf">maximum</span> number of groups.</p><p>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.
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) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r. $$ Here, $\\and$ denotes the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>. </p><p>Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in <span class="tex-font-style-bf">exactly</span> one group, and the <span class="tex-font-style-bf">sum</span> of <span class="tex-font-style-it">strengths</span> of the groups is <span class="tex-font-style-bf">minimized</span>. Among all ways to divide the vampires, he would like to find the way with the <span class="tex-font-style-bf">maximum</span> number of groups.</p><p>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.
输入格式
The first line contains a single integer $t$ $(1 \leq t \leq 10^4)$ — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — the number of vampires.
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $0 \leq a_i \leq 10^9$ ) — the individual strength of each vampire.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — the number of vampires.
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $0 \leq a_i \leq 10^9$ ) — the individual strength of each vampire.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
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.
输入输出样例
输入 #1
3 3 1 2 3 5 2 3 1 5 2 4 5 7 12 6
输出 #1
1 2 1
说明/提示
In the first test case, the optimal way is to take all the $n$ vampires as a group. So, $f(1,3) = 1 \and 2 \and 3 = 0$ .
In the second test case, the optimal way is to make $2$ groups, $(2,3,1)$ and $(5,2)$ . So, $f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0$ .
In the second test case, the optimal way is to make $2$ groups, $(2,3,1)$ and $(5,2)$ . So, $f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0$ .