← 返回题目
题库练习 Almost Roman
← 上一题 下一题 →

A16729 | Almost Roman

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

我们定义一个只包含字母 “XVI” 的字符串的值如下：

- 字母 'X' 的值为 $10$；
- 字母 'V' 的值为 $5$；
- 字母 'I' 的值为 $1$ 或 $-1$：如果它后面的位置上是字母 'X' 或 'V'，则为 $-1$；否则为 $1$；
- 整个字符串的值等于其中所有字母值的总和。

现在你得到了一个仅包含字符 “XVI?” 的字符串，并会询问 $q$ 次。

在第 $i$ 次询问时，会给出三个整数：

- $c_X,~c_V,~c_I$ ——分别代表可用字母 'X'、'V' 和 'I' 的数量。

你需要求出，若将字符串中的所有问号用字母 'X'、'V'、'I' 替换（要求每种字母的使用次数不超过其可用数量），该字符串可以得到的最小值是多少。

输入格式

第一行包含一个整数 $t$（$1\leq t\leq 10^4$）——表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\leq n,q \leq 3\times 10^5$）——表示字符串长度和询问数。

第二行给出一个长度为 $n$ 的字符串，字符串仅由 'X'、'V'、'I'、'?' 构成。

接下来的 $q$ 行，每行包含三个整数 $c_X,~c_V,~c_I$（$0\leq c_X, c_V, c_I\leq n$）——分别表示本次查询可用的 'X'、'V'、'I' 的个数。

【附加输入约束】

- 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$；
- 所有测试用例中 $q$ 的总和不超过 $3 \times 10^5$；
- 对于每个询问都有 $c_X + c_V + c_I$ 大于等于字符串中问号 '?' 的数量。

输出格式

对于每个询问，输出一个整数——表示将所有问号替换为可用字母后，字符串可能取得的最小值。

输入输出样例

输入 #1
4
3 3
???
3 0 0
2 3 1
0 1 2
10 7
??IV?VXIV?
0 0 4
4 4 0
1 1 2
1 1 3
1 1 4
1 2 1
2 2 0
9 5
?V????IVV
9 2 4
4 1 5
0 1 4
4 8 1
3 2 7
3 2
I?V
0 1 0
0 0 1
输出 #1
30
9
5
25
43
36
27
25
42
53
19
17
19
33
17
9
5
C++ 编辑器
输入
输出