2019-Acyclic_SD/AugTrain-29

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(Train-29.png,500px)]]

== 总结 ==

=== Todobe ===

读题杀我们。 B题没发现数据随机。

今天签完三道题之后之后我们又陷入了三人没题写，大家都会我不会的状态。

感觉沉寂了好一会儿，不过好在没有一直看那两个题，xx过了D，不过貌似是乱搞过的。
然后我和jj开了K，商量了一下，感觉这题有点shishi哒，还是我去写了。

但是感觉人不太清醒，思路不是很清晰，写完交上去T了，改成二分WA掉，最后jj当小黄鸭，我找到了一些错误，有两个模数，在算的时候模乱了，改了之后就过掉了。

这个图的罚时是虚假的，最后那个K交上去submit failed，于是就直接去hdu交了几发，所以有些罚时是没有算进去的。

然后就是我们还有一些琐碎的知识点需要掌握。

=== ZhljJoan ===
K题枚举不太够，剪枝没剪够，这次trac真的没什么想写的就一直没写……

=== wxx_louisa ===

[stay real]这个题想来也是搞笑，我觉得nlogn太不稳了，上去敲了一个线性做法，后来发现它假掉了。在机位上fix，一边把队列改成堆，那既然堆是log，为什么不直接sort呢？然后终于把它签掉了。。

[speed dog]做法不是乱搞，但它多了个log。我觉得题解的做法和sub的Minkowski都十分费解。。性质还是很好发现的，听到zyh和彭博小朋友他们的做法是什么，线段树二分，线段树是什么？

没过的题

【salty fish】网络流思想+启发式合并+长链剖分

【nonsense time】没想到倒流+没看到随机 = 我们没有这个题，以后我不能关起门放zlj这小哥去自己读题啊。

【milk candy】问题转化为从每个NPC手中选恰好Ki条边，使得图连通且代价最小。claris的题解说，生成树是图拟阵的基，所以这是图拟阵的对偶拟阵;而从每个边集中选择不超过若干条边的条件，则是划分拟阵M2。claris的题解又说，可以用拟阵交算法解决。

【Faraway】这个题大家都过了。但我们完全想不到要把绝对值拆开来搞，分成n方个平面区域，然后枚举Xe Ye模60的余数，60*60. 顺便Mark一个(x,y)->(x+y,x-y) (x,y)->(x+y)/2,(x-y)/2 

【ridiculous netizens】

== 补题 ==

[yangshi][wiki:2019-Acyclic_SD/paste1 CODE] 

总结

Todobe

读题杀我们。 B题没发现数据随机。

今天签完三道题之后之后我们又陷入了三人没题写，大家都会我不会的状态。

感觉沉寂了好一会儿，不过好在没有一直看那两个题，xx过了D，不过貌似是乱搞过的。

然后我和jj开了K，商量了一下，感觉这题有点shishi哒，还是我去写了。

但是感觉人不太清醒，思路不是很清晰，写完交上去T了，改成二分WA掉，最后jj当小黄鸭，我找到了一些错误，有两个模数，在算的时候模乱了，改了之后就过掉了。

这个图的罚时是虚假的，最后那个K交上去submit failed，于是就直接去hdu交了几发，所以有些罚时是没有算进去的。

然后就是我们还有一些琐碎的知识点需要掌握。

ZhljJoan

K题枚举不太够，剪枝没剪够，这次trac真的没什么想写的就一直没写……

wxx_louisa

[stay real]这个题想来也是搞笑，我觉得nlogn太不稳了，上去敲了一个线性做法，后来发现它假掉了。在机位上fix，一边把队列改成堆，那既然堆是log，为什么不直接sort呢？然后终于把它签掉了。。

[speed dog]做法不是乱搞，但它多了个log。我觉得题解的做法和sub的Minkowski都十分费解。。性质还是很好发现的，听到zyh和彭博小朋友他们的做法是什么，线段树二分，线段树是什么？

没过的题

【salty fish】网络流思想+启发式合并+长链剖分

【nonsense time】没想到倒流+没看到随机 = 我们没有这个题，以后我不能关起门放zlj这小哥去自己读题啊。

【milk candy】问题转化为从每个NPC手中选恰好Ki条边，使得图连通且代价最小。claris的题解说，生成树是图拟阵的基，所以这是图拟阵的对偶拟阵;而从每个边集中选择不超过若干条边的条件，则是划分拟阵M2。claris的题解又说，可以用拟阵交算法解决。

【Faraway】这个题大家都过了。但我们完全想不到要把绝对值拆开来搞，分成n方个平面区域，然后枚举Xe Ye模60的余数，60*60. 顺便Mark一个(x,y)->(x+y,x-y) (x,y)->(x+y)/2,(x-y)/2

【ridiculous netizens】

补题

[yangshi]CODE