PDF《hiho 挑战赛 Solution》

hiho 挑战赛 Solution jcvb May 14,

2016 1 Boxes 这是一道非常容易的题目.

从上往下开箱子的时候,如果发现这堆的底下已经没有宝箱了,就可以不用再管这堆了. 容易看出最优策略是先把其中第 x 堆的宝箱都带走,中途遇到的没用的箱子放到另一个地 方.然后去开其他堆中的宝箱,并把没用的箱子丢到第 x 堆. 为了让步数最少,只要使开第 x 堆时遇到的无用箱子数目最少就可以了.

2 LIS 这是一道比较容易的 DP 题. 由于值域只有

0 和1,可以令状态为 f[i][l0][l1],表示当前在从左到右第 i 个位置,之前 以0结尾的答案最长长度是 l0,之前以

0 或1结尾的答案最长长度是 l1 的方案数.如果 第i+1位是 0,就转移到 f[i + 1][l0 + 1][max{l0 + 1, l1}];

如果第 i +

1 位是 1,就转移到 f[i + 1][l0][l1 + 1]. 最后只要对所有 f[n][l0][l1] * l1 求和即可. 这个 DP 是O(n3) 的.

3 Sequence 先来考虑一个排列可到达的条件是什么. 如果不是 n 排列,而是

01 序列的话,那么条件是显然的:只要对于任意 i,序列 b 的第 i 个1都位于序列 a 的第 i 个1的右边(不一定严格) ,那么 a 就可以到达 b. 对于一个 n 排列 a,以及一个数 k,把a中大于 k 的数标为 1,剩下的数标为 0,就能得 到一个

01 序列.如果对于任意的 k,排列 a 对应的

01 序列都能够到达排列 b 对应的序列,那 么排列 a 就可以到达排列 b.它的必要性是显然的.至于充分性,可以观察下面这个移动策略: i 从n到1的顺序,每次将数字 i 移到它的目标位置,令当前位置为 l,目标位置为 r,当前 (l, r] 区间的最大数字为 a[j],那么把 a[l] 和a[j] 交换一下即可.容易看出这样移动一定是可行 的. 那么只要做一个

01 串DP:从一个全

0 的串开始,每次转移是将串中的某个

0 改为 1,最 后到达一个全

1 的串,且保证经过的都是合法

01 串. 这个 DP 是O(n2n) 的.

1 4 Polynomial 由于多项式次数为 n ? 1,所以 n 个点值是可以唯一确定这个多项式的.设输入的多项式 是f(x),由点值确定的这个多项式是 g(x),我们的任务就是判断 f(x) ≡ g(x) 是否成立. 直接求出 g(x) 的各项系数是比较困难的,但对于某一个 x0 求出 g(x0) 的值是可以做到的, 只要用 Lagrange 插值公式即可, g(x0) = ∑ 0≤i