jiry_2's Blog

大爷们都在做POI的题，我这个蒟蒻也来凑凑热闹...又给自己挖了个大坑

[11.11]本来有点想弃疗了，后来发现大吧的博客上有几道的题解？

[11.13]迷の荒废感

完结撒花！最后剩下来一道计算几何折腾了很长时间实在是无力了..

现在做了几道：

16

【POI2013】Take-out 用两个栈就可以把每个c匹配的b给求出来，然后按照最左边点sort输出即可。

【POI2013】Tales of seafaring 把每一个点拆成两个BFS就可以计算出从每个点出发到其他点经过偶数、奇数条边的最短路，然后比较一下就好了，要注意特判孤立点的情况。

【POI2013】Bytecomputer 猜测一个位置的变化是单调的（想想很显然但是我似乎不会证明？），然后就可以DP了。

【POI2013】Price List 膜拜了题解..删边BFS。复杂度靠谱似乎是因为每一个三元环最多被枚举到三次？(反正我不会证明无向图三元环个数上界是[tex]O(m^{1.5})[/tex]。

【POI2013】Taxis 左半段一定是从大到小乘，因为后半段一定是一辆车走的，所以如果从大到小乘到可以被剩下最大的车一次带到家是有解的，那么这一定是最优解。如果无解，有一定的可能性是由剩下的车的距离都小于[tex]m-d[/tex]引起的，那么我们可以留下距离大于这个值的最小的车，然后依然按照这个策略走。这样就可以得到答案。

【POI2013】Tower Defense game 显然如果我们每一次都是选取当前没有被覆盖的点建塔，那么一定存在一个解，证明很简单，因为每一个城市在原来的方案中一定有一座塔和它相邻，那么如果把新塔建在这儿一定优于把原塔建在相邻的位置。所以只需要暴力覆盖即可（开始写了一个暴力没想到过掉了？复杂度感觉好乱..）

【POI2013】Multidrink 这种题似乎都应该从无解情况入手？想了半天没想出来就去膜拜题解了，按照树上1到n路径分层，每个节点和它连出去非路径上的点为一层，可以证明如果有解，那么一定存在遍历完一层再到下一层的解。然后后面就很简单了，显然只有当每一层只有链以及一些单节点的时候才有解，然后分类讨论搞搞。

【POI2013】Walk 开始以为是像CF某题一样用并查集搞，然后试着去想象样例四维的情况，然后爆炸了。。于是去膜拜题解。删去[tex]k[/tex]个点后一定至多存在一个联通块它的大小大于[tex]nk[/tex]。然后开hash搞BFS。main上面实现二十几分钟爆OJ爆的我都感觉自己要被封号了..最后在main上过了BZ上实在卡不过去。一个下午就在等main评测中度过了..（main上这题100分的只有一个，开始以为数据有问题，后来A了发现..这题满分136分..）

【POI2013】Triumphal arch 二分答案显然，令[tex]f_i[/tex]表示以[tex]i[/tex]为根的子树在到达[tex]i[/tex]之前最少要造多少座，然后判断[tex]f_1[/tex]是不是1就好了。

【POI2013】Maze 构造题苦手..开始分析无解情况，然后发现L必须要比P多4，然后发现没用...于是又去膜拜题解，核心在把规模为[tex]n[/tex]的问题转化为规模为[tex]n-2[/tex]的问题，提取"PL"单元或者"LP"单元，然后把剩余部分递归求解，最后把这个单元插到一条边上。这样就有了一个[tex]O(n^2)[/tex]的做法，然后用双向链表队列什么的乱搞就可以搞到[tex]O(n)[/tex]了。

【POI2013】Watering Can POI少有的数据结构题，当一个数大于等于[tex]k[/tex]后就不会再小于[tex]k[/tex]，所以每一次区间加后找区间最大值，如果大于等于[tex]k[/tex]那么把这个数删除然后插入一个树状数组。

【POI2013】Colorful Chain POI少有的水题，开个数组扫一遍就好了。如果不用快速读入可以AC但是似乎拿不到满分？

【POI2013】Where is the one? POI居然还真有交互题..首先选取位置1为基准点，然后二分求出和它相差最大的那个点位置，然后再找到距离这个点[tex]n-1[/tex]的位置，这两个位置一定是最大值和最小值，最后比较一次大小就好了。注意特判[tex]n=1[/tex]的情况。

【POI2013】Polarization 有趣的题目，开始只会一个[tex]O(n^4)[/tex]的树形DP，然后膜拜题解。最小值一定是[tex]n-1[/tex]（把树黑白染色即可），关于最大值有一个结论：一定存在一个最优解它所以的子树中的边都是朝向它或者离开它。然后要做的就是把每一个节点的子树分成两个集合使得它们尽可能的相近，即最大化函数[tex](n-1-a) \times a[/tex]，[tex]a[/tex]是一个集合的大小。因为一定只有重心的最大子树可能小于等于[tex]\frac{n-1}{2}[/tex]，所以其他的可以直接计算，重心直接把所有数分成小于等于[tex]\sqrt n[/tex]和大于[tex]\sqrt n[/tex]两组，第二组直接暴力背包，第一组则对每一个值背包，按模分组做。总的复杂度就是[tex]O(n \sqrt n)[/tex]

【POI2013】Laser 首先把每一条边用两个端点相对原点的角度代替，然后就变成了数轴上的线段，就可以DP了

【POI2013】Inspector 二分答案显然，然后差分，对于有限制的人可以贪，然后其余人用类似于noip2013d2t1的方法处理，复杂度[tex]O(Tn\log n)[/tex]（题解不详细是因为我不知道怎么回事就A了