题目详情题解（0）讨论（0）提交记录（0）

CF2061D.Kevin and Numbers

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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" 均会被识别为肯定回答。

输入输出样例

  • 输入#1

    9
2 1
4 5
9
2 1
3 6
9
4 2
1 2 2 2
3 4
4 2
1 1 3 3
3 5
4 2
1 2 3 4
3 5
5 5
1 2 3 4 5
5 4 3 2 1
4 2
1 1 1 1
1 1
4 4
1 1 1 1
1 1 1 2
1 1
1
1000000000

    输出#1

    Yes
No
Yes
Yes
No
Yes
No
No
No

说明/提示

第一个测试用例中，可以删除 $ 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 完成

输入解题思路，AI测评打分。不知道怎么写?

首页