第七届全国青少年信息学奥林匹克竞赛分区联赛复赛普及组试题分析

[问题1] [源程序1] [源程序2] [源程序3] [源程序4]

1．这题可以递归枚举，看看程序吧。

2．记忆化搜索形式的动态规划

3．动态规划

4．效果更好的动态规划

[问题2] [源程序]

对于的一个素因子p，显然p的所有幂要么都在a中，要么都在b中。假设有K个互不相同的素因子，那么由乘法原理知答案为。

[问题3] [源程序]

这是一道很经典的题目( UsacoGate 1.3上面是 American Heritage)，方法是构造法：

设三种遍历的序列是：preorder[1..n] , inorder[1..n] , postorder[1..n]

中序遍历的一大特点是：第一个元素 post[n] 就是树的根

所以在 inorder[n]中找出postorder[n]的位置j就能得到做子树inorder[1..j-1]和右子树inorder[j+1..n]，这个时候，输出做postorder[n]，然后再递归输出inorder[1..j-1]和postorder[1..j-1]决定的先序，inorder[j+1..n]和postorder[j..n-1]的先序即可。

Sample 中给出的树是这样的：

/ \

B C

[问题4] [源程序]

这题的 n 比较大，搜索不好写，但是由于给出了 V 的规模，所以可以动态规划。这题的规划方程是很经典的（母函数相乘）：设 h[i,k]为前i个物品能否装满容量k的空间，那么h[ i , k ] = h [ i-1 , k-volume[I] ] or h[ i-1 , k ]; (*)

这种方法的时间复杂度为 O(NV)，空间复杂度为 O(NV)，空间复杂度较大，TP下写起来比较麻烦（除非用位压缩的方法）。观察(*)式，我们发现 h[ i , 0..V ] 只依赖于 h[ i-1,0..V]，所以我们可以只保存 h1, h2 ，每次从 h1 推出 h2 ，然后再令 h1:=h2，也就是利用两个数组进行滚筒操作。再仔细的观察 (*) 式，我们发现：h[i,k]的值只依赖于上h[i-1]的[k]以前的东西，换句话说，我们 for 循环的时候倒过来做就可以了，空间复杂度降为O(V)，请参考程序。