A*搜索

无

无

树同构

Prufer 序列

拓展域并查集

可持久化数据结构 3

线段树分治

无

见专题部分

最小割

一般图最大匹配

洛谷p1379

A*搜索

八数码游戏移动到某一指定图案的最小步数

选取估值函数 $g(n)$ 为当前图案和最终图案有多少个方块不用。然后使用A*搜索即可。

洛谷p4585

线段树，分治，可持久化，字典树

有 $n$ 个商店，编号为 $1\sim n$。每个商店有一个价格为 $v_i$ 的特殊商品。接下来 $m$ 个操作：

1. 时间流逝一个单位，同时商店 $s$ 额外进货一种价格为 $v$ 的商品
2. 给定 $l,r,d,x$ 表示一个顾客的信息，询问该顾客的最大满意度。(满意度等于 $x$ 异或顾客可以购买的商品价格)

记询问时刻为 $t$，该顾客只能在编号为 $[l,r]$ 的商店购物，且只能购买特殊商品或进货时间为 $[t-d+1,t]$ 的商品，问该顾客的最大满意度。

注意初始时刻为 $0$，且询问不会导致时间流逝。

对与区间询问最大异或和操作可以用可持久化字典树 $O(\log v)$ 解决，于是可以先 $O((n+m)\log v)$ 处理出只考虑特殊商品时每个询问的答案。

接下来考虑对时间建立线段树，同时将每个询问加入线段树，遍历线段树时更新答案。

对于修改即进货操作，考虑先对其根据商店编号进行排序，这样就可以使用可持久化字典树加离散化处理询问。

然后遍历线段树时处理完当前节点询问后可以根据修改的时间分配到左右子树处理，每次处理询问重建字典树即可。

时间复杂度 $O((n+m)\log v\log m)$。

不错的线段树分治练手题。

P1646 [国家集训队]happiness

最小割，二者取一式问题

给定一个 $n*m$ 的矩阵（座位表），要分文理科了，每位同学选文或理科可分别获得一个喜悦值，如果某同学和其相邻的同学选了同样的科，那么将获得额外的一个喜悦值，求最大喜悦值。

建立网络流模型，总量减去最小割即为答案。对于每个点 $(i,j)$，从 $s$ 连一条容量为选择文科的边，到 $t$ 连一条容量为选择理科的边。对于 $(i,j)$ 和 $(i+1,j)$ 两个点的组合情况。假设这两个点同时选文科有 $w$ 的喜悦值，我们新建一个节点 $x$，从 $s$ 向 $x$ 连一条容量为喜悦值 $w$ 的边，再从 $x$ 向 $(i,j)$ 和 $(i+1,j)$ 分别连一条容量为 $INF$ 的边。对于左右前后、文科理科同理！

经典的二者取一式问题