某岛

… : "…アッカリ~ン . .. . " .. .
August 18, 2012

Andrew Stankevich’s Contest #2

Overview:

。第二套。。三道 DP 题。。。(A, B, E 。且都要求打印方案。。难度不是特别大。。
。(。。其中 B 题是经典的多柱河内塔问题,要考虑到以后出现各种派生的可能性。。
。。(。。好像大妈系列的所有 DP 题都要输出方案。。。。
。两道贪心。(。。C。 G 。然后 H 题 Polay 计数定理专门开一个页面整理。。
。。。当然最推荐的还是 D 和 F。。

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=1230#overview

Problem A. Non Absorbing DFA
给定一个变种的 DFA,转移函数允许在转移之后保留字符。
问可接受的字符串总数。
————————————————————————
求一般的自动机求可接受字符串的总数,用普通的动态规划就可以了。
这题只要先对 NA-DFA 进行一次预处理转换成普通 DFA 就行了。
(注意中间如果出现环则直接算做不可接受,转移函数全部指向一个空位置即可。
高精度,自动机 dp。

Problem B. The Towers of Hanoi Revisited
给定 N 个盘子和 M 个柱子的多柱河内塔,求最少移动步数,并打印方案。
——————————————————————
设 F[m][n] 表示 m 阶河内塔,n 块盘子时移动方案的步数。则
F[m][n] = max(2 * F[m][i] + F[m-1][n-i] | 1 <= i < n) 时间复杂度 O(n^2m)。 多柱河内塔问题,动态规划,递归。。。

回忆三阶情况下我们的做法,每次都是将最上 n-1 个盘子,
借助当前柱子,移动到中间柱子上,然后移动最下面的盘子到目标柱,
然后在把中间柱子上的盘子以当前柱子作为中间柱子移动到目标柱子上。。(。。。
而对于高阶情况这里的 n-1 并不一定能保证最优,只能枚举。。(?。有规律么 。。
(另外目测随着 M 的增加,函数值下降的会很快?。。
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Multistack_Towers_of_Hanoi

Problem C. Hyperhuffman
求 Huffman Coding 的 WPL (Weighted Path Length)。。。
————————
。。直接用优先队列 O(nlogn) 就行了,
哈夫曼树、贪心、优先队列

(只要求 WPL 不需要把树实际构建出来。。
(另外输入序列是有序的。?。

Problem D. Little Jumper
给定两面距离为 l 的有洞的墙,洞的范围分别为 [b1, t1] 和 [b2, t2]。
一只诹访子要从距离墙壁左侧 ds 的地方起跳,在中间区域停顿一次,再跳到距另一面墙右侧 df 远的地方。
问至少需要多大的初速度。(不允许一跳穿过两面墙。。
Tags:斜抛运动, math, physics, parameter search
————————
做法一:二分法 (180 ms +-。。且精度捉急。。
做法二:三分法(40 ms +-

Problem E. Quantization Problem
dp

Problem F. Roads
二分图最小边边集合覆盖

Problem G. Robbers
有 n 个强盗分 m 个金币。第 i 个强盗的功劳是 xi。。
问如何分金币最公平。
——————
贪心

Problem H. Toral Tickets
Polay 计数法
————————
【专题】Polay 计数定理