分类 数据结构与算法 下的文章

HDU 5692 Snacks(DFS 序+线段树)解题报告


解题思路

这个题还是挺巧妙的。首先我们要明确一下题目中的操作。

第一种操作是单点更新。第二种操作是查询从 0 号结点(树根)开始且必需经过 x 号结点的路径上,数值和最大是多少。

接下来我们先根据第二种操作来把题目要求进行一些转化。既然是要求路径上数值和最大,那么可以先找到可能的路径有哪些.很容易看出可能的路径肯定是 0 到 x 或 0 到 x 的子结点。我们可以在输入完成后将 0 到任意结点的路径数值和都预处理出来,并用 DFS 序处理结点在数组中的分布以使子树结点连续。这样第二种操作就转化成了一个区间查询最大值的操作,我们可以用线段树来实现。

第二种操作分析完后,我们再回头来看第一种操作,它要求实现单点更新。在上一段我们已经通过建模得到了一个保存路径数值和的数组,一旦树上某个结点的数值更新,就意味着它和它的所有子结点到 0 的路径数值和都要更新,而他们的改变量都是一样的,因此我们计算出这个结点的改变量,就可以应用线段树区间更新来对所有受影响的点都进行同步更新。这样就实现了第一种操作的需求。


FZU 1686 神龙的难题(DLX 重复覆盖)解题报告


解题思路

首先将所有有怪物的坐标编号,作为 DLX 矩阵的列,然后将所有攻击区域以选定的某个顶点坐标编号,作为 DLX 矩阵的行。这样本题就转化成了求最少的行数(即攻击次数)使得所有列(即怪物)都被覆盖,而且由于题目允许同一个位置被多次攻击到,这里我们使用 DLX 的重复覆盖算法来解决这个问题。