分数: 900 点
问题陈述
给你两个字符串 S 和 T,每个长度 N 并由以下组成 0 和 1,以及两个正整数 X 和 Y。对于 i = 1, 2, \ldots, N,让 S_i 表示 i- 第一个字符 S.
判断是否可以使 S 相同于 T 通过以任何顺序重复执行操作 A 和 B 任意次数(可能为零):
-
(操作A)选择一个整数 i 满意 1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+X-1} =
0,和 S_{i+X} = S_{i+X+1} = \cdots = S_{i+X+Y-1} =1,然后更改每个 S_{i}, S_{i+1}, \ldots, S_{i+Y-1} to1和每个 S_{i+Y}, S_{i+Y+1}, \ldots, S_{i+Y+X-1} to0. -
(操作B)选择一个整数 i 满意 1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+Y-1} =
1,和 S_{i+Y} = S_{i+Y+1} = \cdots = S_{i+Y+X-1} =0,然后更改每个 S_{i}, S_{i+1}, \ldots, S_{i+X-1} to0和每个 S_{i+X}, S_{i+X+1}, \ldots, S_{i+X+Y-1} to1.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq X, Y \leq N
- S 和 T 是长度的字符串 N 组成
0和1. - 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X Y S T
输出
如果可以的话 S 相同于 T,打印 Yes;否则,打印 No.
示例输入 1
9 2 1 000111001 011000011
示例输出 1
Yes
下面的程序可以改造 S 进入 T:
- 首先,执行操作 A i = 2。现在, S =
010011001. - 接下来,执行操作 B i = 6。现在, S =
010010011. - 最后,执行操作 A i = 3。现在, S =
011000011.
因此,打印 Yes.
示例输入 2
1 1 1 0 1
示例输出 2
No
不可能使 S 相同于 T。因此,打印 No.