思路总览

允许交换的限制是：只在相同的 $a_i$ 分组内任意交换 $s$ 的字符。因此，每个分组内 $s$ 的字符可以任意重排。要让重排后的 $s$ 与 $t$ 同构（即 $t_i$ 是 $s_i$ 的大写），等价于：

P3579.第1题-字符串同构

1000ms

Difficulty: 3

所属公司 : 饿了么

算法与标签>模拟

给定一个长度为 $n$ 的仅由小写字母组成的字符串 $s$ ，一个长度为 $n$ 的仅由大写字母组成的字符串 $t$ ，以及一个长度为 $n$ 的数组{ $a_1,a_2,...,a_n$ } $(a_i∈$ { $0,1$ })。

对于任意两个不同的下标 $1≦i < j≦n$ ，如果 $a_i=a_j$ ，则允许将字符串 $s$ 中下标为 $i$ 与 $j$ 的字符交换。

如果可以通过上述交换，使得对所有 $1≦i≦n$ 都有 $t_i$ 是 $s_i$ 的对应大写字母，则称 $s$ 与 $t$ 是同构的。你的任务是判断它们是否同构。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T (1≦T≦10^4)$ 代表数据组数，每组测试数据描述如下:

第一行输入一个整数 $n(1≦n≦2×10^5)$ ,表示字符串和数组的长度;

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n$ ( $a_i∈$ { $0,1$ }),表示限制数组;

第三行输入一个长度为 $n$ 的仅含小写字母的字符串 $s$ ;

第四行输入一个长度为 $n$ 的仅含大写字母的字符串 $t$ 。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

对于每一组测试数据，新起一行输出 $Yes$ ，如果字符串 $s$ 能通过允许的交换与 $t$ 同构，否则输出 $No$

输入

2
6
0 1 0 1 0 1
abccba
CAACBB
3
0 0 1
abc
AAC

输出

Yes
No

说明

下方所述的集合均指多重集合(不去重)。

在对于第一组测试数据， $a$ 将位置分为两组:

$a_i=0$ 的位置{ $1,3,5$ }， $s$ 中对应字符为{ $a,c,b$ }，其大写集合为{ $A,C,B$ }； $t$ 在这些位置上的字符为{ $C,A,B$ } 集合相同，可以通过组内重排匹配；

$a_i=1$ 的位置{ $2,4,6$ }， $s$ 中对应字符为{ $b,c,a$ }，其大写集合为{ $B,C,A$ }； $t$ 在这些位置上的字符为{ $A,C,B$ }，集合也相同。

因此答案为 $Yes$ 。

对于第二组测试数据， $a_i=0$ 的位置为{ $1,2$ }， $s$ 的大写集合为{ $A,B$ }，而t在这些位置的集合为{ $A,A$ }，不匹配，因此无法同构。

输入

预期输出（选填）