Everybody Likes Good Arrays!

题意翻译

给出一个长度为 $n$ 的数组 $a$，求需要至少几次操作满足所有 $a_i$ 与 $a_{i + 1}$ 的奇偶性不同。 我们定义一次操作为： 1. 选取任意一个 $i$，当且仅当 $a_i$ 与 $a_{i + 1}$ 的奇偶性相同； 1. 删除 $a_{i + 1}$，将 $a_i$ 变为 $a_i \times a_{i + 1}$。 本题有多组数据，所以请在所有输入数据的最前面先输入数据组数 $t$。 By 677831。

题目描述

An array $ a $ is good if for all pairs of adjacent elements, $ a_i $ and $ a_{i+1} $ ( $ 1\le i \lt n $ ) are of different parity. Note that an array of size $ 1 $ is trivially good. You are given an array of size $ n $ . In one operation you can select any pair of adjacent elements in which both elements are of the same parity, delete them, and insert their product in the same position. Find the minimum number of operations to form a good array.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 100 $ ). The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 10^{9} $ ).

输出格式

For each test case print an integer, the minimum number of operations required to form a good array.

输入输出样例

输入样例 #1

3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3

输出样例 #1

2
0
3

说明

Consider the first test case. Select the $ 2 $ -nd and the $ 3 $ -rd integers and apply the operation on them. The array changes from $ [1, \color{red}{7}, \color{red}{11}, 2, 13] $ to $ [1, \color{red}{77}, 2, 13] $ . Next, select the $ 1 $ -st and the $ 2 $ -nd integers, array changes from $ [\color{red}{1}, \color{red}{77}, 2, 13] $ to $ [\color{red}{77}, 2, 13] $ . Thus we require $ 2 $ operations. It can be proved that this is the minimum number of operations. In the second test case, the given array is already good. So we require $ 0 $ operations.

题目大意：
给定一个长度为 $n$ 的数组 $a$，要求通过最少的操作次数，使得数组中任意相邻的两个元素 $a_i$ 和 $a_{i+1}$ 的奇偶性不同。操作定义为：选择任意一个位置 $i$，当且仅当 $a_i$ 和 $a_{i+1}$ 的奇偶性相同时，删除 $a_{i+1}$，并将 $a_i$ 更新为 $a_i \times a_{i+1}$。题目包含多组数据，需要先输入数据组数 $t$。

输入输出数据格式：
- 输入格式：
- 第一行包含一个整数 $t$，表示数据组数（$1 \le t \le 500$）。
- 接下来的每组数据，第一行包含一个整数 $n$（$1 \le n \le 100$）。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。
- 输出格式：
- 对于每组数据，输出一个整数，表示形成好数组所需的最少操作次数。

输入输出样例：
- 输入样例：
```
3
5
1 7 11 2 13
4
1 2 3 4
6
1 1 1 2 2 3
```
- 输出样例：
```
2
0
3
```题目大意： 给定一个长度为 $n$ 的数组 $a$，要求通过最少的操作次数，使得数组中任意相邻的两个元素 $a_i$ 和 $a_{i+1}$ 的奇偶性不同。操作定义为：选择任意一个位置 $i$，当且仅当 $a_i$ 和 $a_{i+1}$ 的奇偶性相同时，删除 $a_{i+1}$，并将 $a_i$ 更新为 $a_i \times a_{i+1}$。题目包含多组数据，需要先输入数据组数 $t$。 输入输出数据格式： - 输入格式： - 第一行包含一个整数 $t$，表示数据组数（$1 \le t \le 500$）。 - 接下来的每组数据，第一行包含一个整数 $n$（$1 \le n \le 100$）。 - 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。 - 输出格式： - 对于每组数据，输出一个整数，表示形成好数组所需的最少操作次数。 输入输出样例： - 输入样例： ``` 3 5 1 7 11 2 13 4 1 2 3 4 6 1 1 1 2 2 3 ``` - 输出样例： ``` 2 0 3 ```