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

[KOI 2023 Round 2] 不稳定数列

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

NN 个自然数从左到右依次排列。第 ii1iN1 \leq i \leq N)个位置上的自然数为 AiA_i

你可以从中任选若干个自然数。注意,不能一个自然数也不选,必须至少选择 1 个自然数。

设你选择的自然数个数为 kk,选择的自然数为 B1,B2,,BkB_1, B_2, \cdots, B_k。所选自然数的顺序应保持其在原序列中的相对顺序。

例如,若 N=5N = 5,且 A=[3,1,4,1,5]A = [3, 1, 4, 1, 5],你选择了第 2、4、5 个位置上的自然数,则 k=3k = 3B=[1,1,5]B = [1, 1, 5]

BB 中相邻两个自然数的和计算出来:第一个和第二个,第二个和第三个,第三个和第四个,……,如果所有的和都是奇数,那么称 BB 是一个不稳定数列。当 k=1k = 1 时,特殊地,BB 被认为是不稳定数列。

例如,若 k=6k = 6B=[1,4,3,2,5,4]B = [1, 4, 3, 2, 5, 4],那么:

  • 第一个自然数(1)与第二个自然数(4)的和为 5,为奇数;
  • 第二个自然数(4)与第三个自然数(3)的和为 7,为奇数;
  • 第三个自然数(3)与第四个自然数(2)的和为 5,为奇数;
  • 第四个自然数(2)与第五个自然数(5)的和为 7,为奇数;
  • 第五个自然数(5)与第六个自然数(4)的和为 9,为奇数。

因此,相邻两个自然数的和始终为奇数,BB 是不稳定数列。

又如,k=1k = 1B=[2]B = [2],由于 k=1k = 1,故 BB 是不稳定数列。

但是,若 k=4k = 4B=[4,5,1,2]B = [4, 5, 1, 2],那么:

  • 第一个自然数(4)与第二个自然数(5)的和为 9,为奇数;
  • 第二个自然数(5)与第三个自然数(1)的和为 6,为偶数。

因为存在相邻两个自然数的和不是奇数的情况,所以 BB 不是不稳定数列。

你的任务是:选择若干个自然数,使得所构成的 BB 是不稳定数列,并且所选自然数的个数 kk 最大。请编写一个程序,求出这个最大的 kk

例如,当 A=[4,5,1,2]A = [4, 5, 1, 2] 时:

  • 如果选取全部的自然数,得到 B=[4,5,1,2]B = [4, 5, 1, 2],这不是不稳定数列,不能用全部 4 个数;
  • 但若选取第 1、3、4 个自然数,得到 B=[4,1,2]B = [4, 1, 2]
    • 第一个自然数(4)与第二个自然数(1)的和为 5,为奇数;
    • 第二个自然数(1)与第三个自然数(2)的和为 3,为奇数。

因此,所选 BB 是不稳定数列,且长度为 3,是可能的最大值。

输入格式

第一行输入一个整数 NN

第二行输入 A1,A2,,ANA_1, A_2, \cdots, A_N,各数之间用空格分隔。

输出格式

输出一个整数,表示可以选择的最大自然数个数 kk

4
4 5 1 2
3
3
3 2 3
3
5
3 3 3 3 3
1

提示

限制条件

  • 所有给定数均为自然数。
  • 1N3000001 \leq N \leq 300\,000
  • 1Ai100000(1iN)1 \leq A_i \leq 100\,000 \quad (1 \leq i \leq N)

子任务

  1. (5 分)答案为 N1N - 1NN
  2. (8 分)N15N \leq 15
  3. (12 分)N5000N \leq 5\,000
  4. (15 分)Ai50(1iN)A_i \leq 50 \quad (1 \leq i \leq N)
  5. (60 分)无附加限制。

翻译由 ChatGPT-4o 完成