3

给定 n 个数字，您可以任意次数执行以下操作：选择数字的任何子集，其中没有一个为 0。将子集中的数字减 1，将不在子集中的数字增加 K。

是否可以执行使除其中一个之外的所有数字都变为 0 的操作？

输入：第一行包含测试用例 T 的数量。接下来是 2*T 行，每个用例 2 行。测试用例的第一行包含数字 n 和 K。下一行包含 n 个数字，a_1...a_n。

输出：输出T行，每个测试用例对应一个。对于测试用例，如果存在描述的操作序列，则输出“YES”，否则输出“NO”。

样本输入：

3
2 1
10 10
3 2
1 2 2
3 2
1 2 3

样本输出：

YES
YES
NO

约束：

1 <= T <= 1000
2 <= n <= 100
1 <= K <= 10
0 <= a_i <= 1000

我已经通过以下算法接受了我的解决方案---

a[i] is value in ith cell
n[i] is number of times it is selected in subset
T is total number of times the operation is done

=> a[i] - n[i] + (T - n[i])*K = 0 for all except 1
=> a[i]= n[i] (K+1) -TK 
=> a[i] = (K+1)(n[i]-T) + T

因此，除 1（将变为 0）和 T 除以 K+1 时，所有 a[i] 的余数都应该相同。我怀疑这个条件是必要的，但它是充分的吗？

4

1 回答 1

1

步骤1

想象一个包含以下内容的动作：

  1. 选择由所有数字组成的子集 A，其中 a[i]>=K+1
  2. 选择由整个集合 K 次组成的子集

子集 A 中的数字将减少 K+1 倍，而集合 A 之外的数字将保持不变（增加 K，然后减少 K 倍）。

重复这个动作，直到所有数字都小于 K+1。

这一步会将数字更改为它们的余数模 K+1。

第2步

现在假设所有数字都相同（1 除外）。

我们现在可以选择由整个集合组成的子集（奇数除外）。

这会将所有数字减 1（奇数除外）。重复这个选择，直到我们一直减少到 0。

结论

因此，如果所有数字（除了一个）具有相同的余数模 K+1，我们可以使用步骤 1 将它们都降低到相同的级别，然后使用步骤 2 将公共级别降低到 0。

于 2013-02-11T19:17:13.560 回答