#P12661. [KOI 2023 Round 2] 不稳定数列
[KOI 2023 Round 2] 不稳定数列
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
有 个自然数从左到右依次排列。第 ()个位置上的自然数为 。
你可以从中任选若干个自然数。注意,不能一个自然数也不选,必须至少选择 1 个自然数。
设你选择的自然数个数为 ,选择的自然数为 。所选自然数的顺序应保持其在原序列中的相对顺序。
例如,若 ,且 ,你选择了第 2、4、5 个位置上的自然数,则 ,。
将 中相邻两个自然数的和计算出来:第一个和第二个,第二个和第三个,第三个和第四个,……,如果所有的和都是奇数,那么称 是一个不稳定数列。当 时,特殊地, 被认为是不稳定数列。
例如,若 ,,那么:
- 第一个自然数(1)与第二个自然数(4)的和为 5,为奇数;
- 第二个自然数(4)与第三个自然数(3)的和为 7,为奇数;
- 第三个自然数(3)与第四个自然数(2)的和为 5,为奇数;
- 第四个自然数(2)与第五个自然数(5)的和为 7,为奇数;
- 第五个自然数(5)与第六个自然数(4)的和为 9,为奇数。
因此,相邻两个自然数的和始终为奇数, 是不稳定数列。
又如,,,由于 ,故 是不稳定数列。
但是,若 ,,那么:
- 第一个自然数(4)与第二个自然数(5)的和为 9,为奇数;
- 第二个自然数(5)与第三个自然数(1)的和为 6,为偶数。
因为存在相邻两个自然数的和不是奇数的情况,所以 不是不稳定数列。
你的任务是:选择若干个自然数,使得所构成的 是不稳定数列,并且所选自然数的个数 最大。请编写一个程序,求出这个最大的 。
例如,当 时:
- 如果选取全部的自然数,得到 ,这不是不稳定数列,不能用全部 4 个数;
- 但若选取第 1、3、4 个自然数,得到 :
- 第一个自然数(4)与第二个自然数(1)的和为 5,为奇数;
- 第二个自然数(1)与第三个自然数(2)的和为 3,为奇数。
因此,所选 是不稳定数列,且长度为 3,是可能的最大值。
输入格式
第一行输入一个整数 。
第二行输入 ,各数之间用空格分隔。
输出格式
输出一个整数,表示可以选择的最大自然数个数 。
4
4 5 1 2
3
3
3 2 3
3
5
3 3 3 3 3
1
提示
限制条件
- 所有给定数均为自然数。
子任务
- (5 分)答案为 或 。
- (8 分)
- (12 分)
- (15 分)
- (60 分)无附加限制。
翻译由 ChatGPT-4o 完成