有生之年系列之历年APIO题解 (4/9)施工中……
今天，大多数高二都去雁荡山春游了，就剩几个化竞的以及我。
本来打算早上参加GCJ，突然发现GCJ竟然不是放在TC上举办的，TC群的公告里面一直有GCJ的日程表，我就以为GCJ是TC办的，没有怎么在意，今天一查才知道，GCJ竟然不是放TC上比的，而且报名时间TMD早就过了TAT
然后只能苦逼地刷APIO了，最近状态又下滑了不少，连APIO的一些水题都不会做了。在百度的帮助下，APIO的题总算是做得七七八八了，再加上APIO的题目不是很多（记得我以前一直以为APIO的历史比Noip还要悠久……），就写一篇题解好了，至于CTSC那就呵呵了，我所知道的只有VFK一人凭着极大的毅力、决心和智商干掉了很多CTSC的题目，我这种蒟蒻还是算了吧……
APIO 2007 (3/3)
2007的题目BZOJ上是有的，只不过被标明为CTSC2007……
风铃-Mobiles
BZOJ上这道题的名字叫做风玲，还有风铃和手机到底有什么关系……
刚开始以为这道题是神题，想了想发现居然是简单的递归，对于每个结点，左右各递归一次，然后根据左右的情况再判断。假设最深的叶子结点是x类结点，第二深的叶子节点是y类结点，那么，我们定义一个结点是第1类当且仅当该结点往下所有的叶子结点都是x类结点，一个结点是第2类当且仅当该结点最底下的叶子结点部分是x类部分是y类，一个结点是第3类则是叶子节点全为y类。当一个结点的两个子节点都是2类的时候输出无解，否则根据题意来就行了。
数据备份-Backup
这道题目做了挺久了，是做BZOJ2151 种树的时候顺便做掉的。种树不会做，然后找到了hzwer的blog，结果看到了这句话“做过数据备份这就很简单了”，然后，hzwer的blog同样也有这题的题解，所以……关门，放链接：http://hzwer.com/2934.html
动物园-Zoo
APIO 2008 (1/3)
BZOJ上只有一道题目，所以剩下的两题以后慢慢搞吧……BZOJ上没有就没有任何动力了……
珠链交换器-Beads
交互式的题目……如果UOJ上出现了这道题，我可能会做一做，否则……呃，那就算了吧……
免费道路-Roads
一眼秒的生成树，结果还是WA了好久。开始是将k条鹅卵石路径先连，然后再连水泥路，但是这是有问题的。我们举个栗子吧：有两条鹅卵石路1-2和2-3，有一条水泥路1-2（似乎不符合题意？不用在意这些细节啦），然后按顺序来的话，你得先选1-2的鹅卵石路，然后就没有什么可以选的了……所以，我们得先将水泥路连上，再用鹅卵石路补全整个图，接着再用能连的鹅卵石路替换水泥路，最后再将水泥路连上……
DNA-DNA
中文名称和英文名称一样看起来好像有点奇葩？还没看过题目，而且BZOJ上也没有，先扔着吧。
APIO 2009 (2/3)
采油区域-Oil
分别求出左上、左下、右上、右下以及行、列上的最大值，然后分六类讨论，图就不上了，很麻烦。Claris以前给我们出过只有两个矩形（这题是三个正方形）的情况，当时我是用两次DP做的（两个矩形只有两种状况），然后以为这题只要三次DP就行了，结果发现如果这样的话，状态表示起来特别麻烦（其实是我自己也不知道该怎么搞），所以就根据网上题解分类讨论了。
会议中心-Convention
听说forever97学长以前出过这道题，当时他本来也是要求输出字典序最小的，结果发现他自己也不会做，然后就降低了难度，变成了那种最简单的贪心，然后，当Claris做了APIO的这题之后，这题就被拿来黑forever97了，当时还出了一场模拟赛，里面都是forever97曾经出过题目的加强版……然而还没坑出来。
抢掠计划-Atm
一眼题，先是SCC缩点，然后最短路。当我照着自己的模板打完SCC和拓扑之后，就开始抓狂了。因为不管我怎么改自己的拓扑，总有两个点过不去（至今不知道为什么），然后去网上搜了一下，发现好像大家都打了最短路？然后就打了SPFA，结果就AC了……
APIO 2010 (3/3)
这套题的难度不是很大，感觉拿来当机房Noip难度的模拟赛还是绰绰有余的。
特别行动队-Commando
这道题是简单的斜率优化DP？（做了太久，忘记了）反正BZOJ上有一千多人AC的题目都是水题（口胡），你们看着办吧。
巡逻-Patrol
求树的直径？开始用的是两遍深搜，结果莫名其妙地出错了（好像是因为可能有多条最长链），后来把找第二条直径时候的方法改成对每个点找其出发的不同子树中的最长路和次长路（感觉我的程序好像还有点问题），然后就AC了……
信号覆盖-Signaling
似乎卡精度？照着网上的程序打的，找出所有的凸多边形和凹多边形，每个凸多边形对答案贡献为2，每个凹多边形对答案的贡献为1，最后再把平均值加3就是答案了。求凹凸多边形的时候，求出凹多边形的个数apol，凸多边形数目就是$tpol=\dbinom{n}{4} -apol$。求凹多边形数目的话，枚举每个点，然后将剩下的点按照极角排序一下，就能$O(n)$求了。
APIO 2011 (1/3)
应该是比较难的一届APIO了，第三题在BZOJ上的AC人数仍然为0……
方格染色-Color
这道题在没有想通前还是很难的，但一旦想通就简单了。首先，根据题意，我们用c(i,j)=1表示格子(i,j)的颜色是红色，c(i,j)=0表示格子(i,j)的颜色是蓝色。那么每个2*2的矩形中四个格子异或起来的值就是1。这样，我们就可以发现，c(1,1)^c(i,1)^c(1,j)^c(i,j)=1当且仅当i和j都是偶数。因为c(1,1)^c(i,1)^c(1,j)^c(i,j)相当于(i-1)*(j-1)个正方形异或在一起，当i和j都是偶数时，其值为1，否则其值为0。我们还可以发现，当确定第一行和第一列的颜色之后，剩下的颜色就都可以确定了。我们首先确定格子(1,1)的颜色（如果输入中没有涉及(1,1)的颜色则分两类讨论），那么我们知道格子(i,j)的颜色就等于是知道了（i,1)和（j,1)之间的关系，用加权并查集维护一下就行了。
APIO 2012 (1/3)
听Claris说，除了第一题，剩下两题都很神的样子。
派遣-Dispatching
忘了哪里看来的了，说是这题可以用左偏树做？具体做法我不懂，我用的是主席树+贪心，因为同样做了比较久了，具体做法也忘了，就这样吧。
守卫-Guard
还没做。
苦无-Kunai
还没做。
APIO 2013 (3/3)
机器人-Robots
这道题是斯坦纳树+DP，我开始做的时候并不知道这是斯坦纳树，只是觉得预处理之后可以用SPFA来搞，但是不知道机器人合并的情况该怎么解决，后来问了Claris才知道是斯坦纳树，于是搜了一下题解。昨天晚上（5.4）照着PoPoQQQ的程序打了一遍，还有些细节问题，今天早上起来稍微改一下就AC了。
道路费用-Toll
花了一两个小时左右，终于AC了，这道题的创意曾经被Claris拿来出模拟赛，虽然当初做的时候想出了做法，但是由于代码能力太差，还是没有搞出来。大致的思想就是将无关的边缩掉，就剩下了20条边，再用位运算来搞，一共$2^k-1$种方案。其实前不久就已经想要做这道题，但是没有想好该怎么搞，我以为哪些缩掉的边也是要计算费用的，现在才发现，原来要计算的费用只与那k条边有关，其次，k条边的边权需要根据别的边来定，做法是，枚举剩下的边，然后更新图中的选中边的边权，可以先求出生成树再用LCA搞，我懒得打，就打了深搜，反正只有k+1个点，还是挺快的，在我的笔记本上跑，有两个点超时，不过我的笔记本本来就挺差的，扔BZOJ上过了。
出题人-Tasksauthor
UOJ上已经出现了这题，所以大家可以去UOJ上做啦！题目大意就是给出一些程序，要你造出数据，在时间上卡掉一个程序，但是不卡掉另外一个程序。这道题对数据的大小有着要求，数据中数字的数目F必须要少于给定值T。卡Floyd是最简单的，101个点，没有边就可以卡了，卡Dijkstra和卡Bellman-Ford我都是看了题解之后才会的。无向图的Dijkstra用一条负边权就可以卡了，但是这里不能这么做，因为一条负边权等于是一个负环，这道题是不能有负环存在的。所以，题解中给出了一种三角形卡法，A到B的直接距离可以比A到C的直接距离大上很多，但是如果C到B的距离是负的，那么实际上A到B的距离可能就会减小，这个时候Dijkstra就要重新更新一遍，因此，构建16个三角形，查询6遍就行了。Bellman-Ford需要用逆序的最短路来卡，我的做法是，设i到(i-1+n)%n的边权为1，剩下的边边权全都置为$+\infty$，查询十遍0和1之间的最短路，要注意的是，总边数需要满足题目要求。之后两个点则是染色问题，实际上只要求你能卡掉一个程序就行了，我看了一下，发现这个程序是迭代加深搜索，最坏情况下当然要搜n层，构造了一个完全图就卡掉了。
APIO 2014 (3/3)
相比过去三年的APIO，这年APIO的题目应该是最水的了（雾）据说考场上有很多人AK了真是可怕！
回文串-Palindromes
这道题可以看我扔在UOJ上的回文树的入门向论文，瞬间可以秒掉这题。据说考场上大多数人都打了manacher+SA或者是hash？果然还是我们大回文树厉害……
序列分割-Sequence
具体什么时候做的这题忘了，斜率优化DP，应该是很水的一道题了。
连珠线-Beads
这道题坑了我一天的样子。首先，很明显就是树形DP，于是开始打暴力，花了半个多钟头打完暴力后扔BZOJ上测，TLE了，顿时信心大增，以为自己的暴力是正确的，谁知道BZOJ竟然是先测大数据再测小数据的QAQ然后好不容易打出了$O(n)$的DP却各种WA了，和暴力对拍死活拍不出来，再和Claris的程序对拍，瞬间出错，这才知道是暴力打萎了。接着就各种乱想了……坑了一天之后突然发现自己后来想复杂了，只要在原先的DP方程上改一改就行了，想通了之后很快就AC了。
APIO 2015 (0/3)
2016年3月31日 17:10
谢谢王北大菊苣，虽然您的回文树我还是没咋看懂
关于风铃我想可能是这样的：mobiles有一个释义是“悬挂饰物”