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和背后的递归思想。如果需要,可以看看《具体数学》的第一章补补课哦。

记f[n][m]为n个disc,m个peg的Hanoi问题,则有dp公式f[n][m]=min{f[n-k][m-1]+2*f[k][m]}。即把上面的k个disc利用m个peg转移某个中间peg,再把下面的n-k个disc利用m-1个peg转移到目标peg,最后把上面的k个disc利用m个peg移到目标peg。dp过程记下使得f[n][m]最小的g[n][m]=k用于反向打印移动过程。

ZOJ2339 Hyperhuffman

downloadsource code (ZOJ2339.cpp) [Huffman_coding]

求Huffman Coding(霍夫曼编码)的WPL(Weighted Path Length)

wiki。当然先建树在树形DP也可以,实际上排序+2个队列求Huffman Coding就能把相应的WPL求出来,ms是数据结构的某次作业?

ZOJ2340 Little Jumper

downloadsource code (ZOJ2340.cpp) [math, physics, parameter search]

小青蛙要从一个地方跳到另一个地方,中间要通过墙上的洞穿过两层墙,并在两墙间的区域停留一次。问小青蛙所需的最小的最大速度。(希望没引入什么关键字= =b)

该死的精度……有两种思路,一种是二分速度,自己写了快200行吐血,不想说了……
然后介绍一下楼教主的方法,二分中间的停留点:在确定跳跃点和落地点的情况下,我们可以求出所需要的最小速度,其中45度起跳最小,不过可能会撞墙。而这个速度关于落地点到墙的距离是凸函数。对于第二此跳,则可以看成从右往左跳到中间点。对于两个速度取最大值后,得到的依然是凸函数。于是可以用三分法求得最小值。
我直接没用eps二分了100次

ZOJ2341 Quantization Problem

downloadsource code (ZOJ2341.java) [DP]

记f[i][j]为处理了前i个数字,最后在level j的最小费用
每次转移就是枚举下次使用 level j里的哪个值来代替x[i]
其实可以不需要枚举所有值,假设l[j][p]与x[i]最接近,我们只要枚举l[j][p- m]~l[j][p+m]就足够了,不过这题这样复杂度是一样的……

ZOJ2342 Roads

downloadsource code (ZOJ2342.java) [MST, bigraph, Hungary]

某个国家有石头路和烂泥路,石头路恰好是生成树,维护路自然是花钱的,现在希望通过修改路的维护费用使得石头路是最小生成树(可以不是唯一的MST),目标是总的修改量最小,要求输出方案。

首先,最优的方案里,我们是不会增加石头路的费用的,也不可能去降低烂泥路的费用,所以可以认为对石头路有d=c-l,对烂泥路有d=c+l,l>=0。生成树加上原图一条边,一定构成一个圈;而最小生成树加上原图一条边,不但构成圈,而且有新加上边的权值一定不比圈中其余边的权值小,否则我们就可以得到了一个更小的生成树。利用这个性质,对于每个圈,都可以构造一些列不等式,假设i是石头路,而j是烂泥路,就有di<=dj,即ci-li<=cj+lj,即li+lj>=cj-ci。而我们的目标是使得所有的l之和最小。这一组不等式如何求呢,其实这就是二分图最大权匹配(Maximum Weighted Matching)的对偶问题二分图最小权覆盖(Minimum Weighted Cover)!所以用匈牙利算法(Kuhn & Munkres (kuhnMunkres) Hungarian Algotithm)解决之。

ZOJ2343 Robbers

downloadsource code (ZOJ2343.c) [greedy]

一伙强盗按预先约定分赃,由于只能是整数,可能不能恰好分好,所以要求离预先约定越小越好。

首先每个人都拿到k=floor(m*x/y)的钱,然后按|(k+1)/m-x/y|-|k/m-x/y|排序,把未分掉的钱,假设有z,z一定小于n,m分给前面z个人。

ZOJ2344 Toral Tickets

downloadsource code (ZOJ2344.java) [BigIntger, burnside, polya, math, combinatorics]

一张票有N*M的黑白格子,可以卷成圆柱再卷成环,问这样操作后依然不同构的票有多少种。

这题需要利用伯恩赛德引理(Burnside’s lemma)波利亚计数定理(Pólya enumeration theorem),而且N==M的时候比较特殊。其他没什么了。

7 Responses to “Andrew Stankevich’s Contest #2解题报告”
  1. ZeroClock says:

    神神神牛,请问2344那题的程序为什么打不开,还有能不能说下详细点,题目看的不是很清楚..

  2. wizard1990 says:

    Ym学长World Final Rank1~
    PS:Roads那题是不是有个笔误?应该是li+lj>=ci-cj ci和cj好像写反了

  3. tracyzhu says:

    弱弱的问下2342Road 囧,因为这题刚学的KM,想知道怎么处理最小权的,直接取反求最大还是用INF减去F[i,j],这样的话求出来的A[i] 和B[i] 能保证都>0吗?

  4.  
Leave a Reply