CF2061D Kevin and Numbers
题目描述
Kevin 在黑板上写了一个长度为 $ n $ 的整数序列 $ a $。
Kevin 可以执行任意次数的以下操作:
- 选择黑板上两个满足 $ |x - y| \leq 1 $ 的整数 $ x, y $,将它们删除,并写入一个新整数 $ x + y $。
Kevin 想知道是否可以通过一系列操作将这些整数转换为长度为 $ m $ 的整数序列 $ b $。
两个序列 $ a $ 和 $ b $ 被认为是相同的,当且仅当它们的多重集完全相同。即对于任意数 $ x $,其在 $ a $ 中出现的次数必须等于在 $ b $ 中出现的次数。
输入格式
每个测试包含多个测试用例。第一行包含测试用例数量 $ t $($ 1 \le t \le 10^4 $)。接下来是测试用例描述。
每个测试用例的第一行包含两个整数 $ n $ 和 $ m $($ 1 \leq m \leq n \leq 2 \cdot 10^5 $)——$ a $ 的长度和 $ b $ 的长度。
第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $($ 1 \leq a_i \leq 10^9 $)。
第三行包含 $ m $ 个整数 $ b_1, b_2, \ldots, b_m $($ 1 \leq b_i \leq 10^9 $)。
保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
输出格式
对于每个测试用例,若可以将 $ a $ 转换为 $ b $,输出 "Yes";否则输出 "No"。
答案不区分大小写,例如 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。
说明/提示
第一个测试用例中,可以删除 $ 4 $ 和 $ 5 $,并写入 $ 9 $。
第二个测试用例中,无法删除 $ 3 $ 和 $ 6 $。
第三个测试用例中,一种可能的操作路径为:
1. 删除 $ 2 $ 和 $ 2 $,并写入 $ 4 $。此时剩余数字为 $ 1, 2, 4 $。
2. 删除 $ 1 $ 和 $ 2 $,并写入 $ 3 $。此时剩余数字为 $ 3, 4 $。
第四个测试用例中,一种可能的操作路径为:
1. 删除 $ 1 $ 和 $ 1 $,并写入 $ 2 $。此时剩余数字为 $ 2, 3, 3 $。
2. 删除 $ 2 $ 和 $ 3 $,并写入 $ 5 $。此时剩余数字为 $ 3, 5 $。
翻译由 DeepSeek R1 完成