309845: CF1744A. Number Replacement

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Number Replacement

题意翻译

给定一个字符串以及一串数,你可以将数列中所有相同的数改为任意一个字母,问能否将数列改变成给定的字符串。 注:改成字母后,位置不变。

题目描述

An integer array $ a_1, a_2, \ldots, a_n $ is being transformed into an array of lowercase English letters using the following prodecure: While there is at least one number in the array: - Choose any number $ x $ from the array $ a $ , and any letter of the English alphabet $ y $ . - Replace all occurrences of number $ x $ with the letter $ y $ . For example, if we initially had an array $ a = [2, 3, 2, 4, 1] $ , then we could transform it the following way: - Choose the number $ 2 $ and the letter c. After that $ a = [c, 3, c, 4, 1] $ . - Choose the number $ 3 $ and the letter a. After that $ a = [c, a, c, 4, 1] $ . - Choose the number $ 4 $ and the letter t. After that $ a = [c, a, c, t, 1] $ . - Choose the number $ 1 $ and the letter a. After that $ a = [c, a, c, t, a] $ . After the transformation all letters are united into a string, in our example we get the string "cacta". Having the array $ a $ and the string $ s $ determine if the string $ s $ could be got from the array $ a $ after the described transformation?

输入输出格式

输入格式


The first line contains a single integer $ t $ $ (1 \leq t \leq 10^3 $ ) — the number of test cases. Then the description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 50 $ ) — the length of the array $ a $ and the string $ s $ . The second line of each test case contains exactly $ n $ integers: $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 50 $ ) — the elements of the array $ a $ . The third line of each test case contains a string $ s $ of length $ n $ , consisting of lowercase English letters.

输出格式


For each test case, output "YES", if we can get the string $ s $ from the array $ a $ , and "NO" otherwise. You can output each letter in any case.

输入输出样例

输入样例 #1

7
5
2 3 2 4 1
cacta
1
50
a
2
11 22
ab
4
1 2 2 1
aaab
5
1 2 3 2 1
aaaaa
6
1 10 2 9 3 8
azzfdb
7
1 2 3 4 1 1 2
abababb

输出样例 #1

YES
YES
YES
NO
YES
YES
NO

说明

The first test case corresponds to the sample described in the statement. In the second test case we can choose the number $ 50 $ and the letter a. In the third test case we can choose the number $ 11 $ and the letter a, after that $ a = [a, 22] $ . Then we choose the number $ 22 $ and the letter b and get $ a = [a, b] $ . In the fifth test case we can change all numbers one by one to the letter a.

Input

题意翻译

给定一个字符串以及一串数,你可以将数列中所有相同的数改为任意一个字母,问能否将数列改变成给定的字符串。 注:改成字母后,位置不变。

Output

**数替换**

**题意翻译:**
给定一个字符串以及一个整数数组,你可以将数组中所有相同的整数替换为任意一个字母,要求判断能否将数组通过替换变成给定的字符串。注意,替换为字母后,数组中字母的位置不变。

**题目描述:**
一个整数数组 $ a_1, a_2, \ldots, a_n $ 可以通过以下步骤转换成一个小写英文字母数组:

- 当数组中至少还有一个数字时,执行以下操作:
- 从数组 $ a $ 中选择任意一个数字 $ x $,并选择英文字母表中的任意一个字母 $ y $。
- 将数组中所有出现的数字 $ x $ 替换为字母 $ y $。

例如,如果我们有一个数组 $ a = [2, 3, 2, 4, 1] $,可以按以下方式转换:

- 选择数字 $ 2 $ 和字母 c,得到 $ a = [c, 3, c, 4, 1] $。
- 选择数字 $ 3 $ 和字母 a,得到 $ a = [c, a, c, 4, 1] $。
- 选择数字 $ 4 $ 和字母 t,得到 $ a = [c, a, c, t, 1] $。
- 选择数字 $ 1 $ 和字母 a,得到 $ a = [c, a, c, t, a] $。

转换后,所有字母合并成一个字符串,在我们的例子中,得到字符串 "cacta"。

给定数组 $ a $ 和字符串 $ s $,判断字符串 $ s $ 是否可以通过上述转换从数组 $ a $ 得到?

**输入输出格式:**

**输入格式:**
第一行包含一个整数 $ t $ $ (1 \leq t \leq 10^3) $ —— 测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $ $ (1 \leq n \leq 50) $ —— 数组 $ a $ 和字符串 $ s $ 的长度。

