考前ykz和我说有我做过的题，点开四道一道都没见过。。。人与人之间的信任呢？
B.BZOJ3008: 象棋
在湖南的时候讲过一个类似的马的移动的问题，我好想只记得当时的结论是 任意时刻两匹马不能再同样一个位置 这个条件是可以忽略的
感性的想起来应该也是正确的。于是就是裸的费用流了
但是这题非得KM才能满分。。。算了，不想学KM了 90分走人 
C.BZOJ3004: 吊灯
首先块的大小必须是n个约数，然后我们的问题就变成了如何判断一个数m能否完整分割这棵树。
我仔细想了想是这样想的。我们首先把所有约数放入一个双向链表里（是为了能够在一个数不合法的时候立即删除而之后就不用再循环他了）
然后对于x所在的子树，它的儿子y，如果s[y]%m!=0,那么剩下的s[y]%m一定要和x分在一个块，所以我们只要求sigma(s[y]%m)然后判断是否>m就可以了。
如果<m实际上作为的fa[x]的s[y]%m。
这样就可以水过90分233 当然最坏复杂度其实是O（10*n√n）的，当然无法通过所有测试数据。（当一条链的时候复杂度达到最大，当然n的约数个数要足够多）
然后我数组开小只拿了80分QAQ
正解其实是推了一个结论。
m能成为解的充要条件是sigma[s[x]%m==0]=n/m
首先不可能有sigma[s[x]%m==0]>n/m，因为每一个s[x]%m==0，都对应着x所在的一个块，而这些块肯定只包含它的子树内的一些点+x，所以是不可能重复的。这样块数*m>n，矛盾。
然后如果sigma[s[x]%m==0]<n/m，那么如果它能够完全覆盖这棵树，就必定有一块>m了。这也与题意不符。
这样复杂度其实是O（10*n）的，可以通过全部的测试数据。
（其实在想到如何判定m是否合法的时候就应该想到复杂度必须是O（n/m）才能保证总的复杂度是O（n）。当然这都是后话了，这种结论还是不容易想到来推的）
另外还发现就是统计子树大小这个问题，我用dfs和直接for循环写了两个，然后前者10s+，后者4s。第一次发现差这么多
A.3007: 拯救小云公主
其实以前看过题面，想的是二分ans，然后把被boss控制的点抠掉，然后看看（1,1）到（row，line）是否联通。
然后发现好难判断啊，而且枚举每个boss，再枚举他身边的店就n^3了。
于是考试的时候就弃疗了，最后也没时间打暴力。
膜拜了题解发现好神啊!先Orz！
我们发现这个棋盘row,line<=3W,而n<=3000.
也就是说boss属于少数，而我们所关注的好点却是非常多的。这使得什么算法都跑不动。
那我们反过来考虑，如何安排ans是的boss能够阻挡住英雄呢？不妨设x是这个最小的能够阻挡住英雄的ans，那么x减去一个很小的值就阻挡不了。
那我们就可以认为这就是答案了。（反正保留两位之后一样）
那我们就把题目转化成了求一个最小的x，使得boss能够阻挡英雄。阻挡无非就是把（1,1）和（row，line）割开（这让我们想到了狼抓兔子）
具体的建图方法就不说了。总之转化到这里就成了一个很水的问题了。关键在于前面的思路。
算了还是说说吧，令g[i][j]表示i到j的距离，然后我们要判断是否存在从下边/右边到上边/左边的一条路径，使得最大值最小。
这是经典模型，可以二分之后spfa。也可以直接spfa。然后就搞完了
D.3009: 集合
这题我不会做，但AC还是没有问题的。
这题正解是一坨。。。考虑如果是一棵树的话，就可以用bfs序（好高大上啊，原来只听说过dfs序）+线段树维护，因为每个点所连出来的边都是一段连续的区间，然后我们可以用一个指标比如说两种颜色的乘积来表示这条边属于哪个集合，然后就可以线段树区间修改+最值查询了。
然后题目中又说任意两点间的不相交路径不超过3条，然后balabala就可以推出这个图被分成了3棵生成树（其实这里我还不懂什么意思。。。）
然后用3棵树来维护。。。
当然我这么傻逼怎么会写这么高大上的东西，dzy大爷教导我：暴力把边排序，然后每次从小到大扫就可以过。。。
然后就AC了
评论 (0)
