### Posts Tagged “solution”

Andrew Stankevich’s Contest #9
ZOJ2696 Chip Designing 19.15% (41/214)
ZOJ2697 Electricity 16.55% (76/459)
ZOJ2698 Numbers to Numbers 10.28% (29/282)
ZOJ2699 Police Cities 19.35% (66/341)
ZOJ2701 Restore the Tree 13.99% (76/543)
ZOJ2702 Unrhymable Rhymes 28.86% (153/530)
ZOJ2703 Selling Tickets 21.79% (51/234)

### ZOJ2696 Chip Designing

source code (ZOJ2696.cpp) [构造, 平面几何]

### ZOJ2697 Electricity

source code (ZOJ2697.cpp) [构造, 拓扑排序(Topological Sort), acyclic]

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 #4
ZOJ2559 The Smart Bomb 53.76% (321/597)
ZOJ2560 I Just Called … 21.05% (76/361)
ZOJ2561 Order-Preserving Codes 18.28% (126/689)
ZOJ2562 More Divisors 30.14% (322/1068)
ZOJ2563 Long Dominoes 37.94% (148/390)
ZOJ2564 The Magic Wheel 17.11% (83/485)
ZOJ2565 Cracking SSH 50.25% (98/195)
ZOJ2566 Periodic Tilings 33.81% (47/139)
ZOJ2568 Counting Triangulations 16.31% (101/619)
ZOJ2569 Unfair Contest 28.57% (64/224)

### ZOJ2559 The Smart Bomb

$\left\{\begin{array}{l}x+y=c\\y+z=a\\z+x=b\end{array}\right.$

Andrew Stankevich’s Contest #5
ZOJ2587 Unique Attack 21.20% (263/1240)
ZOJ2588 Burning Bridges 23.92% (410/1714)
ZOJ2589 Circles 18.57% (120/646)
ZOJ2590 Linear Programming Dual 30.65% (42/137)
ZOJ2591 DVD 13.78% (79/573)
ZOJ2592 Think Positive 40.56% (527/1299)
ZOJ2593 Ranking 21.93% (84/383)
ZOJ2594 Driving Straight 19.64% (168/855)

### ZOJ2587 Unique Attack

source code (ZOJ2587.cpp) [FlowNetwork]

### ZOJ2588 Burning Bridges

source code (ZOJ2588.cpp) [Graph]

M个桥连通者N个岛屿，现在一些桥将被烧毁，但岛屿连通性不变，问那些桥一定不会烧毁。

### ZOJ2589 Circles

source code (ZOJ2589.cpp) [geometry, math, Euler's formula]

### ZOJ2590 Linear Programming Dual

source code (ZOJ2590.cpp) [simulation]

### ZOJ2670 Nonoptimal Assignments

$\begin{pmatrix}0&1&1&\cdots&1\\0&2&2&\cdots&2\\0&0&2&\cdots&2\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&2\end{pmatrix}$

### ZOJ2671 Cryptography

source code (ZOJ2671.c) [math, SegmentTree]

### ZOJ2672 Fibonacci Subsequence

source code (ZOJ2672.c) [DP, hash]

### ZOJ2673 Hexagon and Rhombic Dominoes

source code (ZOJ2673.c) [DP, bitwise]