刷题总结

POJ 3253 Huffman树
错误:结果超出了int的范围,应该用long long;而且printf("%lld",ans),注意是lld
POJ 2686 Traveling by Stagecoach(DAG,状压dp)
题目大意:m个结点的无向图,每个结点表示一个城市,n张票,经过一条边消耗一张票,每张票有一个数值,经过一条边的时间为边的长度/票的数值。给定起点a,问终点b是否可达,若可达,求最短时间。
用搜索来做,在结点v,有k张票,每条边用k张票去试。这样可以重新建一张有向图,图中结点表示状态,即所在城市+手中余票,边表示原来边的长度/所用票的数值。问题转化为了从起点到终点的最短路问题。这个有向图呢,是一个DAG,因此可考虑用dp来求最短路,把票的状态压缩成一个整数T,相当于填一张T*m的表。
POJ 3734,3233 (dp,矩阵快幂)
POJ 2932 平面扫描(line sweep)
POJ 2187 Graham凸包,旋转卡壳求凸多边形直径(最远点对)
POJ 1741 树的点分治
POJ 3264 RMQ问题,sparse table or segment tree

POJ 2217 两个字符串的最长公共部分:拼接之后求出后缀数组SA和高度数组LCP,高度数组中的最大值即为所求结果
POJ 3581 后缀数组(仍需再加考虑)
POJ 3690 二维字符哈希
POJ 1961,2406,3461 KMP
LA 3942 枚举+Trie
HDU 2222 AC Automaton
ZOJ 1015 Maximum Cardinality Search求完美消除序列,弦图的判定(实现上的问题:图的邻接表和邻接矩阵都需要建立?)
BZOJ 1006 弦图的色数
LeetCode 最长回文串 Manacher‘s Algorithm https://www.felix021.com/blog/read.php?2040
POJ 3061,3320 尺取法

ZOJ 1610 Count the Colors

线段树,区间更新

UVA 699 The Falling Leaves

二叉树构建、遍历。一个想错的地方是,下落后最靠左的结点是根的左孩子的左孩子的左孩子…(直到叶结点)。一个反例是,根的右孩子的左孩子向左延伸很长,成为下落后最靠左的结点。