gui vfk. 在hdsdfz听讲过的题. 可持久化seg tree优化建边.好像一句话就能说清楚啊. 然后证明了我的网络流的姿势严重不科学ovo 然后bzoj上样例居然是图片ovo于是附上手打的样例ovo 10 0 1 7 3 9 2 7 4 0 9 10 5 1 0 4 2 10 2 7 9 1 5 7 2 6 3 5 3 6 2 6 6 4 1 8 1 6 1 6 0 6 5 2 2 5 0 9 3 5 1 3 0 2 5 5 6 7 1 1 2

有点像xyz在wc的时候讲的动态图连通性问题.不过这个看上去要水些啊. 考虑建一棵生成树,那么所有剩余的边覆盖了的边就不是桥.如果没有被覆盖就是桥. 于是这个题可以倒过来,支持加边和查询两点间没有被覆盖的边数. 似乎挺水. 完了.

下午写的东西被奇妙地吞掉了ovo 最小直径生成树,一定不要用sort,否则会tle. 首先考虑一个绝对中心的概念.既在生成树上它是所有直径的严格中心.它有可能在点上,也有可能在边上. 于是我们枚举边,试图让这个绝对中心在这条边上.那么每个点都选择到这条边的最短路树来生成.如果两个端点的最长链的差距不是很大,那么就有可能在这条边上找到最小直径生成树的绝对中心. 考虑绝对中心对一个端点的距离,会对每个点形成一个峰形的函数.要找的答案就在相邻两个峰之间.于是可以利用两边直线k相同,把b排序之后直接做.总复杂度O(n3). 然后如果每个边强行排序只会多个log,但是会tle.

考试的时候do big die去刷bzoj.大概下午会hug zero. sam的第二题.其实这个玩意是应该用sa做的,不过现在我觉得sa没有sam简单.虽然sam的构造和性质还是一团大雾. 这个题可以做出原串的后缀树,然后在上面dp一下.每个点对答案的贡献为任意两个不在同一子树的终态对数*深度. 然后倒过来建sam,它的parent树就是原串的后缀树.虽然我还没有成功理解这个东西. 然后坑了一会的一件事情是新建的nq节点的right集合为空.因为它只是一个扩展点,但是不是一个接受态ovo 我还是太弱啊怎么办.

idy又开坑辣,虽然是个无聊的无聊题. 考虑每条路径会被哪些路径包含.那条路径的两个端点一定是在条路径的两个端点的子树上.(如果这两个点有祖先关系,那么需要重新makeroot一下) 当然我不是说要用Lct.直接用可持久化线段树在dfs序上把路径存下来就完了.

好难得自己去开坑hhhhh 其实之前看过做法,觉得有点麻烦.于是拖到现在.然后荣登最慢yeah.不知道那些又短又快的东西是怎么来的.肯定和我不是一个写法的啦. 我的做法是把序列每b个分成一块.对于同一块,直接b2求内部有三个点或者两个点的等差三元组的数量. 对于分别在3块的,对每块把两边的所有东西卷积一次来统计. 其实也没啥技术含量ovo

谁说最小乘积生成树是取log了ovo题意都不一样好么. 首先这个东西一定在一个像是下凸壳一样的东西上.其实是一个反比例函数的k的最小值. 把x和y的和看作坐标,求在(x0,y0)与(x1,y1)中间的一个点,为了平均分配,要取那个三角形最大,于是可以用叉积弄出一个式子来当作x和y的系数,这样就可以直接kruskal求最小生成树了. 如果求出来的点在这个线段上,那这个区间就不用再找了.否则还得去两边继续递归. 然后最初的左端点和右端点就取x的最小生成树和y的最小生成树就好了. 这个时间复杂度似乎还是没有保证啊.有点像自适应simpson的感觉,虽然这个肯定是精确的.然后跑起来也比较快.有意思. 这个玩意还是比较好写的.虽然中间kruskal把0打成1,看了半天ovo

比较好想的dfs容斥，然后二分答案。 就只用dfs不超过sqrt(n)的素数的平方和。

idy又开坑辣。 mobius反演题么么哒。强行sqrt(n)的询问。 于是推一下式子。 answer = ∑i∑j1 (gcd(i, j) = 1) = ∑_p∑_gu(g) * (n/(p*g)) * (m/(p*g)) 然后把p和g合起来设为v。 h(v) = ∑ u(v) (v = x/p) 然后发现h(v)函数是很好推的。 h(px) = (x % p == 0) ? (u(x)) : (u(x) - h(x)) 然后就搞定啦orz.

去年的省选题.之前知道了是找负环.不过一直感觉好迷是个坑.最近又想了想发现也不是很麻烦. 当年省选的时候完全对比例题无感啊.经过一年之后终于觉悟了一点东西. 考虑一个网络流,每条边的流量上限是inf,只有从源出来的边不是.然后如果进行一次正向增广会使代价增加b+d,如果进行一次逆向增广的话代价会增加a-d,前提是有流量.于是只要二分一个答案,看下存不存在一个负环来增广就好了. 然后一个spfa就迷之拿了bzoj的rank1.好开心.