总结

今天是腊月初五，还是做的 D2。前两道题都很简单，四道题找到了三道题的原题。

题解

今天不是很喜欢说话，就说这一句话。算了还是简单总结一下。今天考的还行，就是对轮廓线 dp 还是不是很熟悉。今天 D2T3 没有用网络流想出后虽然想到了看到数据范围可能是轮廓线 dp，但是不是很会。没有足够大的决心去想另一种方法。

A. IOI 馒头

原题来自 JOI 2014 Final。

发现取一定个数的馒头时肯定是选最大的几个馒头。那么考虑现在选个馒头，那么要选择盒子容量大于等于的最代价。那么类似于背包 dp 一下再搞个后缀就可以了。

B. Lost Kingdom

暂时还没有找到原题。就是给你一个无向连通图，要你选择若干个连通子图，然后将边集与点集求交，求这个东西连通块个数最多是多少？

容易发现一个边双可以所有边都没有，就是点的个数，（弄一个环出来搞两个链就行），然后发现两个边双合并是有一个割边的，会损失一个连通块。发现合并一定是不劣的，所以就是总点数减去割边的数量。

C. Lighthouse

原题 http://codeforces.com/gym/103446/problem/C 略有加强。

数据范围变成了，所以最少的那个边是不大于的。这道题就是轮廓线，但是不是插头。就是三种状态，一种是无关的，就是没有影响的，可以理解为障碍（但这个位置不一定是障碍），另一种是这个格子垂直方向被消灭，但是分为两种，一种是之后，一种是已经了。就暴力转移就行。

D. Dark Blue

原题Gym102803E 。经过了加强，原题可以之类的过，这道题需要。。

差分约束好题。

就是给你一个未知的小写字母的字符串的 sa 后缀数组和 height 数组中一部分位置的值。要你求满足条件的最小字符串。考虑有值的 height 位置，发现就是一串相等和一个位置小于，这是充要的。考虑没有 height 的位置，就考虑下一个位置的大小关系，就是小于或者小于等于。然后就是一个差分约束。有可能有环，那环上都是 0（因为保证有解），然后 dag 上乱搞就行。（其实在 tarjan 的时候也可以顺便更新）。然后相等的用两次差分就行，因为容易发现是一个 sa 上的区间。

后记

还没想好。就不写了。今天很好。（感觉好水）