noip2007提高组题解

时间:2023-03-08 16:09:01
noip2007提高组题解

题外话:这一年的noip应该是最受大众关心的,以至于在百度上输入noip第三个关键字就是noip2007。主要是由于这篇文章:http://www.zhihu.com/question/21107274/answer/18452037

 

第一题:统计数字

排序/平衡二叉树

受上面这篇文章的影响,我没有用快排,而是用了STL的multiset的count函数来统计出现次数。但事实证明STL的sort足以应付此题。另外的解法是用Treap实现的名次树,效率不及sort但高于multiset。

 

第二题:字符串的展开

模拟

虽然是模拟题但是可惜没有1次AC。原因出在我没有考虑到连续的两个展开,比如:

1 1 1

a-c-e

展开后应该是:abcde。而我的策略是处理掉一个「展开」操作后就马上输出前面的部分并删除,这就导致输出的结果是:abc-e。实际上应该保留后面的这个字符,以便作为另一个展开操作的开头。

 

第三题:矩阵取数游戏

动态规划、高精度

不得不承认我一开始确实想不到思路。看了网上的题解,发现主要是两种方法:(以下描述均针对矩阵的每一行,最终结果即各行结果之和)

  1. f(i, j) 表示在左边取i个数、在右边取j个数能得到的最大分数,则

    f(i, j) = max{ f(i, j-1)+w(m-j+1)*2^(i+j), f(i-1, j)+w(i)*2^(i+j) }

     

  2. f(i, j) 表示从第i个格子取到第j个格子能得到的最大分数,则

    f(i, j) = 2*max{ f(i+1, j)+w(i), f(i, j-1)+w(j) }

其中第二种方法很巧妙地避开了高精度乘法,用2在状态转移的时候进行累乘。最后,高精度最好用加法 char[] 而不要用 string,两者速度相差太明显了(几乎是超时与无压力AC的区别)。

 

第四题:树网的核

DFS

这道题目的特点是用大量的概念、定义来吓唬人。

几乎所有网络上的题解都说「只要对于一条直径进行计算即可」,但是我想不明白。那就姑且承认这个结论。

首先,在树上找到一条直径。方法如下:

  1. 从树上任意一点 u 出发,找到距其最远的点 v;
  2. 从 v 出发,找到距其最远的点 x。

路径 v -> x 即树网的直径。(证明见注释)

然后找核。枚举直径上的每个点,向单方向扩展出一段长度小于等于 s 的「核」,然后对于「核」上的每一个结点,求出它到每个点的最短距离。在所有这些最短距离中找出最大值,这个值就是现在这个「核」的偏心距。找到所有偏心距中最小的一个即可。

注释:关于用两次遍历求出直径的方法的正确性,证明如下:

首先,我们要证明从树上任意一点 u 出发找到的最远结点 v 必然是直径的一个端点。如果能够得到这个结论,整个方法的正确性就显然了。

先假设我们找到的 v 结点不是直径的端点。

我们可以证明 u->v 必然与直径 a->b 有交叉点。

如果没有交叉点,任选两条路径的两个端点相连就能得到一条更长的路径。如下图。

noip2007提高组题解

所以,既然有交叉点,设交叉点为 x,由 u->v 大于 u->a,可以推出 x->v 大于 x->a,那么路径 v->x->b 比 a->b 更长,a->b 不是直径,矛盾。

noip2007提高组题解

所以 v 只能是直径的端点。