#CF2272E. Memory Cell Interception
Memory Cell Interception
题目描述
有两个线程 和 ,以及一个共享内存单元。初始时,内存单元中的值为 。
线程 有一个长度为 的固定命令序列 ,线程 有一个长度为 的固定命令序列 。每条命令要么是 (记为 ),要么是 (记为 )。
每个线程的命令必须按原始顺序执行。然而,两个线程的命令可以任意交错执行。换句话说,实际执行的是将 和 合并得到的一个长度为 的全局命令序列,且每个字符串内部的命令顺序保持不变。
例如,假设 , 。
- 序列 是一个合法的交错。对应的全局命令序列为 。
- 序列 不是合法的交错,因为 的命令未按原始顺序执行。
- 序列 不是合法的交错,因为它没有执行所有命令。
全局执行具有时间戳。在任何命令执行之前,时间戳为 。全局序列中第 个位置执行的命令的时间戳为 。
- 当 命令在时间戳 执行时,它将值 写入共享内存单元。
- 当 命令执行时,它读取共享内存单元中当前存储的时间戳值。
对于 或 中出现的每个 命令,求在两个命令序列的所有合法交错下,它能读取到多少种不同的值。
输入格式
每个测试包含多个测试用例。第一行包含测试用例数量 ()。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 和 ()——分别为线程 和 的命令序列长度。
第二行包含一个长度为 的字符串 ——线程 的命令序列。
第三行包含一个长度为 的字符串 ——线程 的命令序列。
和 的每个字符要么是 要么是 。字符串 和 各自至少包含一个字符 。
保证所有测试用例的 之和不超过 ,所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出两行。
第一行包含一组整数,表示 中每个 指令按顺序对应的答案。该序列的长度必须等于 中字母 的个数。
第二行包含一组整数,表示 中每个 指令按顺序对应的答案。该序列的长度必须等于 中字母 的个数。
样例
3
1 1
R
R
1 2
R
WR
3 3
WRW
RWR
1
1
2
2
4
3 4
说明
在第一个样例中,两个 命令都只能读取单元中初始设置的值 ,因此答案均为 。
在第二个样例中,有 种不同的交错方式(红色字母 表示 中的 ):
- :第一个 读取 ,第二个 读取 ;
- :第一个 读取 ,第二个 读取 ;
- :第一个 读取 ,第二个 读取 ;
综上,两个 命令都可能看到 种不同的值。
来源
转载自 Codeforces — Codeforces Round 1130 (Div. 2)。