Background：我们机房的厕所很臭，没人扫，因此不让用

About Beijing

处处是毛（柳絮）！堵车！脏乱差/随地摆摊一样有！路横平竖直，很容易找到方向！干燥！昼夜温差大！

About Tsinghua

车多！饭便宜！没汤！几乎都喝饮料！校园太大！从六教到桃李园吃饭再回来就快要上课了！没有午休！高富帅巨多，Macbook/IPhone/Monster随处可见！

About Lessons

听不懂！有的还挺有趣（AI、教你打游戏、函数式编程）！一群人睡觉！某湖南神牛发言总是听不懂，和中文听力类似，不知所云！

About Fujian Team

认识了一些福建的OIer，夏一的lyd/ldf/crc，福三的cty，师大附中的zgx，三明一中的ly。总之，我是最弱的一个。

About APIO2012 Contest

20分……如果加上第一题的v.size()打成n以及第二题的输出没排序的话，那就90……今年铜奖40……

About Me

弱爆了，在跟福建的小圈子走的时候，发现他们讲的好多我都不会……

Read on →

这题就是求在树中添加1条或者2条边，使得从第一个点开始走，在必须经过新添加的边的前提下，经过每个点且回到源点的最小长度。

加1条边

如果我们不加边的话，那么很显然，总的长度就是2*(n-1)。做这题的时候比较容易想到，如果添加1条边，那么连接最远的两个点。

事实上这确实是有点道理的：假设叶子A和叶子B的最近公共祖先为P。那么，如果我们新建边(A, B)，则可以减少dist(A, B)-1的长度。因此，如果我们把树中最远的两个点连起来，那么就减少了树直径-1的的路程。

加2条边

一开始我的想法是加完1条边后，再在剩余的图中找一条最长的路径，扣掉即可。但实际上，样例数据十分好地把这个想法扼杀了。

Read on →

这题也是USACO 2002 February 的题目。

这题显然是树形动规，状态表示也十分容易想到，用f[i, j]表示以i为根的子树，删除j个节点的最小代价。问题的关键就是如何求解。

由于是多叉树，所以不能够直接枚举每一个孩子节点分配多少删除目标（直接枚举的话莫非是要写一个全排列？？），考虑将多叉树转成二叉树，左孩子右兄弟，那么只要考虑孩子和兄弟之间的关系。

如果i这个节点和i的父节点的联系被切断，那么显然不用考虑孩子节点了（左孩子），直接考虑把j-son[i]-1删除任务交给兄弟（右孩子）。

否则如果给孩子（左孩子）分配了k个删除任务，那么兄弟（右孩子）就得完成j-k个任务。

另外，这题可以是从大树中剪除一棵子树或者分离出一棵子树，所以答案还得枚举以谁为根最优。

注意边界情况的处理。

PS.这题也可以在树形DP里面套一个背包。 Read on →

我的第一题斜率优化，没看题解就A了，高兴啊^O

拿到这题一开始我的想法是根据二次函数的对称性来贪心解决，后来发现这样不仅难以实现而且有严重的BUG。

随后就想到了DP，十分朴素的DP：用f[i]表示前i个队员分组后的最大值，那么可以枚举j，使得j+1..i为一组，计算其中的最大值。

