Posts Tagged “ZOJ”


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 »


Andrew Stankevich’s Contest #10
ZOJ2704 Brackets 12.52% (513/4095)
ZOJ2705 Dividing a Chocolate 20.60% (102/495)
ZOJ2706 Thermal Death of the Universe 16.01% (205/1280)
ZOJ2707 Equations System 12.18% (24/197)
ZOJ2708 Fool’s Game 38.46% (25/65)
ZOJ2709 Lottery 32.21% (48/149)
ZOJ2710 Two Pipelines 21.00% (71/338)
ZOJ2711 Regular Words 28.44% (357/1255)

所有题目都附上了我AC的代码,不过AC不等于没问题,如果代码显示或下载有问题,或者我的程序有错,请在comment中说明,我会尽快fix。这套题中的ZOJ 2705, 2707, 2708强烈推荐!

ZOJ2704 Brackets

downloadsource code (ZOJ2704.c) [bracket, greedy]

给定一个只含()[]的字符串,问其中最长的合法字串是什么。

要判断一个串是否合法,只要维护一个栈进行O(n)的扫描就可以了。但是枚举字串+扫描就O(n^3),肯定不靠谱了。事实上注意到,如果从左往右扫描到第i个,出现不合法的情况,那么前面无论保留什么,都是非法的,所以把栈清空,继续从位置i+1开始新的扫描,复杂度O(n)。代码是入门的时候c语言写的……

ZOJ2705 Dividing a Chocolate

downloadsource code (ZOJ2705.cpp) [Fibonacci, greedy, 逆推]

给定一个m*n(m和n均可以很大)的矩形,初始可以沿任意的整数位置分成两个矩形。然后始终让大矩形减小矩形,直到两个矩形相等,目标是最后的矩形面积最小。题目最后的说明要求:中间不能出现一个矩形大面积大于另一个的两倍的情况。可以说这道题的sample说明才是本体啊。

从描述中可以知道,完成第一刀之后后面的发展是确定的,但由于规模很大,我们不可能去枚举第一刀的情况。可以反过来思考,事实上,知道了最后的结果,比如最后是两个a*b的矩形,那么我们也可以反过来推出之前较大的那个矩形依次是2a*b, 3a*b, 5a*b, 8a*b …,这不正是著名的Fibonacci数列么。目标是a*b尽量小,也就是要找最大的Fibonacci数f,使得m%f==0||n%f==0,10^9内的Fibonacci数不过几十个,枚举就可以了,答案就是m*n-m*n/f。注意要用long long。

ZOJ2706 Thermal Death of the Universe

downloadsource code (ZOJ2706.cpp) [SegmentTree, floor/ceil, off-by-1]

Comments 3 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 »