cnPhil » HNOI

HNOI 2010 解题报告

July 5th, 2010 6 comments

由于题目的版权问题, 这里并不会出现题目描述, 请通过其他渠道获取题目描述.

合唱队 Chorus

很容易的区间DP, 设 $F_{i, j}, G_{i, j}$ 分别表示当前状态为区间 $[i, j]$ , 最后一个放的元素在区间的左侧和右侧的方案数. 时间复杂度 $O(n^2)$ .

平面图判定 Planar

判定存在 Hamilton 回路的平面图, 实际上就是判定能否把区间(边)分成两个集合, 使得每个集合内的元素互不相交(但可以严格包含).

这道题其实是有 $O(nlogn)$ 的解法的, 但是这道题的点数过少, 也有很方便的解法. 根据欧拉定理, 平面图的边数 $|e|$ 和点数 $|v|$ 满足 $|e| \leq 3|v| - 6$ . 那我们可以把边数的规模降低, 然后可以用 $O(n^2)$ 的染色解决此题.

物品调度 Fsk

假设我们已经知道了终止状态, 如何求得最小步数呢. 我们可以用 $O(n)$ 的时间求出这个置换的每个循环. 对于每个长度大于1的循环, 若其中含有0元素, 那么最少需 $length - 1$ 步, 否则需要 $length + 1$ 步.

现在的问题是如何求出终止状态, 观察题意发现, 每个元素的终止状态是放在 $C_i~mod~gcd(n, d)$ 之后第一个非空的模 $gcd(n, d)$ 剩余系中, 并且放在这个模 $gcd(n, d)$ 剩余系中当前位置的下一个可行位置, 因此我们可以用链表/平衡树维护每个模 $gcd(n, d)$ 剩余系的情况以及每个模 $gcd(n, d)$ 剩余系内部的情况. 可以做到 $O(n)$ 的复杂度.