#P9680. Where is the legend?

    ID: 6307 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-差分转化不变量分析2-adic 赋值以值为状态枚举最后一次操作线性 DPIZhO

Where is the legend?

Source: International Zhautykov Olympiad 2022, Computer Science, Day 1, Task A. 「Where is the legend?」.

题目描述

给定一个长为 nn 的正整数序列 a1,⋯ ,ana_1,\cdots,a_n。

你可以进行若干次操作,每次操作你可以选择一个位置 i∈[2,n−1]i\in[2,n-1] 使得 ai=ai−1+ai+12a_i=\dfrac{a_{i-1}+a_{i+1}}{2},随后将 aia_i 删去,之后的数按顺序向前补空位。

求若干次操作后序列长度最小可以是多少。

输入格式

第一行,一个正整数 TT,表示数据组数。之后对于每组数据:

  • 第一行,一个正整数 nn;
  • 第二行,nn 个正整数 a1,⋯ ,ana_1,\cdots,a_n。

输出格式

对于每组数据,输出一行,一个正整数,表示答案。

样例

3
5
1 2 3 4 5
7
1 3 5 6 7 8 10
3
1 1 1
2
4
2

对于第一组数据 [1,2,3,4,5][1,2,3,4,5],依次删除 2,4,32,4,3 即可。

对于第二组数据 [1,3,5,6,7,8,10][1,3,5,6,7,8,10],依次删除 3,7,83,7,8 即可。

对于第三组数据 [1,1,1][1,1,1],删除中间的 11 即可。

样例 2 见下发文件,该样例符合测试点 17∼2017\sim 20 的限制。

数据范围

本题共 2020 组测试点,各 55 分。

对于所有数据,n≥3n\ge 3,1≤T≤1031 \le T\le 10^3,∑n≤3⋅105\sum n\le 3\cdot 10^5,1≤ai≤1091 \le a_i\le 10^9。

测试点编号 n≤n\le ∑n≤\sum n\le 特殊性质
1∼31\sim 3 1515 400400
4∼64\sim 6 A
7∼87\sim 8 B
9∼129\sim 12 300300 10310^3
13∼1613\sim 16 3×1033\times 10^3 10410^4
17∼2017\sim 20

特殊性质 A:ai=ia_i=i。

特殊性质 B:ai≤3a_i\le 3。