AdditionalFile3253.zip

P6878 [JOI 2020 Final] JJOOII 2

题目描述

定义有连续 $K$ 个 $\tt J$ 和连续 $K$ 个 $\tt O$ 和连续 $K$ 个 $\tt I$ 组成的字符串为 $K$ 阶 JOI 串。

比如，$\tt JJOOII$ 为 $2$ 阶 JOI 串，但是，注意要有顺序，比如 $\tt OOJJII$ 就不是 $2$ 阶 JOI 串。

现在，给定一个长度为 $N$ 的字符串 $S$，可以对他进行 $3$ 种操作：

• 操作 $1$：删除 $S$ 开头的字符
• 操作 $2$：删除 $S$ 结尾的字符
• 操作 $3$：删除 $S$ 除了开头和结尾之外的一个字符

我们要通过这些操作让 $S$ 变为 $K$ 阶 JOI 串。

但是，我们想让操作 $3$ 尽量的少。

所以我们想知道，变为 $K$ 阶 JOI 串操作 $3$ 最少需要进行多少次？

如果不能变为 $K$ 阶 JOI 串，那么输出 $-1$。

输入格式

第一行两个整数 $N,K$ 代表字符串长度和要构造的 JOI 串的阶数。
第二行 $N$ 个字符代表字符串 $S$。

输出格式

一行一个整数代表操作 $3$ 的最小进行次数。
如果不能变为 $K$ 阶 JOI 串，那么输出 $-1$。

输入输出样例 #1

输入 #1

10 2
OJIJOIOIIJ

输出 #1

2

输入输出样例 #2

输入 #2

9 3
JJJOOOIII

输出 #2

0

输入输出样例 #3

输入 #3

9 1
IIIOOOJJJ

输出 #3

-1

说明/提示

样例 1 解释

1. 进行一次操作 $1$，变为 $\tt JIJOIOIIJ$。
2. 进行一次操作 $2$，变为 $\tt JIJOIOII$。
3. 进行一次操作 $3$，删掉字符 $2$，变为 $\tt JJOIOII$。
4. 进行一次操作 $3$，删掉字符 $4$，变为 $\tt JJOOII$。

样例 2 解释

$\tt JJJOOOIII$ 已经是 $3$ 阶 JOI 串了，所以不需要进行操作。

样例 3 解释

$\tt IIIOOOJJJ$ 无法变为 $1$ 阶 JOI 串，无解。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（1 pts）：$N \le 21$。
• Subtask 2（12 pts）：$N \le 3000$。
• Subtask 3（87 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $3 \le N \le 2 \times 10^5$。
• $1 \le K \le \dfrac{N}{3}$。
• $S$ 只包含 $\tt J$，$\tt O$，$\tt I$ 且长度为 $N$。

说明

翻译自 第19回日本情報オリンピック　本選 B JJOOII 2。

#3253. 「JOI 2020 Final」JJOOII 2

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

译自 JOI 2020 Final T2「JJOOII 2 / JJOOII 2」

比太郎收到了一个长度为 $N$ 的字符串 $S$ 作为他的生日礼物，且这个字符串仅由 $\texttt{J},\texttt{O},\texttt{I}$ 组成。

对于所有正整数 $K$，若一个字符串仅由 $K$ 个连续的 $\texttt J$，$K$ 个连续的 $\texttt O$ 和 $K$ 个连续的 $\texttt I$ 顺次连接而成，则我们称这个字符串为 $K$ 级 JOI-串。
例如，$\texttt{JJOOII}$ 就是一个 $2$ 级 JOI-串。

比太郎热衷于构造 $K$ 级 JOI-串，于是他打算通过以任意顺序使用以下三个操作任意次来将字符串 $S$ 构造为一个 $K$ 级 JOI-串：

1. 删除 $S$ 的开头字符。
2. 删除 $S$ 的结尾字符。
3. 删除 $S$ 的一个非开头且非结尾的字符。

由于操作 $3$ 十分耗时，比太郎想要尽可能少地使用操作 $3$。
请对于给定的长度为 $N$ 的字符串 $S$ 和一个正整数 $K$，输出将其构造为 $K$ 级 JOI-串所需要的最少的操作 $3$ 的次数。
若无解，请输出 $-1$。

输入格式

第一行，两个正整数 $N,K$。
第二行，一个字符串 $S$。

输出格式

一行，一个整数，表示操作 $3$ 的最少次数或 $-1$。

样例 1

输入

10 2
OJIJOIOIIJ

输出

2

你可以通过按以下顺序执行操作来将 $S$ 构造为一个 $K$ 级 JOI-串：

1. 使用操作 $1$，$S$ 变为 $\texttt{JIJOIOIIJ}$。
2. 使用操作 $2$，$S$ 变为 $\texttt{JIJOIOII}$。
3. 使用操作 $3$ 删除第 $2$ 个字符，$S$ 变为 $\texttt{JJOIOII}$。
4. 使用操作 $3$ 删除第 $4$ 个字符，$S$ 变为 $\texttt{JJOOII}$。

可以证明没有更优解，故输出 $2$。

样例 2

输入

9 3
JJJOOOIII

输出

0

显然，在这个样例中你甚至不需要任何操作。

样例 3

输入

9 1
IIIOOOJJJ

输出

-1

显然，在这个样例中你的一切操作都是无用功。

数据范围与提示

对于所有测试数据，$3 \le N \le 2 \times 10^5, 1 \le K \le \frac N3, S$ 是一个仅有 $\texttt J, \texttt O, \texttt I$ 组成的字符串。

子任务编号	分值	$N$
$1$	$1$	$N \le 21$
$2$	$12$	$N \le 3000$
$3$	$87$