BZOJ 1010
见此讲解

Codeforces 980E
题意：有一颗无根树编号$1$到$n$，每个点权值为$2^i$, 要删除$k$个点，并且删后原树还是联通的。请问整棵树权值最大的删点方案？

因为每个点权值为$2^i​$，而$2^i = \sum_{j=1}^{i-1}2^j+1​$，所以最大的那个点权值比其他所有点的权值都大。那么我们必须用一切代价保留大编号的点。我们可以把删除转化为选择问题，看从大开始能选几个点进去。预处理将$n​$转为根，$n​$加入选择集合。这个选择集合的所有节点必须在树上是连通块。所以我们枚举$n-1​$到$1​$的点看它到联通块的最短距离来判断能不能加，能加就把路径上所有点加入集合。对于看它到联通块集合的最短距离，我们用树上倍增的方法找到距离该点最近的已经在联通块集合的点在哪里。

Codeforces 909E
题意：给你一堆任务，有些要用主处理器处理，有些要用副处理器处理，副处理器可以一次处理很多个任务，一个任务能被执行的条件为前继任务已经被执行过了或者前继任务和自己同时被放进副处理器处理，现在给你这些前继任务的关系和每个任务处理要用的处理器，求副处理器最少运行了几次，保证关系是一张有向无环图 (主处理器与副处理器之间没有任何关系，随意顺序处理)

DAG图就能想到DP和拓扑排序，这题明显可以拓扑排序。先把最外面能被拓扑的一堆0点处理(不一定就一层)，然后再处理里面的能被拓扑的一堆1点，并且使答案加一。以此类推

Codeforces 922E
题意：一条直线上有$n$棵树, 每棵树上有$c_i$只鸟, 在一棵树底下召唤一只鸟的魔法代价是$cost_i$ ，每召唤一只鸟，魔法上限会增加$B$ ，从一棵树走到另一棵树，会增加魔法$X $，一开始的魔法和魔法上限都是$W$， 问最多能够召唤的鸟的个数(题意来自Luogu)

只能向前走，所以一定是DP。但是费用都是$10^9$明显不能加到状态里。那么设$dp(i,j)$为到$i$棵树下已经召唤了$j$只鸟剩下的魔法，那么就是一个比较容易的DP
$$dp(i,j)=max(dp(i-1, j-k)-cost_i \cdot k|1 \leq k \leq min(j, c_i))$$
由于$c_i$的总数不大，直接循环即可。
注意无用的状态和初始化都$dp(i,j)=-1$, 只有$dp(0,0)=W$，要注意不要有负数出现，要及时剪枝。也不能从无用状态转移。
最后由于相邻状态转移会恢复$X$魔法，所以要根据当前容量大小来修改dp的值。

一定要注意初值、无用状态转移的处理。

Codeforces 1013E
题意：给你$n$个数，你一次操作可以把某一个数$-1$（可以减为负数），你的目标是使任意的$k$个数严格小于它旁边的两个数（第一个数只用严格小于第二个数，第$n$个数只用严格小于第$n-1$个数），问最少需要几次操作。$k$是不确定的，请输出$k \in[1,\left\lceil\dfrac{n}{2}\right\rceil]$时的答案。(题意来自Luogu)

求最优值，想到DP，并且要求$,\left\lceil\dfrac{n}{2}\right\rceil$个值，所以可以设$dp(i,j)$为前$i$个数有$j$个数满足题意的最优值。但是这样转移非常困难，因为不知道上一个接上的是不是满足题意的值。那么我们设：

dp(i,j,0) 为前$i$个数有$j$个数满足题意，并且$i, i-1$都不满足题意的最优值
dp(i,j,1) 为前$i$个数有$j$个数满足题意，并且$i$满足题意的最优值
dp(i,j,2) 为前$i$个数有$j$个数满足题意，并且$i-1$满足题意的最优值

是否很像树状DP的样子？
然后分别转移：
$$dp(i,j,0)=min(dp(i - 1, j ,0), dp(i - 1, j ,2))$$
这个意思是直接继承之前的，画个图就能搞明白
$$dp(i,j,2)=dp(i - 1, j ,1)+max(0, a_{i} - a_{i - 1} + 1)$$
因为之前$dp(i - 1, j ,1)​$的最后一个满足题意没有考虑现在的$i​$，于是要进行操作。

然后考虑$dp(i,j,1)$
$$s =dp(i - 1,j - 1,0) + max(0, a_{i - 1} - a_{i} + 1)$$
前面两个都不是满足题意的，所以直接操作
$$t=dp(i - 1,j - 1,2) + max(0, min(a_{i - 1}, a_{i - 2} - 1) - a_{i} + 1)$$
前面两个点中$i-2$满足题意，并且$i-1$必然在之前操作中已经小于$i-2$，所以操作要取$min$
$$dp(i,j,1)=min(s, t)$$
综合前面的答案取最小。

