← 返回题目列表

AtCoder · arc194_e

E. 交换 0^X 和 1^Y

中文机器翻译题面 查看原题

分数: 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} to 1 和每个 S_{i+Y}, S_{i+Y+1}, \ldots, S_{i+Y+X-1} to 0.

  • (操作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} to 0 和每个 S_{i+X}, S_{i+X+1}, \ldots, S_{i+X+Y-1} to 1.

约束

  • 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.