Posts Tagged “FlowNetwork”


Andrew Stankevich’s Contest #1
ZOJ2313 Chinese Girls’ Amusement 34.16% (233/682)
ZOJ2314 Reactor Cooling 26.61% (297/1116)
ZOJ2315 New Year Bonus Grant 35.25% (239/678)
ZOJ2316 Matrix Multiplication 44.19% (293/663)
ZOJ2317 Nice Patterns Strike Back 24.05% (115/478)
ZOJ2318 Get Out! 19.91% (94/472)
ZOJ2319 Beautiful People 26.34% (254/964)
ZOJ2320 Cracking’ RSA 31.41% (82/261)

大妈题第一套的解体报告。个人推荐ZOJ 2318ZOJ 2320。AC代码含,可直接看或下载

ZOJ2313 Chinese Girls’ Amusement

downloadsource code (ZOJ2313.cpp) [number theory]

求最大的k<=n/2使得gcd(n,k)=1。

如果n是2m+1形式的,那么k=m就是答案;
如果n是4m形式的,那么k=2m-1就是答案;
如果n是4m+2形式的,那么k=2m-1就是答案。
证明略,需要简单的高精度。

ZOJ2314 Reactor Cooling

downloadsource code (ZOJ2314.java) [FlowNetwork, 上下界最大流]

求一个无源汇的上下界网络流的可行流。

裸的上下界网络流问题,规模也很小,最暴力的网络流算法也没问题。至于上下界网络流可行流转化为普通网络流最大流的构图和原理,看论文吧(明白了很简单,虽然要独立想到绝对不容易)。

ZOJ2315 New Year Bonus Grant

downloadsource code (ZOJ2315.java) [graph, greedy]

给定一棵树,要求找出一个最大的边集合,要求一个顶点上至多只有一个边属于这个集合。

对于一个图,这是一个一般图最大匹配问题;如果这个图没有奇环,那还是一个二分图匹配问题;而

Comments 10 Comments »

ZOJ八周年庆,8道题,比赛时间188min,很有爱。其实是因为勉勉强强才凑到了8道题,如果正正经经比5个小时的话,大家都圆满了。


ID Title Ratio (AC/All)
A(ZOJ3305) Get Sauce 16.56% (142/857)
B(ZOJ3306) Kill the Monsters 17.36% (25/144)
C(ZOJ3307) Magic Machine 18.03% (11/61)
D(ZOJ3308) Move the Knights 37.23% (35/94)
E(ZOJ3309) Search New Posts 20.20% (80/396)
F(ZOJ3310) Unrequited Love 23.47% (307/1308)
G(ZOJ3311) ZOJ Special AC String 24.59% (338/1374)
H(ZOJ3312) 8*8 7.14% (2/28)


除了G和H外都是summer2009暑期集训里的题。不说废话了,正文开始:

ZOJ3305: Get Sauce

一个n<=16个元素的集合,给定m<=种备选子集,问最多可划分出多少个不相交的备选子集。

source code [bitwise, search]

这题有复杂度O(3^n),而且常数很小的算法。这基于下面这个简单又漂亮的位运算枚举子集的循环

for (int sub = mask; sub != 0; sub = (sub - 1) & mask)

sub将依次表示mask所有可能的子集,总的枚举复杂度则是n^3。

当然,搜索加有效地剪枝总是能过的。不过我表示剪枝苦手,当时也不知道这样一个O(3^n)枚举子集的算法,所以我是训练前18名中唯一一个没过这道题的,惭愧啊~

ZOJ3306: Kill the Monsters

在一个20×20的grid中,选择共n行与列,使得最多的’#'同时被所选行和列覆盖。

source code [bitwise]

Comments 15 Comments »