poj 3565
题意：在坐标系中有$N$只蚂蚁，$N$棵苹果树，给你蚂蚁和苹果树的坐标。让每只蚂蚁去一棵苹果树，一棵苹果树对应一只蚂蚁。这样就有$N$条直线路线，问：怎样分配，才能使总路程和最小，且$N$条线不相交。

可以发现如果相交的两个线段一定可以修改为不相交(三角形)，且总路程和更小。题目保证有解，那么直接带权二分图完美匹配。这里可以费用流做，设源点$s$，汇点$t$，$s$到蚂蚁连边$(1,0)$($(cap, w)$表示容量和价值)，苹果树到$t$连边$(1, 0)$，每个蚂蚁到每个苹果树连边$(1, dist(a_i,b_j))$

最后在蚂蚁到苹果树边中容量为0的即为匹配边。

poj 3017
给定一个数列$a_n$，任意将连续的$a_i$分块，使所有块的和都不超过$M$，最小化各块的最大值的和。

设$dp(i)$为前$i$个的最优值。
$$
dp(i)=\min(dp(j)+\max(a[j,i-1]))
$$

这个是$O(n^2)$的。考虑优化。
这里$\max(a[j,i-1])$不能表示为多项式，所以不能斜率优化了。
那么我们考虑缩小候选集合$j$的大小。

引理：

若$j$可能成为$f(i)$的最优决策，则必有$a_j > \max[j+1,i]$

证明很容易，假设如果$a_k \leq \max[k+1,i]$，那么我们可以在前面找到一个位置$k$，使得$a_k > \max[k+1,i]$，然后因为$f(i)$单调递增，所以$k$比$j$优，证毕。

那么我们可以维护一个单调队列，满足$a_i - a_{q_{l}} \leq m$，且对于$i$单增则$a_i$单减。
那么对于每个$q_k$，他转移到$i$的代价为$dp(q_k)+a(q_{k+1})$，显然$[q_k,i]$的最大值为$a(q_{k+1})$。
那么

$$
dp(i)=\min_{k \in [j,i]} (dp(q_k)+a(q_{k+1}))
$$

发现$dp(q_k)+a(q_{k+1})$与$i$无关，用数据结构维护之。
这里可以用堆来维护，将单调队列和堆构成一一映射关系，堆维护$\min_{k \in [j,i]} (dp(q_k)+a(q_{k+1}))$，然后每次查询即可。这里方便删除可以用multiset

Codeforces 1097F
题意：给$n(n\leq 10^5)$个multiset，然后进行如下操作：
1 x v：把第$x$个multiset变成${v}$
2 x y z：把第$x$个multiset变成$y∪z$
3 x y z：把第$x$个multiset变成如下内容：$gcd(a,b)|a∈y,b∈z$
4 x v：查询$v$在第$x$个multiset里出现的次数奇偶性

只关注奇偶性所以想到了bitset……
然后刚开始我发现$gcd$操作可以反演/容斥去做……然后跪了
看别人代码发现只需要对询问进行反演即可。。
维护$f_x(i)$为第$x$个multiset中$i$倍数的个数。
那么显然$y∪z$等价于$f_y(i)+f_z(i)$，$gcd(a,b)|a∈y,b∈z$等价于$f_y(i) \times f_z(i)$
然后根据位运算的技巧，$xor​$是不进位的加法，$and​$是不进位的乘法，所以上面操作
$f_y(i)+f_z(i) \Leftrightarrow f_y(i) xor f_z(i)$
$f_y(i) \times f_z(i) \Leftrightarrow f_y(i) and f_z(i)$

然后考虑怎么询问答案。设$g(i)$为$i$的个数。
我们已经维护了$f_x(i)$为第$x$个multiset中$i$倍数的个数，那么根据反演：
$$
g(i)=\sum_{d=1}^{\lfloor \frac ni \rfloor} \mu(d)g(di)
$$
即可求出。对于反演式子中的乘法，可以预处理$bitset$的$\mu$，然后做$and$运算，加法即为最后得到的$bitset$中的$1$的个数。

poj 2942
题意：
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的$2$个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数$n$，再给出$m$对憎恨对（表示某$2$个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议？

建补图，补图中的边即为两个骑士能一起开会议。

引理：

一个双联通分量中存在奇环，那么整个双联通分量的点一定至少被一个奇环包含。

那么本题就是在点双连通分量中求是否是奇环即可，奇环判断用二分图判定判。
容易发现二分图没有奇环，所以可以判断。

Codeforces 1101D
题意：给出一棵无向带点权树，定义$dist(x,y)$为$x,y$之间的点(包含$x,y$)的个数，$g(x,y)$为$x,y$之间所有点权$gcd$，求最大的$dist(x,y)$，并且$g(x,y) \geq 2$

由于$2 \times 10^5$以内的数最多$7$种质数相乘，所以可以对点权分解质因数，指数不重要，只考虑质因子，因为质因子相同的$gcd$一定$\geq 2$。

所以我一开始想对每个质因子建一棵树，然后在树上做类似直径的DP。
这样的树的总大小不会超过$7n$，但是空间就比较爆炸，虽然可以用map之类的搞但是麻烦得要死还带了$log$。

其实不需要建那么多棵树，直接一次DFS，找到孩子如果和自己有公质因数，那么像树直径DP那样转移即可。

注意这里距离为点的个数而不是边的条数，DP 方程要特别注意

即某个点初始化长度即更新为1，然后转移时

ans = max(ans, st_dfs[u][k].second + st_dfs[v][j].second);
st_dfs[u][k].second = max(st_dfs[u][k].second, st_dfs[v][j].second + 1);

注意加一的位置，画画图更好。

poj 3696
题意：给出一个无向图，动态加边，动态询问桥的条数。

先用 Tarjan 求出桥的条数并且边双连通分量缩点，变为一棵树，然后树上的边就是桥。发现如果加了一条边$(x,y)$，则树上构成一个环，树上的部分都不再是桥。所以可以将这个环又缩成点。具体实现将所有点并到$LCA(x,y)$处，显然可以并查集轻松维护。也可以不求 $ LCA $，将每个$(x,y)$路径上的点并到他的父亲，一样的效果。

本题还有种解法，即只求出最开始桥的条数，然后将搜索树树剖，将桥边权赋值为1，那么加了一条边$(x,y)$，则树上构成一个环，答案将减去树上$(x,y)$部分的权值，并且将$(x,y)$全部置为 $ 0 $

BZOJ 2208
题意：求无向图中每个点能到点的个数。

显然传递闭包模板，这里类似CH2101，这题是无向图而且数据范围小。所以可以尝试暴力。

暴力是$n^3$的，用 $bitset$ 优化即可达到 $\frac {n^3}{32}$

具体就是将邻接矩阵存在$bitset$中, 枚举每个点$i$，然后找能到$i$的$j$，$i$能到的$j$也能到，所以把$i$的$bitset$并给$j$

BZOJ 1912
题意：给你一棵$n$点$n-1$边的树，要从$1$开始出发走遍所有边然后回到$1$，现在你可以加$K(1 \leq K \leq 2)$条边，并且加的边正好走一次，求出最小的路程。

明显如果不加边答案即为$2(n-1)$。
考虑加一条边情况：此时加一条边在$(x,y)$之间，相当于使答案少了$dis(x,y)-1$。即只走这条边不用回溯$x,y$之间的边。我们想要答案最小，那么$dis(x,y)$要最大，所以$x,y$是直径的两个端点。

加两条边的情况，可以考虑先将直径加边，然后再将直径上的边删除，然后树变为森林，求每棵树的直径取最大值。但不一定第一条边加在直径最优，这个贪心是错的，但是分还挺多。
我们考虑第一条边还是先加直径，但是我们之后将直径上的边权都改为$-1$，然后再对树求一下直径，然后答案减去直径长-1。
因为-1相当于还原之前选的直径上的边，即这个位置还是走两次。感觉和Bzoj 1050类似。
这里有负权就不能两次搜索找直径了，所以要用DP，DP有点类似点分治。
最开始原图还是最好用两次搜索，这样方便找到端点。

BZOJ 1801
题意：在一个$N$行$M$列的棋盘上，让你放若干个炮（可以是$0$个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。

先是可以发现每行每列最多放两个棋子。
然后我们可以暴力剪枝过掉30分。
根据暴力思路，我们按行DP，列记录状态。
考虑优化，我们可以做一个三进制状压DP，记录每行的状态(放了0个，放了1个，放了2个)来DP。
实质上，我们不需要知道具体的棋盘是怎么样的，我们可以像Bzoj 1079那样记录。
设$dp(i,j,k)$为前$i$行有$j$列现在有$1$个棋子的，有$k$列现在有$2$个棋子的方案数。
这样就非常好转移了，具体看代码转移注释。

Bzoj 1123
题意：Byteotia城市有$n$个towns, $m$条双向roads. 每条road连接 两个不同的towns ,没有重复的road. 所有towns连通。输出$n$个数，代表如果把第$i$个点去掉，将有多少对点不能互通，点对有序。

求出割点，然后对每个割点进行计数，显然如果删去割点，原图变为几个连通块，对于每个联通块都与不在这个连通块的元素不连通，所以求出第一部分的解。然后因为割点父亲的联通块无法通过割点来判，那么减一下算就行。最后割点本身还有算，加上$n-1$

对于不是割点的，答案为$2(n-1)$