题目很简短：给定一棵树，边有权，求一条路径使得边权和等于K，且边数最少。第一次做树分治，Orz cxjyxx_me。

点分治大体思路

对于一个有根图的某个点，它的状态只有两种：

• 不在答案的路径上。这个时候就要递归处理它的所有子树，取一个最优答案。
• 在答案的路径上。

在答案的路径上的话，也有两种状态（不是每个题目都需要分开考虑）：

• 这个点在答案的链的一端。可以DFS。
• 这个点在答案的链的中间。可以DFS每棵子树，然后合并两条链。

有意思的是，这个看似暴力的分治，在每次选取重心的时候，可以证明有O(nlogn)的复杂度。所谓重心，就是以它为根的树中最大子树最小的那个点。实际做的时候并不需要每次都换根，只需要以任意点开始做，算出这样形态下每个节点的大小，这样，换到以i为根的时候，只要多出一个n-son[i] (n为节点总数)的子树即可。

这题的做法

因为K不是很大，所以可以开个桶记下来所有子树出现过的边权和，这样如果一个答案是T，那么我们只要考虑K-T即可。但是需要注意一个问题：我们并不希望出现两条链都在同一棵子树上的情况，所以我们在做DP的时候，要先更新答案，在更新用来统计边权的桶。

用dist[u].first表示到达u点的路径长度，dist[u].second表示到达u的边数。m[k].first表示k这个边权最少需要几条边可以走到，m[k].second作为时间戳，用来区别递归时的不同子树。

代码

LCA

这题经过seter重做数据后，和spoj原题很大的不同是：强制在线。也就是说求LCA不能再用各种离线算法（比如Tarjan）。在线求LCA的算法我能想到的有两个：一个是DFS序+RMQ，一个是倍增算法。因为几乎没打过倍增算法，所以就用倍增算法做了。

倍增求LCA的主要思路是：求出i点往上2^j个父亲parent[i][j]，还有i点的深度。转移很愉悦parent[i][j] = parent[parent[i][j-1]][j-1]。然后查询的时候就先让两个点u, v爬到同一个高度，然后再从同一个高度爬到LCA。

可持久化线段树

这题竟然是可持久化线段树，我一开始的时候，还以为是树链剖分之类，后来Orz cxjyxx_me和 Orz Yangyue之后发现这个可以用可持久化线段树做。（询问区间第k大肯定是建立权值线段树，对于原始的区间第k大参见：从区间第k大讲起）

具体的做法就是先求出一个特殊的DFS序：当一个点入栈的时候在可持久化线段树上新建版本+u，在出栈的时候建立版本-u。这个时候可以发现，对于每个点u，我们找到它那个+u的版本，如果直接从这个版本走下去，会发现恰好是u这个点到根（一般就当作1了）这条链上的所有数。因此，对于查询路径(u, v)，我们可以用版本+u + 版本+v - 版本+lca - 版本+parent[lca]来表示(u, v)路径上的所有数。然后就很愉悦的求第k大了。

代码

写起来还是很愉悦的

直到做完这题我才完全搞清楚Splay的标记下传的正确姿势。顺便说一下，这题是双倍经验题，bzoj2209 [Jsoi2011]括号序列也可以去交，只要把读入输出改一下。

看起来很简单

1. Replace a b c Solution: Tag!
2. Swap a b Solution: Tag!
3. Invert a b Solution: Tag!
4. Query a b … What the fuck?

Query?

首先还是得膜拜AnOldMan的题解。

