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

Luogu

IDLGP9492

Time500ms

Memory512MB

DifficultyP2

2023洛谷原创O2优化构造

给定序列 $a_1\dots a_n$，小明想要把它拆成两个子段 $[1, l][l + 1, n](1 \leq l \lt n)$，即 $a_1\dots a_l$ 和 $a_{l+1}\dots a_n$。由于小明强迫症很严重，他不希望对于这两个子段，其中一个是另一个的 **子序列**，换句话说，他不希望其中一个子段可以通过删掉若干（可能为 $0$）个元素变成另一个。在父母出门的时候，小明终于找到了把序列拆开的机会！所以，他想知道，是否存在一种拆解的方式满足：任意一个子段都不是另一个子段的子序列。 ## Input 第一行一个整数 $T$，表示小明总共要拆解 $T$ 个序列。接下来 $T$ 行，每行描述一个序列： + 每行第一个整数 $n$，表示序列长度； + 接下来 $n$ 个整数，依次代表序列中每一个数。 ## Output 输出共 $T$ 行。对于每轮游戏，若存在满足条件的序列，输出 `YES`，否则输出 `NO`。 [samples] ## Background **公告：Subtask 0 数据有误，现已更改。** ------------ 三岁的小明非常不喜欢完整的东西，他甚至连序列都想要拆掉。 ## Note ### 样例解释对于第一个序列，所有拆分方式有： - $\lbrace 1 \rbrace,\lbrace 2,1,2,1 \rbrace$。 - $\lbrace 1,2 \rbrace,\lbrace 1,2,1 \rbrace$。 - $\lbrace 1,2,1 \rbrace,\lbrace 2,1 \rbrace$。 - $\lbrace 1,2,1,2 \rbrace,\lbrace 1 \rbrace$。从任何地方拆开都是不合法的——较短的那个序列都是另一个序列的子序列。对于第二个序列，其中一种合理的拆分方式为 $\lbrace 1,2,1,1,2 \rbrace,\lbrace 1,0 \rbrace$。 ### 数据规模与约定 **本题采用捆绑测试**。 - Subtask 0（15 points）：$a_i = 0$。 - Subtask 1（15 points）：$n = 10$，保证数据随机生成。 - Subtask 2（30 points）：$n$ 为偶数。 - Subtask 3（40 points）：无特殊限制。对于所有数据，$1\leq T \leq 10^5$，$2 \leq n \leq 10^5$，$1 \leq \sum n \leq 10^6$，$0 \leq a_i \leq 100$。

Samples

Input #1

2
5 1 2 1 2 1
7 1 2 1 1 2 1 0

Output #1

NO
YES

API Response (JSON)

{
  "problem": {
    "name": "「SFCOI-3」进行一个拆的解",
    "description": {
      "content": "给定序列 $a_1\\dots a_n$，小明想要把它拆成两个子段 $[1, l][l + 1, n](1 \\leq l \\lt n)$，即 $a_1\\dots a_l$ 和 $a_{l+1}\\dots a_n$。 由于小明强迫症很严重，他不希望对于这两个子段，其中一个是另一个的 **子序列**，换句话说，他不希望其中一个子段可以通过删掉若干（可能为 $0$）个元素变成另一个。 在父母出门的时候",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9492"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定序列 $a_1\\dots a_n$，小明想要把它拆成两个子段 $[1, l][l + 1, n](1 \\leq l \\lt n)$，即 $a_1\\dots a_l$ 和 $a_{l+1}\\dots a_n$。\n\n由于小明强迫症很严重，他不希望对于这两个子段，其中一个是另一个的 **子序列**，换句话说，他不希望其中一个子段可以通过删掉若干（可能为 $0$）个元素变成另一个。\n\n在父母出门的时候...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments