Codeforces 1072D
题意：题意给出一个 $ n × n $ 的矩阵，允许修改 $ k $ 次，求一条从$(1,1)$到$(n,n)$的路径。要求字典序最小

先处理每个坐标到起点是否能全改a(DP预处理到当前位置不改能经过多少个a)，能改就当前坐标改a
然后就要在这个网格图上每一步都尽可能最小地走到终点。每一步枚举向下走了多少步，然后每次找到最优解标记一下所有最优解的位置，以便下一步找的时候能连起来找到最小的。有点分层图的思想。

Codeforces 1068E
题意：

$1 - multihedgehog$ 满足：
是一棵树存在一个中心节点$u$与其它所有点相连包括中心节点在内，至少$4$个节点
$2 - multihedgehog$ 刺猬图满足：
是一棵树存在一个中心节点$u$与其它所有$1 - multihedgehog$的中心节点相连
这个中心节点至少连接$3$个以上的$1 - multihedgehog$
$k- multihedgehog$依次类推，给你一棵树，问你它是不是$k- multihedgehog$

看见样例图第一感觉合法图直径都是等长并且经过最开始的那个根。。并且是直径的中点(直径奇数长图不合法，也就是树的中心)，所以求一下树的直径然后找到中点即可。从起点搜完直径终点后再从起点搜如果搜到终点则返回真，标记这些点，这些点在直径上，然后再枚举找到距离是直径一般而且在直径上的点，这个点就是树的中心。

注意特判问题
1一个点的图不合法
2直径奇数长不合法
3直径不等于 $ 2k $ 不合法

Loj 10172
题意：给出一个矩阵，有一行涂上了已经颜色，有1 2 3三种颜色，求涂完能有多少种方案使得没有两个相邻的格子颜色是相同的。
对于$k$行填色的限制，我们不妨把$k$行上下分开做，最后方案数乘一下即可。
这个题目是很经典的网格图状压DP，不多说了。关键说说多进制状压的做法。
这里先考虑三进制状压：
我们相当于把一个整数当做三进制数来看，也就是说$(25)_{10}={221}_3$，我们就维护这个$221$。
我们开一个数组sjc[状态][位]=位上的值 (0, 1, 2)，用来找一个状态每一个位上是什么
这个数组可以用十进制转三进制的方法求得，具体看代码。
然后注意本题要特判$k=1，k=n$，并且只有一行的情况。

BZOJ 2423
题意：给定两个长度为$n, m$字符串, 求最长公共子序列长度和方案数$\mod 10^{8}$ $n,m\leq 5000$

第一问太简单不再说，主要看第二问
对于第二问，我们当前第一问的 DP 状态是 $ dp(i, j) $ 表示第一个串匹配到 $ i $，第二个串匹配到 $ j $ 的最长公共子序列。
然后我们再加一个数组 $ g(i, j) $ 表示第一个串匹配到 $ i $，第二个串匹配到 $ j $ 的最长公共子序列方案数。
对于这个数组的转移：
当 $ a_i = b_j $ 时，方案数加上$ g(i-1,j-1) $ 如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $，那么加上这些方案数
否则如果当前的 DP 值等于 $ dp(i-1, j) $ 或 $ dp(i, j-1) $，那么加上这些方案数。但是如果当前还等于 $ dp(i-1, j-1) $，说明 $ a_i , b_j $ 没做贡献，说明两个 LCS 均是从$i-1,j-1$的位置转移而来，减掉$ g(i-1,j-1) $即可。

例题及讲解

LIS

最长上升子序列 (Longest Increasing Subsequence，LIS)，一个数列中最长的单调递增的子序列。

例如 1 2 5 8 8 2 9 的 LIS 为 1 2 5 8 9，长度为 5.

模板题：Hdu 1257

某国发展出一种导弹拦截系统，它的第一发炮弹能够到达任意的高度，以后每一发炮弹都不能超过前一发的高度，给你一个导弹依此飞来的高度序列，请帮助计算一下最少需要多少套拦截系统.

BZOJ 1857
题意：见上。
观察(生活经验)发现，在 $ AB $ 上肯定存在一个点，他左移右移都会增大答案，所以是个单峰函数，同理 $ CD $ 。所以我们写一个三分套三分，即三分完以后再用这个三分结果进行下一个三分操作。

BZOJ 1858
题意：一个$01$序列，序列里面包含了$n$个数，这些数要么是$0$，要么是$1$，现在对于这个序列有五种变换操作和询问操作：

• $0 a b$ 把$[a, b]$区间内的所有数全变成$0$
• $1 a b$ 把$[a, b]$区间内的所有数全变成$1$
• $2 a b$ 把$[a, b]$区间内的所有数全部取反，也就是说把所有的$0$变成$1$，把所有的$1$变成$0$
• $3 a b$ 询问$[a, b]$区间内总共有多少个$1$
• $4 a b$ 询问$[a, b]$区间内最多有多少个连续的$1$

类似CF 817F，都是要维护$01$序列的区间修改和翻转。
这里更为复杂。
维护

$sum$：区间和
$lsum[0/1]$：左起区间最长$0$串，最长$1$串
$rsum[0/1]$：右起区间最长$0$串，最长$1$串
$maxsum[0/1]$：区间最长$0$串，最长$1$串
$upd$：区间修改$lazy$标记
$rev$：区间翻转$lazy$标记

翻转区间时注意$lsum[0]$和$lsum[1]$互换，其他同理。显然正确。

对于询问$4$的处理，我们分成三种情况讨论

1、在左子树
2、在右子树
3、在中间

注意第三种情况要满足限制$[x,y]$，所以在求值时加上限制。

BZOJ 3907
题意：见上。
注意到$n=m$时是卡特兰数。
也可以考虑正方形的时候，可以发现三角形的情况就是正方形的方案数除以正方形边包含的点数。(从简单情况入手)
也可以进行 DP，设$dp(i,j)$为$(0,0)$到$(i,j)$的方案数，转移时判一下，懒得写高精用 python TLE到60分……

我们发现不穿过$y=x$就是不经过$y=x-1$上的点……
所以我们从$(-1,0)$开始走，总方案数是$C^{n+1}_{n+m+1}$。
然后从出发点向上走的路径条数是$C^{m-1}_{n+m+1}$，向右走的方案与向上走的路径条数关于直线对称，所以最后答案是$C^{n+1}_{n+m+1}-2C^{m-1}_{n+m+1}$

Codeforces 821D
题意：题意:$n \times m$的地图,有$k$个位置是点亮的,有$4$个移动方向,每次可以移动到相邻的点亮位置,每次站在初始被点亮某个位置,暂时使某行或该某列全部点亮,花费为$1$,下一次使用时,上一次暂时点亮被熄灭.
问从$(1,1)$到$(n,m)$的最小花费

这题发现可以直接跑最短路。。每次循环找下一个灯如果相邻费用为0，如果能点亮一列过去费用为1，否则为INF，复杂度有点神奇

可以将行列缩成一个点，因为题目中点亮一次是一行或一列。然后每个灯可以连到周围能到的行列和灯，相应的边权看着办，然后边权只有01，跑0-1BFS。

2018.10.31 upd: 0-1 BFS 不要开vis数组！用dis松弛即可。

Codeforces 892D
题意：给出一个$n$个点$m$条边的无向联通图，有$q$个询问每个询问询问一个边集$E_i$，回答这些边能否在同一个最小生成树中

本题又加强我对最小生成树定理的理解……

首先同一个图最小生成树所有相同边权数量都是一样的，并且在 Kruskal 加边时不同边互相之间独立。也就是说我们可以将每个边权分开来加，并且每种边权都可以被一条不产生环的。关于更多最小生成树的定理，请看Bzoj 1016
其实这题和Bzoj 1016有类似的地方。
我们将询问离线。按照边权大小从小到大加边。枚举当前边权大小为$w$, 如果在某个询问中有$w$大的边，那么就将这些$w$大的边权加到并查集里看会不会产生环，如果产生环则无解，当然这些边要撤销，用能撤销的并查集。然后每次循环完以后，将当前边权的所有边加入并查集不撤销，继续做。