CF2170D Almost Roman

我们定义一个只包含字母 “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$ 大于等于字符串中问号 '?' 的数量。

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

（无） 由 ChatGPT 5 翻译