SPOJ 最近做的题目

傻叉题就不说了。。
Trees Again 
令Dp[root][Dep]表示子树根为root,最大深度(从root往下)是Dep的个数。。
然后考虑计算。。可以发现子树的状态只跟最深的两个节点有关。。
那么枚举这两个节点和它们的深度。。
然后有一点就是假如两个节点深度一样。。就会有重复。。要考虑一下。。
Easy Longest Common Substring
二分+Hash。。
Two Paths
跟TREECST一样的做法。。首先两个条路径必然有一条边把它们分开。。那么我们需要计算的就是对于每一条边。。它的上发子树和下方子树的直径。。画个图仔细想想就可以写出来了。。注意常数小心TLE。。。
Counting Arborescence
注意这里的图是有向的。。所以没法用那个xx矩阵。。。
所以只好集合动态规划Dp[set][root]表示set的顶点集合。。以root为顶点。。有几个Arboresecence。。。
然后推一下方程就可以了。。
Highway
块状数组。。我记得好像是GDOI的题目?
Copying DNA
集合DP。。记录一下目标串哪些被覆盖了。。常数优化一下>_<。。
好吧。。写的有点简陋。。有时间充实一下。。。

8 thoughts on “SPOJ 最近做的题目

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>