A15332. Burenka and Traditions (easy version)
编程题
普及/提高-
知识点
题目描述
This is the easy version of this problem. The difference between easy and hard versions is only the constraints on $a_i$ and on $n$ . You can make hacks only if both versions of the problem are solved.
Burenka is the crown princess of Buryatia, and soon she will become the $n$ -th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $n$ -th ruler, the inhabitants of the country give them an array of $a$ of exactly $n$ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:
- select two indices $l$ and $r$ , so that $1 \le l \le r \le n$ and a non-negative integer $x$ , then
- for all $l \leq i \leq r$ assign $a_i := a_i \oplus x$ , where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). It takes $\left\lceil \frac{r-l+1}{2} \right\rceil$ seconds to do this operation, where $\lceil y \rceil$ denotes $y$ rounded up to the nearest integer.
Help Burenka calculate how much time she will need.
Burenka is the crown princess of Buryatia, and soon she will become the $n$ -th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $n$ -th ruler, the inhabitants of the country give them an array of $a$ of exactly $n$ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:
- select two indices $l$ and $r$ , so that $1 \le l \le r \le n$ and a non-negative integer $x$ , then
- for all $l \leq i \leq r$ assign $a_i := a_i \oplus x$ , where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). It takes $\left\lceil \frac{r-l+1}{2} \right\rceil$ seconds to do this operation, where $\lceil y \rceil$ denotes $y$ rounded up to the nearest integer.
Help Burenka calculate how much time she will need.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 500$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ( $1 \le n \le 5000$ ) — the size of the array.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 5000$ ) — elements of the array.
It is guaranteed that the sum of $n$ in all tests does not exceed $5000$ .
The first line of each test case contains a single integer $n$ ( $1 \le n \le 5000$ ) — the size of the array.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 5000$ ) — elements of the array.
It is guaranteed that the sum of $n$ in all tests does not exceed $5000$ .
输出格式
For each test case, output a single number — the minimum time that Burenka will need.
输入输出样例
输入 #1
7 4 5 5 5 5 3 1 3 2 2 0 0 3 2 5 7 6 1 2 3 3 2 1 10 27 27 34 32 2 31 23 56 52 4 5 1822 1799 57 23 55
输出 #1
2 2 0 2 4 7 4
说明/提示
In the first test case, Burenka can choose segment $l = 1$ , $r = 4$ , and $x=5$ . so it will fill the array with zeros in $2$ seconds.
In the second test case, Burenka first selects segment $l = 1$ , $r = 2$ , and $x = 1$ , after which $a = [0, 2, 2]$ , and then the segment $l = 2$ , $r = 3$ , and $x=2$ , which fills the array with zeros. In total, Burenka will spend $2$ seconds.
In the second test case, Burenka first selects segment $l = 1$ , $r = 2$ , and $x = 1$ , after which $a = [0, 2, 2]$ , and then the segment $l = 2$ , $r = 3$ , and $x=2$ , which fills the array with zeros. In total, Burenka will spend $2$ seconds.