初始值：$dp(i,0,0)=0, dp(1,1,1)=1$，其他赋值$∞$
第一个不用解释，第二个因为只有一个数所以必然有一个满足题意的数。
写初值的时候要注意全面考虑，不要忘

然后就可以直接做了

方法二，设$dp(i,j,0/1)$为前$i$个数有$j$个数修房子，并且$i$修(0)/不修(1)房子的最优值
注意转移$dp(i,j,1)​$的时候不要从$i-1​$转移，而是从$i-2​$转移，这样转移非常方便
转移方程：
$dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + max(0, a[i] - a[i - 1] + 1))$
$dp[i][j][1] = min(dp[i - 2][j - 1][1] + max(0, a[i - 1] - min(a[i - 2], a[i]) + 1), dp[i - 2][j - 1][0] + max(0, a[i - 1] - a[i] + 1))$

poj 1386
题意：给出几个字符串问能否首位相接成一个环或者一条链。

就是判有向图是否存在欧拉路即可。

欧拉路存在条件(图连通)：
有向图：有一个点入度等于出度加一，有一个点出度等于入度加一，其余所有点入度等于出度
欧拉回路存在条件(图连通)：
有向图：所有点入度等于出度

用并查集维护一下就好。

模板及讲解

定义

欧拉路：能从无向图的一个点出发走一条路径，每条边恰好经过一次，这样的路叫欧拉路。
欧拉回路：能从无向图任意一个点出发走一条路径，每条边恰好经过一次，并且回到该点，这样的路叫欧拉路。
欧拉图：具有欧拉回路的图称为欧拉图，具有欧拉路而无欧拉回路的图称为半欧拉图

性质

至多有两个奇点(度数为奇数)的无向图一定存在欧拉路

当有两个奇点时欧拉路必然从一个奇点到另一个奇点
当有没有奇点时欧拉路必然是一个欧拉回路

欧拉图中所有点都是偶点并且所有点连通。

一笔画：
连通分量是一个孤立的点, 只需要0笔可以完成
连通分量是一个欧拉图或半欧拉图, 只需要1笔可以完成
否则需要奇点数目/2笔可以完成
简单证明为一个联通分量中两个奇点(非欧拉图/半欧拉图)就要有一条笔画划过，如果没有奇点(就是一个欧拉图)也要用一条笔画划过，结论得证
HDU 3018

题目

判断是否有欧拉回路/欧拉路

Hdu 1878
题意：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
解：欧拉图中所有点都是偶点并且所有点连通。用并查集判连通，记录度数即可。

Hdu 1045
题意：题目告诉你一张网格图，图上有的格子有障碍物挡着，问一个在图上最多放几个炮台能覆盖整张图，且不会火力部重叠。

考虑二分图，并且如果没有障碍物，那二分图一条边相当于一个格子，求最大匹配即可。
如果有障碍物，我们不妨拆行拆列，即如果一行中有障碍物，那么障碍物前后的行是互不影响的，所以我们可以拆出一个行，之后也是同理，列的情况也是同理。

(样例一为例)

.X..
....
XX..
....

拆行直接在后面加行即可，行列坐标就可以是((X, X)是X)

(1, 1), (X, X), (5, 3), (5, 4)
(2, 1), (2, 5), (2, 3), (2, 4)
(X, X), (X, X), (6, 3), (6, 4)
(4, 6), (4, 7), (4, 3), (4, 4)

然后用这个坐标来加边，对新图进行最大匹配即可。

poj 2226
题意：用宽度为1长度不限的木板将 * 盖住而不盖住 .。

我们考虑二分图中一条边为一个点。我们对横竖进行遍历，看只横和只竖所需要的木板并且标号，例如样例

4 4
*.*.
.***
***.
..*.

横着：（图中数字表示用的是第几块木板）

1.2.
.333
444.
..5.

竖着：

1.4.
.345
234.
..4.

我们发现每一个点都可以被两块方向不同的木板覆盖，所以就以这个为依据建边，边相当于一个点，那么只要求出最小顶点覆盖即可。

poj 2446
题意：给出一个网格图，有$k$个格子是空洞，然后用$1 \times 2$的矩形，对所有非空洞的格子进行覆盖，问是否可以全部覆盖。
考虑将图黑白染色，即相邻的格子颜色不同(黑白相间)。本题就是相当于将白格和黑格进行匹配，连边二分图，然后求出最大匹配即可。但是最大匹配后可能还会有$1 \times 1$的小方块不在匹配中，要验证答案。
对于一个点$(x,y)$，如果$x,y$是奇数，则他是一种颜色；反之是另一种颜色。我们用这种方法来区分颜色。注意障碍物不要连边。