AdditionalFile5575.zip

#5575. 「RMI 2025」Cheap AI

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

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "cheapai.h"。

题目描述

题目译自 Romanian Master of Informatics 2025 Day2 T1 「Cheap AI」

你是一只压力山大的小老鼠，正试图在人工智能初创公司飞速崛起的浪潮中求生。竞争对手无处不在，获得技术优势似乎几乎是不可能的。在绝望地寻找优势的过程中，你偶然发现了 CheapAI™，这是一家资金少得可怜的初创公司，就连你也能够在那里谋得一份差事。你的第一个任务是构建世界上最便宜的分词器（Tokenizer）。

你被 CheapAI™ 录用了，首要任务就是构建分词器。不幸的是，预算非常有限，除了英语字母表的 $26$ 个字母外，你只能负担得起一个长度不超过 $K$ 的额外标记（token）。

给定一个由小写英文字母组成的字符串 $S$ 和一个数字 $K$。你的目标是选择一个长度不超过 $K$ 的标记（字符串），使得如果将该标记在 $S$ 中出现的部分（互不重叠）替换为特殊字符 #，所得结果字符串的总长度最小。

给定一个数字 $K$ 和一个由小写英文字母组成的字符串 $S$，选择一个非空字符串（标记）$t$，满足 $1 \leq |t| \leq K$，将 $S$ 中出现的 $t$（选择互不重叠的部分）替换为特殊字符 #，从而得到一个长度最小的最终字符串。

请确定这个最小长度。

实现细节

你需要实现以下函数：

int solve(int K, std::string S);

该函数接收 $K$ 和 $S$ 作为参数，你需要确定在将选定的长度不超过 $K$ 的标记的（互不重叠）出现位置替换为特殊字符 # 后，所获得的字符串的最小长度。

样例 1

输入

5 
aabaabacbbaabaa

输出

7

样例 2

输入

8 
aaaaaaaaaaaaaaaaaaa

输出

4

数据范围与提示

对于所有输入数据，满足：

• $1 \leq K \leq |S| \leq 200000$
• $S$ 由小写英文字母组成。

详细子任务附加限制及分值如下表所示。