← 返回题目列表

AtCoder · agc077_a

A. 反向 A…B

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

分数: 800 点

问题陈述

给你字符串 X 和 Y 长度 N 组成 A 和 B。让 X_i 表示 i- 第一个字符 X.

判断是否可以使 X 等于 Y 通过在之间执行以下操作 0 和 \left\lfloor \frac{N}{2} \right\rfloor 次,含在内。

  • 选择一对整数 (l, r) 这样 1\leq l < r \leq N, X_l= A,和 X_r= B。反转元素 X 来自 l-第 r- 第一个位置。这里,“反转元素 X 来自 l-第 r第位置”表示同时替换 X_l,X_{l+1},\ldots,X_{r-1},X_r 与 X_r,X_{r-1},\ldots,X_{l+1},X_l.

如果可以的话 X 等于 Y,输出这样的操作序列。

T 给出了测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 2.5\times 10^5
  • 2 \leq N \leq 5\times 10^5
  • 总和 N 所有测试用例最多 5\times 10^5.
  • X 和 Y 是长度的字符串 N 组成 A 和 B.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
X
Y

输出

输出以下问题的答案 \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T 按以下格式顺序排列。

如果不可能 X 等于 Y 使用之间 0 和 \left\lfloor \frac{N}{2} \right\rfloor 操作,包含,输出 No.

如果可能,按以下格式输出操作序列:

Yes
K
l_1 r_1
l_2 r_2
\vdots
l_K r_K

这里 K 是操作次数,并且 l_i, r_i 是整数 l, r 选择于 i-第次操作。这些必须满足以下条件:

  • 0 \leq K \leq \left\lfloor \frac{N}{2} \right\rfloor
  • 1 \leq l_i < r_i \leq N

如果存在多个有效的操作序列,则其中任何一个都将被接受。


示例输入 1

3
5
ABAAB
ABBAA
4
AAAA
BBBB
10
BABBAABBAA
BBBBAAABAA

示例输出 1

Yes
1
3 5
No
Yes
3
2 7
4 6
3 5

在第一个测试用例中, X_3= A 和 X_5= B,所以我们可以执行元素反转的操作 X 来自 3-rd 到 5- 第一个位置。经过这次操作后, X is ABBAA,等于 Y.

在第二个测试用例中,不可能使 X 等于 Y 无论执行什么操作。