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.好开心.

迷之数据结构.我的想法比较简单,确定一个值b,对所有小于b的k建线段树维护,对大于b的k直接朴素找. 于是时间复杂度算起来比较迷. 试了一下发现b取20的时候能过.虽然还是跑得最慢的一个.无语喽.大概我不是正解.

白天讲课讲到的题。感觉比较有意思于是就去写了。然后这也是我超过于教授的题。感觉还是挺有意义的。 之前遇到过这个题。不过没有想出比较靠谱的方法。然后就用黑暗水过了。这回算是来对地方了。 做法比较简单。二分一个xo，看x=xo这条直线上有没有一部分被所有圆覆盖。如果有就ok。没有的话，如果有圆完全在它左或者它右，那么可以确定二分往哪边走或者无解。否则去随便找两个不相交的圆。如果它们在不同侧那就没有解了。在同一侧也可以确定方向。虽然我觉得没解这个地方需要再想想严格的证明。 不过反正填了2个点分之后终于写了道有意思的题，开心ing。 Historical Comments Unknown friend at 2016-01-18T08:27:34 @bzoj2289: “否则去随便找两个不相交的圆。如果它们在不同侧那就没有解了。” QAQ这里是有反例的……！ —- anonymous Unknown friend at 2016-01-18T08:27:34 @bzoj2289: “否则去随便找两个不相交的圆。如果它们在不同侧那就没有解了。” QAQ这里是有反例的……！ —- anonymous Unknown friend at 2016-01-18T22:40:55 @bzoj2289: 也许是吧= =表示高考解析几何比这玩意好玩多了ovo还有啊匿名是几个意思ovo —- laekov Unknown friend at 2016-01-18T22:40:55 @bzoj2289: 也许是吧= =表示高考解析几何比这玩意好玩多了ovo还有啊匿名是几个意思ovo —- laekov

又是idy开的坑。感觉回去要被他吊打致残。 树分治。最开始想用二分，然后直接去每个分治点上查询。这样的总复杂度是O(n*log3n)的。不过感觉常数比较小而且绝对省代码，只用二分不用数据结构。然后发现要输出所有的边。这个算法要用容斥一样的东西来减，根本搞不定。 于是向mhy学习。使用类似noi那个超级钢琴的思路，每次把最大的一条路径找出来，然后找它的替代品。树分治后，对于每一个树上的团，算出它的dfs序。默认一个点与dfs序在它前面的区间中最深的连边。这样就可以保证不重，也比较好写。然后用堆来维护。堆中一个点需要记录的信息是这个点的答案，线段树的根，左右端点，这个点到分治团的根的距离。然后每次找出一个最大的之后把它的区间再折成两半扔回堆里就好啦。 比较神的做法。感觉我自己是想不出来的。要是考场上遇到还真会出事呢。郁闷ing。

没有五笔好烦。 无语的期望题。AC第一页最长。 首先用像借教室一样的做法去求每个位置被覆盖了多少次。然后一个下降的序列需要求导再积回来。然后发现要加回来，这个东西是不能积的。于是坑了我好久。 最后期望就是∑1-Pim。其中Pi表示第i个点被任意一个区间覆盖的概率。 水过去啦。