Posts Tagged “MST”


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 »