Posts Tagged “andrewzta”


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 »