题解 | #D 与集合#

D 与集合

https://ac.nowcoder.com/acm/problem/229483

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

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

  • 总共 0\ne0 的数都不到 kk 个,一定分不出来;

  • 全局 sum=0sum=0,且 k=1k=1,一定分不出来;

然后通过一个 bb 数组先把所有的 0\ne0 的数记录下来:

考虑将 b1bkb_1\cdots b_k 放进 kk 个集合,然后剩下来的 bk+1bb0b_{k+1}\cdots b_{b_0}b0b_0 表示 bb 数组的长度,即 0\ne0 的数)全部随机扔到某个集合中。

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

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

这样的东西(其中 -91 的个数都是 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");
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 15:39
希望奇迹发生的布莱克...:真的是 现在卷实习就是没苦硬吃
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务