### 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)

### ZOJ2361/SGU209 Areas

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

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)
ZOJ2343 Robbers 37.35% (133/356)
ZOJ2344 Toral Tickets 43.41% (56/129)

### ZOJ2337 Non Absorbing DFA

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

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

### ZOJ2338 The Towers of Hanoi Revisited

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

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)

### ZOJ2704 Brackets

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

### ZOJ2705 Dividing a Chocolate

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

### ZOJ2706 Thermal Death of the Universe

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