[科大国创杯小学组 2025] 改写

Luogu

IDLGB4323

Time1000ms

Memory512MB

DifficultyP5

动态规划 DP贪心2025分类讨论科创活动小学活动科大国创杯

小可可在学习字符串算法！一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i = r_{m+1-i}$ 对所有 $1 \leq i \leq m$ 均成立。例如 $\tt{aaabaaa}$，$\tt{abba}$ 都是回文串，但 $\tt{aaabaa}$ 不是回文串。给定一个字符串 $s$，把 $s$ 分成若干个非空子段，使得每一个子段都不是回文的，同时最大化划分出的子段数目，请你输出最大划分数，无解则输出 $-1$。子段的定义为：一个字符串保留任意连续字符后形成的字符串。由于字符串 $s$ 可能很长，我们将会按照 $c, len$ 的形式给出整个字符串，具体含义见输入格式。 ## Input 第一行一个整数 $T$ 表示数据组数。对于每组数据，第一行输入一个数 $n$ 表示极长连续相同字母段的数量。接下来 $n$ 行中，第 $i$ 行包括一个 $a$ 到 $z$ 之间的小写字母 $c_i$ 和一个整数 $len_i$，分别表示该段的数字以及长度，保证对于所有大于 $1$ 的 $i$，均满足 $c_{i-1} \neq c_i$。 ## Output 输出共 $T$ 行，每行输出一个整数，表示最大的划分段数，若无解则输出 $-1$。 [samples] ## Background Subtask 0 为民间数据（最后两组测试点为民间 hack 数据），Subtask 1 为官方数据。 ## Note ### 样例解释 - 对于第一组数据，序列为 $\tt{ba}$，且只存在 $\tt{ba}$ 这一种划分方案，因此答案为 $1$。 - 对于第二组数据，序列为 $\tt{bbbb}$，显然没有合法方案。 - 对于第三组数据，序列为 $\tt{aabbabbaba}$，存在一种划分出四段的方案: $\tt{aabb}$，$\tt{ab}$，$\tt{ba}$，$\tt{ba}$，可以证明没有答案更优的划分方式。 - 对于第四组数据，序列为 $\tt{aabaaccaa}$，存在一种划分出三段的方案: $\tt{aaba}$，$\tt{ac}$，$\tt{caa}$，可以证明没有答案更优的划分方式。 - 对于第五组数据，序列为 $\tt{aba}$，容易发现无论怎么划分，都至少有一个回文串，所以无解。 ### 约定和数据范围 - 数据点 $1$，$T = 10$，$1 \leq n \leq 3$，$1 \leq len_i \leq 2$。 - 数据点 $2$，$T = 10$，$1 \leq n \leq 3$，$1 \leq len_i \leq 10^9$。 - 数据点 $3, 4$，$T = 10$，$1 \leq n \leq 150$，$1 \leq len_i \leq 2$。 - 数据点 $5, 6$，$T = 10$，$1 \leq n \leq 150$，$1 \leq len_i \leq 10^9$。 - 数据点 $7 \sim 9$，$T = 10$，$1 \leq n \leq 2.5 \times 10^3$，$1 \leq len_i \leq 2$。 - 数据点 $10 \sim 12$，$T = 10$，$1 \leq n \leq 2.5 \times 10^3$，$1 \leq len_i \leq 10^9$。 - 数据点 $13 \sim 16$，$T = 10, 1 \leq n \leq 10^5, 1 \leq len_i \leq 2$。 - 数据点 $17 \sim 20$，$T = 10, 1 \leq n \leq 10^5, 1 \leq len_i \leq 10^9$。

Samples

Input #1

5
2
b 1
a 1
1
b 4
7
a 2
b 2
a 1
b 2
a 1
b 1
a 1
5
a 2
b 1
a 2
c 2
a 2
3
a 1
b 1
a 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[科大国创杯小学组 2025] 改写",
    "description": {
      "content": "小可可在学习字符串算法！ 一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i = r_{m+1-i}$ 对所有 $1 \\leq i \\leq m$ 均成立。例如 $\\tt{aaabaaa}$，$\\tt{abba}$ 都是回文串，但 $\\tt{aaabaa}$ 不是回文串。 给定一个字符串 $s$，把 $s$ 分成若干个非空子段，使得每一个子段都不是回文的，同时最大化划分出的子段",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4323"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小可可在学习字符串算法！\n\n一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i = r_{m+1-i}$ 对所有 $1 \\leq i \\leq m$ 均成立。例如 $\\tt{aaabaaa}$，$\\tt{abba}$ 都是回文串，但 $\\tt{aaabaa}$ 不是回文串。\n\n给定一个字符串 $s$，把 $s$ 分成若干个非空子段，使得每一个子段都不是回文的，同时最大化划分出的子段...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments