首页 > 其他 > 详细

ZOJ Monthly, March 2014

时间:2014-03-03 16:42:48      阅读:501      评论:0      收藏:0      [点我收藏+]

A:

模拟,队友写的

B:

转化到十进制后暴力sqrt(n)判素数,不要问我为什么,后面都不是素数。。队友写的

D:

二分图最大权独立集

对于x^y为奇数的点i和点j,xi^yi^xj^yj为偶数,而p也为偶数,所以gcd至少为2,所以奇数点之间互不冲突

对于x^y为偶数的点同理

因此将互相冲突的点之间连边,可以得到一个二分图,做最大权独立集 == 总权和-最小割 

E:

将每个球向他4个方向的最近点连边,那么答案就是联通块的个数,因为每个连通块总是有办法能够弹得只剩一个

对于一个连通块,必须保证在弹的过程中一直只有一个连通块,

要保证这个性质,只需要按照dfs序或bfs序,逆序删点即可。删的方向,设为dfs或bfs树中该点的父亲方向就可以了

恩,队友写的

F:

对于每一个点,把所有点按照该点以极角序排序,然后顺序枚举边,再去找凸包上直线左侧最远点,而这个满足凸性,因此可以从前一次找到的凸包上的点继续往前找,直到距离不增加为止。那么复杂度是O(n^2lgn)

H:

题意为求原图删掉最多K条边后的最大流的最小值

容易想到K条边是删在割上的

因此2^n次枚举所有的割,维护删掉割集中K条最大边后的最小割,就是答案

I:

无脑平衡树

只需要敲啊敲啊敲就能AC了

ZOJ Monthly, March 2014,布布扣,bubuko.com

ZOJ Monthly, March 2014

原文:http://blog.csdn.net/hei_nero/article/details/20307637

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!