P12661 [KOI 2023 Round 2] 不稳定数列

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

有 $N$ 个自然数从左到右依次排列。第 $i$（$1 \leq i \leq N$）个位置上的自然数为 $A_i$。 你可以从中任选若干个自然数。注意，不能一个自然数也不选，必须至少选择 1 个自然数。 设你选择的自然数个数为 $k$，选择的自然数为 $B_1, B_2, \cdots, B_k$。所选自然数的顺序应保持其在原序列中的相对顺序。 例如，若 $N = 5$，且 $A = [3, 1, 4, 1, 5]$，你选择了第 2、4、5 个位置上的自然数，则 $k = 3$，$B = [1, 1, 5]$。 将 $B$ 中相邻两个自然数的和计算出来：第一个和第二个，第二个和第三个，第三个和第四个，……，如果所有的和都是奇数，那么称 $B$ 是一个**不稳定数列**。当 $k = 1$ 时，特殊地，$B$ 被认为是不稳定数列。 例如，若 $k = 6$，$B = [1, 4, 3, 2, 5, 4]$，那么： - 第一个自然数（1）与第二个自然数（4）的和为 5，为奇数； - 第二个自然数（4）与第三个自然数（3）的和为 7，为奇数； - 第三个自然数（3）与第四个自然数（2）的和为 5，为奇数； - 第四个自然数（2）与第五个自然数（5）的和为 7，为奇数； - 第五个自然数（5）与第六个自然数（4）的和为 9，为奇数。 因此，相邻两个自然数的和始终为奇数，$B$ 是不稳定数列。 又如，$k = 1$，$B = [2]$，由于 $k = 1$，故 $B$ 是不稳定数列。 但是，若 $k = 4$，$B = [4, 5, 1, 2]$，那么： - 第一个自然数（4）与第二个自然数（5）的和为 9，为奇数； - 第二个自然数（5）与第三个自然数（1）的和为 6，为偶数。 因为存在相邻两个自然数的和不是奇数的情况，所以 $B$ 不是不稳定数列。 你的任务是：选择若干个自然数，使得所构成的 $B$ 是不稳定数列，并且所选自然数的个数 $k$ 最大。请编写一个程序，求出这个最大的 $k$。 例如，当 $A = [4, 5, 1, 2]$ 时： - 如果选取全部的自然数，得到 $B = [4, 5, 1, 2]$，这不是不稳定数列，不能用全部 4 个数； - 但若选取第 1、3、4 个自然数，得到 $B = [4, 1, 2]$： - 第一个自然数（4）与第二个自然数（1）的和为 5，为奇数； - 第二个自然数（1）与第三个自然数（2）的和为 3，为奇数。 因此，所选 $B$ 是不稳定数列，且长度为 3，是可能的最大值。

第一行输入一个整数 $N$。 第二行输入 $A_1, A_2, \cdots, A_N$，各数之间用空格分隔。

输出一个整数，表示可以选择的最大自然数个数 $k$。

**限制条件** - 所有给定数均为自然数。 - $1 \leq N \leq 300\,000$ - $1 \leq A_i \leq 100\,000 \quad (1 \leq i \leq N)$ **子任务** 1. （5 分）答案为 $N - 1$ 或 $N$。 2. （8 分）$N \leq 15$ 3. （12 分）$N \leq 5\,000$ 4. （15 分）$A_i \leq 50 \quad (1 \leq i \leq N)$ 5. （60 分）无附加限制。 翻译由 ChatGPT-4o 完成