luogu#P9492. 「SFCOI-3」进行一个拆的解

「SFCOI-3」进行一个拆的解

题目背景

公告:Subtask 0 数据有误,现已更改。


三岁的小明非常不喜欢完整的东西,他甚至连序列都想要拆掉。

题目描述

给定序列 a1ana_1\dots a_n,小明想要把它拆成两个子段 [1,l][l+1,n](1l<n)[1, l][l + 1, n](1 \leq l \lt n),即 a1ala_1\dots a_lal+1ana_{l+1}\dots a_n

由于小明强迫症很严重,他不希望对于这两个子段,其中一个是另一个的 子序列,换句话说,他不希望其中一个子段可以通过删掉若干(可能为 00)个元素变成另一个。

在父母出门的时候,小明终于找到了把序列拆开的机会!所以,他想知道,是否存在一种拆解的方式满足:任意一个子段都不是另一个子段的子序列。

输入格式

第一行一个整数 TT,表示小明总共要拆解 TT 个序列。接下来 TT 行,每行描述一个序列:

  • 每行第一个整数 nn,表示序列长度;
  • 接下来 nn 个整数,依次代表序列中每一个数。

输出格式

输出共 TT 行。

对于每轮游戏,若存在满足条件的序列,输出 YES,否则输出 NO

2
5 1 2 1 2 1
7 1 2 1 1 2 1 0
NO
YES

提示

样例解释

对于第一个序列,所有拆分方式有:

  • {1},{2,1,2,1}\lbrace 1 \rbrace,\lbrace 2,1,2,1 \rbrace
  • {1,2},{1,2,1}\lbrace 1,2 \rbrace,\lbrace 1,2,1 \rbrace
  • {1,2,1},{2,1}\lbrace 1,2,1 \rbrace,\lbrace 2,1 \rbrace
  • {1,2,1,2},{1}\lbrace 1,2,1,2 \rbrace,\lbrace 1 \rbrace

从任何地方拆开都是不合法的——较短的那个序列都是另一个序列的子序列。

对于第二个序列,其中一种合理的拆分方式为 {1,2,1,1,2},{1,0}\lbrace 1,2,1,1,2 \rbrace,\lbrace 1,0 \rbrace

数据规模与约定

本题采用捆绑测试

  • Subtask 0(15 points):ai=0a_i = 0
  • Subtask 1(15 points):n=10n = 10,保证数据随机生成。
  • Subtask 2(30 points):nn 为偶数。
  • Subtask 3(40 points):无特殊限制。

对于所有数据,1T1051\leq T \leq 10^52n1052 \leq n \leq 10^51n1061 \leq \sum n \leq 10^60ai1000 \leq a_i \leq 100