CF2125F.Timofey and Docker

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

不久前，Timofey 了解了 docker，现在他想在一次会议上做关于它的报告。他已经准备好了文本 $s$ 。

有 $n$ 位与会者。第 $i$ 位与会者只有在文本中连续子串“docker”出现的次数不少于 $l_i$ 且不多于 $r_i$ 时，才能听懂 Timofey 的报告。

为了让尽可能多的人了解 docker，Timofey 可以修改文本中的字符。

请你帮助 Timofey 计算，最少需要修改多少个字符，才能让最多数量的与会者听懂报告。

输入格式

每组测试数据包含若干组测试用例。第一行包含一个整数 $t$ （ $1 \le t \le 10^{4}$ ），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个字符串 $s$ （ $1 \le |s| \le 5 \cdot 10^{5}$ ），即 Timofey 的文本，由小写拉丁字母组成。

第二行包含一个整数 $n$ （ $1 \le n \le 5 \cdot 10^{5}$ ），表示与会者的数量。

接下来的 $n$ 行，每行包含两个整数 $l_i, r_i$ （ $1 \le l_i \le r_i \le 10^{9}$ ）。

输入数据的额外约束：

所有测试用例中 $|s|$ 的总和不超过 $5 \cdot 10^{5}$ ；
所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^{5}$ 。

输出格式

对于每组测试用例，输出一个整数，表示最少需要修改多少个字符，才能让最多数量的与会者听懂报告。

输入输出样例

输入#1

2
dockerdockerxxxxxx
3
3 3
2 4
1 5
ljglsjfkdieufj
5
1 5
3 3
2 4
3 7
2 9

输出#1

6
11

输入#2

4
dockerdockerdockerdockzzdockzz
4
1 1
1 1
4 5
4 5
docker
5
1 1
2 2
3 3
4 4
5 5
ddddddoooooocccccckkkkkkeeeeeerrrrrr
10
1 200
500 600
1 600
6 6
6 6
500 2000
6 400
89 90
4 7
1 10
dockerdockerdockerdockzzdockzz
4
2 2
2 2
4 5
4 5

输出#2

说明/提示

我们详细分析第一个测试用例：

在第一个测试用例中，可以将字符串末尾所有的 'x' 全部改为单词“docker”，这样所有 $3$ 位与会者都能听懂报告；
在第二个测试用例中，可以将 $s$ 中的部分字符修改如下：“ $l\color{red}{docker}kd\color{red}{ocker}$ ”，这样最多有 $3$ 位与会者能听懂报告。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页