好长时间没有写记录…感觉没有压迫感。
6.15
BZOJ 2069: [POI2004]ZAW PoPoQQQ大爷的题解 非常神奇的一道题。问题相当于从1号节点走到一个相邻节点，之后再不经过这条边走回1号节点。把这样一条路径的第一个不是1的节点记为$s$，最后一个不是1的节点记为$t$。这样就成了找一对$s,t$使得$len(1, s) + cost(s, t) + len(t, 1)$最小。去除1号节点，把点集分成两部分$A$和$B$，对于在$A$的节点$i$，其起始值为$len(1, i)$，之后做一遍dijkstra，所有$B$集合内的点$i$，可以更新答案$ans = min(ans, d[i]+len(i,1)$。这样如果每对点都不属于一个集合中做过一次最短路，就可以求得答案。对于$i$和$j$，$i \ne j$，则一定有一个二进制位不同，所以枚举二进制位，每次把这一位为1的分为一个集合，0的分为另一个集合，做一遍最短路。 查看代码
BZOJ 2525: [Poi2011]Dynamite 膜PoPoQQQ大爷的。首先肯定二分时间$T$，之后计算最小需要的点燃点的数量，验证之。处理出每每个点$i$儿子中，距离最远且有炸弹的点的距离$deepest_i$，以及从$i$点出发最远可以点燃的距离$down_i$。然后就比较显然了，看代码
BZOJ 1117: [POI2009]救火站Gas 之前做过一次，之后WA某个点弃疗了。树形dp，和上题区别是这个每个点有数量限制。维护救火站到达点$u$以后，还可以救火最大距离为$i$时，能救的点数量$have{u,i}$。维点$u$距离为$i$的点，还没有被覆盖的点$need{u,i}$。对于当前维护的点$u$，$i \ge j$，$have{u,i}$和$need{u,j}$可以抵消掉，即选择一部分救火站去覆盖点。当$i = j$的时候，一定要抵消掉，否则向上传递后，需要救火的的距离变远，而覆盖的范围变小，变的不合法，如果此时从其兄弟或祖先来救自己的话一定不会更优。对于其他的即使向上传递后也合法，那么暂时不考虑，让传递上去。当然对于$have{u,i}$和$need{u,i-1}$向上传递也会变得不合法，不过要等所有$have{u,i}$和$need{u,i}$抵消完之后才可以抵消这个（YY证一下这个吧，对着数据调出来的结论）。之后就是各种细节了，看代码
6.16
BZOJ 3203: [Sdoi2013]保护出题人 可以发现对于每个僵尸$i$都要满足$y_n \ge \frac{\sum_i^n A_i}{x_n + (n-i)_d}$。相当于求后面那个东西的最大值。把每个僵尸转化成一个点，$x$坐标为为$\sum_i^n A_i$，$y$坐标为$x_n + (n-i)_d$。这样可以发现，答案是过原点与某个点的斜率最大值。一定在上凸包上，而且往前面新加入点相对位置不会变，这样维护凸包就比较方便了。之后三分求答案。不过注意这个输出的时候，直接printf保留0位小数即可，转化成long long再输出来会崩。 查看代码
6.17
BZOJ 1122: [POI2008]账本BBB 先考虑不进行移动操作时方案，如果需要把“-”变成“+”，那么一定把序列前面一部分“-”变成“+”，这样后面所有可能为负的地方值都会加2。如果需要变成“-”，则一定在最后变。之后前缀和最小的地方如果非负后，那么一定整个序列一定合法了。对于有移动的时候，快速找到最小值可以用单调队列来做。查看代码
BZOJ 1127: [POI2008]KUP 构造题。先处理每行，看看是不是有符合条件的一段（矩形的宽为1）。之后如果没有的话，把大于2_K的点设置为障碍点，再找一个矩形的和大于K的。这个矩形和如果大于2_K，就减去一行，一直减到符合条件位置。因为处理过每行了，所以每次减的一定小于K，所以正确。查看代码
6.20
端午节快乐
BZOJ 2081: [Poi2010]Beads
枚举$k$，之后hash判重就可以了。从hzwer那里看到一个优化，对于反向的串不必插两次，而是把正向和反向的值乘起来。（其实我一开始不仅插两次而且怕冲突双hash了）
BZOJ 2082: [Poi2010]Divine divisor
题太神了。第一问其实是求质因数分解的最大指数$k$。第二问有$cnt$个$p_i^{k_i}$的$k_i$与$k$相同，答案是$2^{cnt}-1$。
可以把每个数小于$10^6$的质因子搞出来，剩下的要么是一个质数，要么是一个质数的平方，要么是两个质数相乘。判断质数可以用miller-rabin做，两个质数相乘可以互相求gcd来找。如果还没有找到那么肯定是两个质数相乘且没有再其他数里面出现过（注意要判读两个数是否一样）。
附上Matrix67的miller-rabin算法介绍。我的miller-rabin的a只取了2和3，结果没有卡。这题感觉细节特别恶心，而且最后还需要高精度！
感觉给main函数炸掉了TAT。查看代码
6.22
BZOJ 2083: [Poi2010]Intelligence test
一开始用的方法是利用st表的方法，记录后面$2^k$个和自己一样的数字的位置，再倍增找。BZOJ上莫名T掉，交到main上爆内存。看hzwer的题解觉得自己傻逼了，可以为每个数字开一个数组，记录这个数字出现的位置，之后二分即可。
BZOJ 2084: [Poi2010]Antisymmetry
manacher改变一下即可。不过注意这个需要对于不是’*‘（分隔符）的位置直接跳过不处理。因为如果某个不是分割符号为中心作为“可以覆盖到最远回文串”，则会导致复制过来的len出错，中心字符是无法“对称”的。
BZOJ 2085: [Poi2010]Hamsters
看到数据后突然有些似成相识，我是不是在哪里做过这题@cstdio。
可以预处理出来一张图，对于$i->j$的长度为$len(strj) - i,j重合的长度$。之后$f{i,j,k}$表示$i$到$j$走$k$条边的最短路，直接dp显然不行，可以发现这个是“符合结合律”的dp，直接倍增。
**BZOJ 2086: [Poi2010]Blocks
数据范围显然要求做到一次询问在$O(n)$完成。对于每个询问，处理一个sum数组，其中sum[i] = sum[i-1] + a[i] - K。接着对sum数组处理一个单调递减序列。之后从后往前，尝试求每个位置作为子序列结尾的最长长度。显然满足一段序列$[l,r]$符合条件的要求是$sum_r - sum_l \ge 0$。如果处理的过程中某个位置的sum值比之前（后面）某个值还要小，那么显然不可能成为答案。这样选择作为左端点的点在单调队列中的位置是只会向左移动的，用个指针维护左端点在单调队列中的位置即可。
6.25
BZOJ 2087: [Poi2010]Sheep
对着别人代码抄的，不过比想象中简单。预处理出每条边是否可行，即是否把分成两部分都是偶数。只关心是不是偶数就行了，这样一定是合法的。之后是一个dp，用$f{i,j}$表示从第$i$个点到第$j$个点连线时构成的方案数，答案为$f{1,n}$，转移方程如果$i$到$j$的连边合法，那么$f_{i,j} = sumk f{i,k}*f_{k,j}$，否则为0。
6.26
BZOJ 2088: [Poi2010]Teleportation
1到2的距离必须大于等于5，那么先假设最后求出来正确答案了，之后再做出来分层图，而且可以得结论：
之后统计答案就行，然后我讨论了这么多，代码似乎比别人长一些。不过1A，爽！
BZOJ 2091: [Poi2010]The Minima Game
先排序，之后记$f_i$表示第$i$个数以及之前的一个子局面的最优值。可以发现一个人如果选择的话一定选择后一段。可以反正其正确性：如果有空隙的话，后手可以补上，而且获得的分一定不低于先手，此时先手可以还获得剩余局面的最优分，但其实一开始可以直接选择获得剩余局面最优分的方案，再给后面一段带上去，这样一定不会更差。
之后dp方程为$fi = max(f{i-1}, ai - f{i-1})$，相当于枚举这个点属于新的一段或者归上一段。
感觉poi2010剩下的题要不然不想做要不然就是太神，不太想玩了，弃坑弃坑，以后有机会慢慢玩。