#P6428. 「JOI 2023 Final」现代机器
「JOI 2023 Final」现代机器
「JOI 2023 Final」现代机器
题目描述
Bitaro 生日这天收到了一个 JOI 机作为生日礼物。JOI 机由一个球, 条光带和 个按钮组成。光带从 到 编号。当 Bitaro 打开开关时,光带 会发出颜色 的光(蓝光 () 或红光 ())。按钮从 到 编号。如果 Bitaro 按下按钮 ,将发生如下事情。
- 把球放置在光带 上。
- 光带 变成红色(不管它原来是什么颜色)
- 进行如下操作,直到球被移除。
令 为球目前所在的光带编号。- 如果光带 是蓝色,
光带 变为红色。在此之后,如果 ,这个球就被移除。否则,球移向光带 。 - 如果光带 是红色,
光带 变为蓝色。在此之后,如果 ,这个球就被移除。否则,球移向光带 。
- 如果光带 是蓝色,
Bitaro 对 JOI 机十分感兴趣。他计划进行 次实验。在第 次实验中,在 Bitaro 开启电源后,他将按 的顺序按下这些开关。在 Bitaro 按下一个开关后,他将等到球被移除后再按下下一个开关。
给定 JOI 机和实验的情况,写一个程序计算对于每个实验,当实验结束后红色的光带有多少。
每次实验都从初始颜色串 重新开始;同一次实验内,各次按按钮造成的颜色变化会保留。不同按钮可以把球放到同一条光带上。按按钮时先强制把 变红,再执行移动规则,因此这一轮第一次处理该光带时,会将其变蓝并向右移动或在右端移除。
输入格式
第一行两个整数 。
第二行一个长度为 的字符串 ,字符串中仅包含字符 和 。
第三行 个整数 。
第四行一个整数 。
接下来 行,每行两个整数 。
输出格式
输出 行,第 行输出一个整数,表示当第 个实验结束后红色的光带有多少。
样例输入 1
5 1
RBRRB
4
1
1 1
样例输出 1
1
样例输入 2
5 3
RBRBR
1 3 4
2
2 3
1 3
样例输出 2
5
0
样例输入 3
10 3
BBRRBRBRRB
2 10 5
1
1 3
样例输出 3
2
样例输入 4
10 10
RRRRRRRRRR
3 1 4 1 5 9 2 6 5 3
5
1 7
2 8
3 9
4 10
1 10
样例输出 4
4
8
10
0
9
样例输入 5
10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6
样例输出 5
2
6
0
10
7
样例输入 6
30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10
样例输出 6
21
15
15
4
17
16
14
20
12
23
样例 1 说明
按下按钮 后,球从光带 开始,其颜色先被设为红色。随后球依次经过 ,再从右端移除。颜色依次变为
$$\texttt{RBRRB}\to\texttt{RBRBB}\to\texttt{RBRBR}\to\texttt{RBRRR}\to\texttt{RBBRR}\to\texttt{RBBBR}\to\texttt{RBBBB}.$$最后只有光带 为红色,答案为 。
数据范围与提示
对于全部数据,满足
- 不是 就是
详细子任务附加限制及分值如下表。
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| 且 是 | ||
| 存在一个整数 ,使得对于每个 都有 是 ,对于每个 都有 是 | ||
| 或 | ||
| 无附加限制 |