令S[i] = a[1]+...+a[i]，以及calc(x) = Ax^2+Bx+C
f[i] = max{f[j]+calc(S[i]-S[j])   0 <= j < i

经实验证明，这么做可以拿到30分。

所以考虑一下优化。如果能在决策的时候，也就是选取j的时候，能够在O(1)的时间内完成，那么总体的复杂度就由O(n^2)降至O(n)。

Read on →

这题如果不止有123三种编号，那么可以用nlogn的LIS解决。但是这题限定了只有123三种编号，因此可以简化成O(n)的动规。

先考虑升序序列，降序类似。

用f[i][j]表示前i位升序，并且第i位为j（j = {0, 1, 2}）的最小修改次数。那么就有：

• f[i][0] = f[i-1][0] + change(a[i]->0)
• f[i][1] = min(f[i-1][0], f[i-1][1]) + change(a[i]->1)
• f[i][2] = min(f[i-1][0], f[i-1][1], f[i-1][2]) + change(a[i]->2)

升序的答案就是min(f[n][0], f[n][1], f[n][2])

降序类似，最后答案就是升序降序中的最小值。

Read on →

这题是线段树的经典应用：求区间左边连续最长空位。为了O(logn)的复杂度，得用lazy-tag，因此也增大了代码复杂度。

线段树中记录三个东西：lmax, rmax, sum，分别为区间左部起最长空位，从右边起最长空位，区间总共的空位。因为当sum==0时lmax=rmax=0；sum==rig-lef+1时，lmax=rmax=rig-lef+1；sum!=0且sum!=rig-lef+1的时候lmax/rmax不固定；且sum可以用来判断区间是否有足够的空位，因此用sum作tag再合适不过了。

根据这个定义，遗传和上传就确定了：

遗传：如果sum==0，那么其儿子的sum=lmax=max=0；sum==rig-lef+1，其儿子的sum=lmax=rmax=各自区间长度。

上传：lmax=left_son.lmax, rmax=right_son.rmax, sum=left_son.sum+right_son.sum。当然要特殊处理：如果left_son.lmax==left_son的区间，也就是左右孩子在左侧相连了，那么lmax+=right_son.lmax。rmax类似。

插入/删除：先遗传，如果区间包含在修改区间内，那么马上修改（插入就是清空，删除就是释放），否则从中间切开做左右子树。

查询：因为这题的查询总是伴随着插入，因此我们可以在查询成功后直接插入，因此query函数可以设计成返回bool值。查询也是要先遗传，然后按照：左子树、左子树+右子树、右子树的顺序依次查看各区间剩余大小，如果合适的话就在那个区间插入。插入之后一定要记得由孩子更新自己，也就是上传。 Read on →

一个显然的事实：当b[]中的所有元素都出现在a[]中时，答案最小。

因此，不妨将a[]离散化到v[]，先不考虑降序（因为数据中没有降序，所以我程序里面也就没有打降序），接下来就是一个水水的二维动规了：

f[i][j]表示前i个元素升序，并且把a[i]改成v[i]的最小代价。那么就有：

f[i][j] = min(f[i-1][k])+abs(a[i]-v[j]) (k<=j)

显然min(f[i-1][k])可以记录下来，因此复杂度只有O(nm)。 Read on →

题目求的是在免费部分边的条件下的最短路。

这种题目非常的经典，解决方法也十分简单。枚举答案ans，对于每一条边，如果w>ans，建边；否则建边。之后做最短路，求得的最短路就是需要被免费的边。如果最短路小于题目所允许的k，那么当前方案就是合法的。注意到根据ans的变化，所求得的最短路是具有单调性的，因此可以二分答案。根据所求的最短路与k的关系，调整二分左右边界，即可出解。 Read on →

很显然是树形动规（虽然网上也有贪心的做法）。因为每个节点必须被覆盖，所以设：

• f[i][0] => i已经被其父亲覆盖
• f[i][1] => i必须自己覆盖自己
• f[i][2] => i将会被儿子覆盖

因此就容易得到：

• f[i][0] = sum{min(f[son[i]][1], f[son[i]][2])}
• f[i][1] = sum{min(f[[son[i]][1], f[son[i]][2], f[son[i]][3])}
• f[i][2] = sum{min(f[son[i]][1], f[son[i]][2])}
• 注意，f[i][2]中的min决策不能全为第二个（这样i就没有被孩子覆盖了），也就是说起码得保证有一个孩子是选则1的。如果没有的话，就得再枚举一遍把哪个孩子从2换到1之后f[i][2]最小。f[i][2] = min(f[i][2]-f[son[k]][2]+f[son[k]][1])

我还是喜欢写记忆化搜索，比较方便： Read on →