Beyond the Void

NOI2000的题目是[瓷片项链][单词查找树][青蛙过河][程序分析器][古城之谜][算符破译]。[瓷片项链][单词查找树][青蛙过河][程序分析器]都是简单题，[古城之谜]难度一般，[算符破译]是较难。

[瓷片项链]是简单的二次函数求最值的问题，数学方法可以直接解决。[单词查找树]是一种基本的字符串处理的数据结构。[青蛙过河]是一个递归的数学问题，可以求出直接的公式。[程序分析器]是个模拟题，需要细心。[古城之谜]是个动态规划问题，但是需要对题意尤其是对范式的深入分析。[算符破译]是个较难的搜索题，需要大量剪枝和优化。
Read the rest of this entry »

我的计划就从NOI1997开始。NOI1997一共有6道题，分别是[卫星覆盖][积木游戏][竞赛排名][最佳游览][最优乘车][文件匹配]。这一年的6个题难易分布均衡，做完后收获不小。

其中[竞赛排名]和[最佳游览]是两个最简单的题，但是往往细节是容易忽视的。[积木游戏]和[最优乘车]难度属于中等，分别是动态规划和构造最短路径解题。[卫星覆盖]和[文件匹配]属于较难题，用到了[卫星覆盖]离散化或者立体切割的方法，而[文件匹配]是搜索中的难题，需要很多的优化。

做这些题我花了4天的时间，进度还算正常，希望能继续保持下去。今后做题的宗旨是“不求多，不求快，但求精”。

Read the rest of this entry »

首先是根据输入的前序遍历建树，然后树形动态规划，递归地建立二叉树。假设绿色为0，红色为1，蓝色为2。要求两遍动态规划。

以最大值为例，动态规划状态设定

• F[i,c] 以节点i为根的子树中，根的颜色为c时，这棵子树上颜色为0的节点的个数。

状态转移方程

如果i为叶节点

• F[i,c]=1 (c为0)
• F[i,c]=0 (c不为0)

如果i只有一个子节点

• F[i,0]=Max { F[i.left,1] , F[i.left,2] } + 1
• F[i,1]=Max { F[i.left,0] , F[i.left,2] }
• F[i,2]=Max { F[i.left,0] , F[i.left,1] }

如果i有两个子节点

• F[i,0]=Max { F[i,left,1]+F[i.right,2] , F[i,left,2]+F[i.right,1] } + 1
• F[i,1]=Max { F[i,left,0]+F[i.right,2] , F[i,left,2]+F[i.right,0] }
• F[i,2]=Max { F[i,left,0]+F[i.right,1] , F[i,left,1]+F[i.right,0] }

目标状态

• Max{ F[root,0] , F[root,1] , F[root,2] } (root为根)

以上为求最大值，求最小值方法一样，把Max全部改成Min即可。
Read the rest of this entry »

Read the rest of this entry »

分析：输入二叉树的前序遍历、中序便利，求后序遍历
Read the rest of this entry »