考虑把一个不合法序列中的合法部分全都消去，那么序列一定会变成类似)))(((((这样的形式。这个时候，答案就是[(右括号数量+1)/2] + [(左括号数量+1)/2]。

那么如何统计出消除了合法部分之后剩余的左右括号数量呢？实际上如果把左括号当作+1，右括号当作-1，那么从左边开始，如果出现了一个左括号，相当于阻挡了减小的趋势，我们计算出左起最小值，那么这个就是我们要求的右括号的数量。同理维护右起最大值，就是我们要的左括号数量。

看起来轻松愉悦啊

仍然是点分治，点分治是个蛋具体参见[BZOJ2599][IOI2011]Race。

这题和那题不一样的是，要求边权和<=K的。一个比较科学的统计方法是，统计出点u为根的树中所有的合法方案，再扣掉两条链都在同一子树内的不合法方案。

代码

  ∑∑((n mod i) * (m mod j))  1<=i<=n, 1<=j<=m, i≠j
= ∑(n mod i) * ∑(m mod i) - ∑((n mod i) * (m mod i))
= ∑(n-[n/i]*i) * ∑(m-[m/i]*i) - ∑(nm-([n/i]+[m/i])i+[n/i][m/i])

然后就分块暴力了。

这题很容易看出来求n!/(A1! * A2! * ... * An! * (n-ΣAi)!) % M，但是模数太大，用一种比较特殊的方法，这个也是对付阶乘取模的一个通用方法。对于比较特殊的情况，可以参考[BZOJ2313]分组

大体思路

• 把模数M拆成质因子相乘的形式p1^c1 * p2^c2 * ... * pk^ck，然后对每一项pi^ci求答案，最后中国剩余定理合并。
• 把阶乘拆成n! = A * pi^B的形式，其中A为除去所有pi因子之后mod pi^ci的结果。这样做除法的时候，就可以指数相减，A再用扩展欧几里得算法搞定。

拆阶乘

n! = (n%p^c)! * ((p^c)!^(n/p^c)) * (n/p)!

前面两项可以预处理fac[i]数组和快速幂解决，后面那一项递归。需要注意的是，算fac[i]的时候，要把所有的p的倍数去掉。也就是说：

fac[i] = fac[i-1] * (i % p ? i : 1)

代码

求平面内最近点对。不用K-d Tree的话，可以用分治。程序十分简洁易懂。可以用抽屉原理证明，合并的时候每次最多考虑7个点。

首先，数学书上说，平行光产生的投影形状和大小都不会改变= =。因此，这一个个的圆台的投影就是一个个圆和它们之间的公切线。让x轴穿过所有圆的圆心，这样就变成了求x轴上方面积*2。

这题可以用自适应Simpson来做（似乎只要不是FJTSC，求面积并都可以用自适应simpson？？）。自适应simpson的主要思想是：根据[Simpson’s rule](http://en.wikipedia.org/wiki/Simpson’s_rule)计算一个函数f(x)在[lef, rig]上的近似面积，然后分别计算在[lef, (lef+rig)/2], [(lef+rig)/2, rig]上的近似面积，如果两者之和约等于前者（abs(S1 + S1 - S) < EPS），那么就返回近似面积，否则递归计算左右两边。

自适应simpson看起来十分轻松愉悦，但存在下面2个风险：

• 不保证正确性：可以构造锯齿函数让递归的第一次计算就符合要求，但实际上仅仅是第一次误差很小，如果细分的话就会发现面积误差很大。
• 不保证复杂度：即使没有卡simpson的数据，EPS太小会导致TLE，EPS太大会导致精度误差WA。并且，一般情况下，计算f(x)的复杂度有O(n)

另一方面，自适应simpson的编程复杂度还是非常愉悦的，可以作为考场的骗分利器！

在实现的时候，建议还是传几个参数进去，这样可以减少计算函数值的次数，速度快很多！

连接到Dropbox需要一个脚本：Dropbox-Uploader

然后配合下面的脚本就可以自动备份到Dropbox了

1
2
3
4
5
6
7
8
9
10
11
12

#!/bin/bash
dt=`date +"%Y%b%d"`
dir=/root/backup
mkdir $dir/$dt
cd $dir/$dt
tar zcf home_$dt.tar.gz /home
tar zcf conf_$dt.tar.gz /usr/local/nginx/conf
/usr/local/mysql/bin/mysqldump -uroot -ppassword --all-databases > db_$dt.sql
../dropbox_uploader.sh mkdir $dt
../dropbox_uploader.sh upload db_$dt.sql /$dt/db_$dt.sql
../dropbox_uploader.sh upload conf_$dt.tar.gz /$dt/conf_$dt.tar.gz
../dropbox_uploader.sh upload home_$dt.tar.gz /$dt/home_$dt.tar.gz

因为独立插头还有最小表示法没有打过，独立插头没看懂，广义路径连看都没看过，所以这些不再本文的总结范围内。

去年学插头DP的时候还是很惧怕的，也只做了一题，还是按着课件对着标程打的。还好今年终于懂得原理了。其实打多了也变成模板了（当然每题的转移不一样）。

插头DP有下面的分类：

• 按模型：多回路问题、单回路问题、简单路径问题、广义路径问题
• 按表示方法：是否有插头、括号法（广义括号法）、最小表示法

插头DP最朴素的实现就是用f[i][j][k]记下在(i, j)这个点轮廓线状态为k的答案。空间上很大，所以一般用队列实现了。而且队列实现可以免去动规数组初始化的麻烦。队列实现需要一个hash，对于内存比较宽裕的题目，可以直接开一个桶解决。

参考资料

• 基于连通性状态压缩的动态规划问题 - 陈丹琦

多回路问题

这类问题是最水的，只要记录当前位置有没有插头即可。比如说hdu1693。

• 有上插头和左插头 → 没有右插头或下插头
• 没有上插头或做插头 → 有右插头和下插头
• 只有一个插头 → 右插头和下插头分别只有一个

单回路问题