Posts Tagged “bigraph”


Andrew Stankevich’s Contest #3
ZOJ2361 SGU209 Areas 18.12% (62/342)
ZOJ2362 SGU210 Beloved Sons 45.40% (173/381)
ZOJ2363 SGU211 Strange Counter 28.12% (63/224)
ZOJ2364 SGU212 Data Transmission 11.95% (104/870)
ZOJ2365 SGU213 Strong Defence 36.40% (83/228)
ZOJ2366 SGU214 Weird Dissimilarity 13.31% (84/631)
ZOJ2367 SGU215 PL/Cool 22.91% (33/144)
ZOJ2368 SGU216 Royal Federation 24.80% (64/258)
ZOJ2369 SGU217 Two Cylinders 15.71% (94/598)

还是先推荐两道构造题2363 Strange Counter2368 Royal Federation2361 Areas是一道coding量很大的计算几何题,而2367 PL/Cool是一道考验基本功的蘑菇题。2363 Data Transmission是一个值得再研究的分层图的阻塞流问题。

ZOJ2361/SGU209 Areas

downloadsource code (ZOJ2361.cpp) [geometry, 计算几何, dfs]

题目描述很简单,问给定的n条线把平面分出了几个有限的区域。

规模为80,不得不ym那些用优化的半平面交轻松AC这道题的牛人们,但我觉得这不能算a right approach。

我的算法是O(n^2lg(n))的。

Comments 10 Comments »


Andrew Stankevich’s Contest #2
ZOJ2337 Non Absorbing DFA 18.36% (92/501)
ZOJ2338 The Towers of Hanoi Revisited 35.60% (115/323)
ZOJ2339 Hyperhuffman 22.30% (252/1130)
ZOJ2340 Little Jumper 22.22% (72/324)
ZOJ2341 Quantization Problem 42.85% (84/196)
ZOJ2342 Roads 36.70% (116/316)
ZOJ2343 Robbers 37.35% (133/356)
ZOJ2344 Toral Tickets 43.41% (56/129)

最小生成树和二分图最优匹配你可能都熟悉得不能再熟悉了,可是把它们巧妙的隐藏到题目中,再通过不等式组(整数规划问题)联系起来呢?ZOJ 2342 Roads强烈强烈强烈推荐。然后可以通过ZOJ2344复习一下Burnside引理|Polya计数定理;做做ZOJ2338的扩展Hanoi问题;有爱的还可以挑战一下ZOJ2340,一道不简单的数学(物理?)参数搜索题。

ZOJ2337 Non Absorbing DFA

downloadsource code (ZOJ2337.java) [BigIntger, DP, graph]

已知一个DFA,问有多少长度为N的字符串会被accept。与普通DFA不同的是这里多了一个G,如果某边有G(u,c)=1,则沿这条边,字符串的第一个字符不会被移除。

Deterministic finite automation (DFA),好像不需要了解也可以。首先对G做预处理,在某点沿某条边出发,如果有G(u,c)=1的环,说明永远不会accept,否则我们就将这条边指向第一个G(u,c)=0处,经过这样处理以后,问题就是在一个普通的DFA了。然后只要在这个普通的DFA,也就是有向图上,做动态规划就好了,dp的两维状态分别是长度和所在节点。

ZOJ2338 The Towers of Hanoi Revisited

downloadsource code (ZOJ2338.java) [DP, recursive]

解决n个盘m根棍的河内塔(谁翻译的汉诺塔,zhua啊)

相信传统Hanoi问题的解大家都烂熟于胸了,不过这道题能够检验你是否真正理解了Hanoi和背后的递归思想。如果需要,可以看看《具体数学》的第一章补补课哦。

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