每个测试用例的第二行包含 $ n $ 个整数:$ a_1, a_2, \ldots, a_n $ $ (1 \leq a_i \leq 50) $ —— 数组 $ a $ 的元素。

每个测试用例的第三行包含一个长度为 $ n $ 的字符串 $ s $,由小写英文字母组成。

**输出格式:**
对于每个测试用例,如果能从数组 $ a $ 得到字符串 $ s $,则输出 "YES",否则输出 "NO"。每个字母的输出大小写均可。

**输入输出样例:**

**输入样例 #1:**
```
7
5
2 3 2 4 1
cacta
1
50
a
2
11 22
ab
4
1 2 2 1
aaab
5
1 2 3 2 1
aaaaa
6
1 10 2 9 3 8
azzfdb
7
1 2 3 4 1 1 2
abababb
```

**输出样例 #1:**
```
YES
YES
YES
NO
YES
YES
NO
```

**说明:**
第一个测试用例对应于题目描述中的示例。

在第二个测试用例中,我们可以选择数字 $ 50 $ 并将其替换为字母 a。

在第三个测试用例中,我们可以选择数字 $ 11 $ 并将其替换为字母 a,然后 $ a = [a, 22] $。接着选择数字 $ 22 $ 并替换为字母 b,得到 $ a = [a, b] $。

在第五个测试用例中,我们可以将所有数字逐个替换为字母 a。**数替换** **题意翻译:** 给定一个字符串以及一个整数数组,你可以将数组中所有相同的整数替换为任意一个字母,要求判断能否将数组通过替换变成给定的字符串。注意,替换为字母后,数组中字母的位置不变。 **题目描述:** 一个整数数组 $ a_1, a_2, \ldots, a_n $ 可以通过以下步骤转换成一个小写英文字母数组: - 当数组中至少还有一个数字时,执行以下操作: - 从数组 $ a $ 中选择任意一个数字 $ x $,并选择英文字母表中的任意一个字母 $ y $。 - 将数组中所有出现的数字 $ x $ 替换为字母 $ y $。 例如,如果我们有一个数组 $ a = [2, 3, 2, 4, 1] $,可以按以下方式转换: - 选择数字 $ 2 $ 和字母 c,得到 $ a = [c, 3, c, 4, 1] $。 - 选择数字 $ 3 $ 和字母 a,得到 $ a = [c, a, c, 4, 1] $。 - 选择数字 $ 4 $ 和字母 t,得到 $ a = [c, a, c, t, 1] $。 - 选择数字 $ 1 $ 和字母 a,得到 $ a = [c, a, c, t, a] $。 转换后,所有字母合并成一个字符串,在我们的例子中,得到字符串 "cacta"。 给定数组 $ a $ 和字符串 $ s $,判断字符串 $ s $ 是否可以通过上述转换从数组 $ a $ 得到? **输入输出格式:** **输入格式:** 第一行包含一个整数 $ t $ $ (1 \leq t \leq 10^3) $ —— 测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ $ (1 \leq n \leq 50) $ —— 数组 $ a $ 和字符串 $ s $ 的长度。 每个测试用例的第二行包含 $ n $ 个整数:$ a_1, a_2, \ldots, a_n $ $ (1 \leq a_i \leq 50) $ —— 数组 $ a $ 的元素。 每个测试用例的第三行包含一个长度为 $ n $ 的字符串 $ s $,由小写英文字母组成。 **输出格式:** 对于每个测试用例,如果能从数组 $ a $ 得到字符串 $ s $,则输出 "YES",否则输出 "NO"。每个字母的输出大小写均可。 **输入输出样例:** **输入样例 #1:** ``` 7 5 2 3 2 4 1 cacta 1 50 a 2 11 22 ab 4 1 2 2 1 aaab 5 1 2 3 2 1 aaaaa 6 1 10 2 9 3 8 azzfdb 7 1 2 3 4 1 1 2 abababb ``` **输出样例 #1:** ``` YES YES YES NO YES YES NO ``` **说明:** 第一个测试用例对应于题目描述中的示例。 在第二个测试用例中,我们可以选择数字 $ 50 $ 并将其替换为字母 a。 在第三个测试用例中,我们可以选择数字 $ 11 $ 并将其替换为字母 a,然后 $ a = [a, 22] $。接着选择数字 $ 22 $ 并替换为字母 b,得到 $ a = [a, b] $。 在第五个测试用例中,我们可以将所有数字逐个替换为字母 a。

加入题单

上一题 下一题 算法标签: