题解 | #D 与集合#

给出一个看上去挺厉害的随机化算法，欢迎 Hack。

首先考虑判掉一些特殊情况：

• 总共 $\mathrm{\ne }0\backslash ne0$ 的数都不到 $kk$ 个，一定分不出来；

• 全局 $sum=0sum=0$，且 $k=1k=1$，一定分不出来；

然后通过一个 $bb$ 数组先把所有的 $\mathrm{\ne }0\backslash ne0$ 的数记录下来：

考虑将 $b_1\cdots b_{k}b\_1\backslash cdots\; b\_k$ 放进 $kk$ 个集合，然后剩下来的 $b_{k+1}\cdots b_{b_0}b\_\{k+1\}\backslash cdots\; b\_\{b\_0\}$（$b_{0}b\_0$ 表示 $bb$ 数组的长度，即 $\mathrm{\ne }0\backslash ne0$ 的数）全部随机扔到某个集合中。

但是这样其实还不是很优，比如他给了一个类似：

• -9 -9 -9 ... -9 1 1 1 1 ... 1

这样的东西（其中 -9 和 1 的个数都是 $99$ 个），那我们岂不是扫描完一遍都找不到解？

没关系，把 $bb$ 打乱就好啦！

请出我们的致胜法宝：std::random_shuffle，这个函数可以用来打乱一个数组，使之无序。

然后我们再把这个过程重复 $100100$ 次，如果还找不到解就证明真的无解了！

std::stable_sort(a + 1, a + 1 + n);
int num = 0;
for (int i = 1; i <= n; ++i)
  num += (a[i] == 0);
if (n - num < k) { puts("NO"); return 0; }
int sum = 0;
for (int i = 1; i <= n; ++i) sum += a[i];
if (k == 1 && sum == 0) { puts("NO"); return 0; }
for (int i = 1; i <= n; ++i) if (a[i]) b[++b[0]] = a[i];
int times = 100;
do{
  std::random_shuffle(b + 1, b + 1 + b[0]);
  int Sum = 0;
  for (int i = k + 1; i <= b[0]; ++i) Sum += b[i];
  for (int i = 1; i <= k; ++i)
    if (b[i] + Sum != 0) {
      puts("YES");
      print(1 + num + b[0] - k), putchar(' ');
      print(b[i]), putchar(' ');
      while (num--) print(0), putchar(' ');
      for (int j = k + 1; j <= b[0]; ++j) print(b[j]), putchar(' ');
      putchar('\n');
      for (int j = 1; j <= k; ++j) {
        if (j != i) { print(1), putchar(' '); print(b[j]), putchar('\n');
        }
      }
      return 0;
    }
} while(times--);
puts("NO");