bzoj

rausen大爷太强辣! 嗯看到这个东西,咦,直线某一边的点的权值和?kd-tree上上上. 于是就开敲kd-tree.敲到一半弃emacs换vim. 然后就wa了.然后发现double的精度太高了ovoovo 于是rausen跑得好快啊.

之前感觉是sg函数.不过不会.在wulala神犇的指点下找来题解看了一下.太神辣.自己肯定想不出来… 设以点u为根的子树的局面的sg值为sgu.设以u为根的子树中先手先hack掉v后的sg函数为gu,v. 那么gu,v = f[v] xor ∑ fu到v路径上所有点的非主干儿子. 然后fu = mex{gu,v} 这个转移得转移是O(n2)的样子吧. 然后发现某棵子树的g其实每次都是异或了一个相同的值.而且会合并. 咦可以用trie来优化一下.打下标记啥的.然后根据主席的论文这个东西是O(log n)的?虽然感觉复杂度证明没有说清楚啊ovoovo 然后就在trie树标记上卡了好久啊火冒三丈ing

上课题.之前只有5个人过5个人交.我成功地拉低了这题的通过率yeah. 其实就是考虑Si序列走完之后对x和y的贡献以及对方向的改变就好了. 比较烦的是中间那一个东西是哪个方向.然后发现如果在上一层的左边就是1否则是0.和更上层没有关系不能直接异或往下传. 代码越写越丑了TAT

还不错的题ovoovo 发现其实要求x的二进制表示中没有相邻的1就行了. 第一问水水的数位dp.从未写得如此愉快. 第二问就是前面的g.然后发现是fib数列.矩阵快速幂搞定.

最近总是被一些水题虐智商啊…怎么回事Ovo 无脑地状压dp一下就好了. 每个物品分开dp,这样可以降到O(2m * n * m)级别. 我还是太弱了.

naive之laekov系列.这么水的题还想了几天ovoovo 这个距离,咦,不是传统的距离啊.等距线是十字形的. 思考一下.发现,分别按x和y排序,把相邻的两点之间连边,dijkstra,完了. 为啥啊?因为这样建图可以保证任意两点的最短路一定能在图上跑出来. 毕竟我太弱,ovoovo

mhy大爷多久之前开的坑啊ovo 这题的思路比较神.点分+fft.两个点会产生的贡献是1/(dist + 1).于是要知道长度为多少的链有多少条. 利用树分可以将∑深度降到O(n*log n)的级别.原因很明显啊. 然后就用fft来求就好喽.反正是double也懒得用数论了.然后找了wyf的程序随便就拍出一组末位不等,也没用long double.居然能过太神奇了. 总复杂度O(n*log2n).然后莫名其妙就拿了rank1好开心啊.

simplex第一题.这玩意是不是拖得太久了啊ovo记得初中买算导的时候就想学它… simplex的思路其实比较简单.先找标号最小的目标函数中系数为正的变量.选择约束最紧的限制条件.通过这个条件来换元.直到消光. 感觉好神奇啊然而为啥啊ovoovo 然而线性规划的条件是≤而求的是目标函数的max.和这题的式子刚好相反啊. 然后神奇的东西是,对偶.强行把矩阵转制,然后把大小于符号取反,求出来的目标式max就是原问题的min.为啥啊Ovo算导上的证明也能看? 然后就是一个类似于高消的东西.据说跑得比较快. 另一个神奇的事情是在这道题里面因为奇怪的系数所以所有变量的系数都是+-1或者0.于是可以不用double强行写.开心. 然后网上的某份代码似乎会把无解的情况搞错hah 然而第一遍自己也有地方写丑… 这种东西还要再练练.

mhy写此题写了良久啊然后T啊T,T啊T.然后我去翻了一下seter的博客.结合他的东西yy出一种比较优越的做法. 如果我是出数据的,我会出两种数据,菊花图和链. 如果是菊花图,直接朴素ovoovo如果是链,可以以每个叶子节点为根建一次可持久化线段树. 如果是链上长出了一团菊花… how to 结合? 不停地删叶子.如果删到某层时叶子足够少了,那就建可持久化线段树去. 对于询问,有若干种情况. 标记每个根里离得很近的点. 如果两个中有一个被标记过,那么直接以这个根求另一个的答案,然后朴素查找近的这个点到根的答案. 如果两个点都没有被删 ,那一定有至少一个根可以使得这条链的两个端点有祖先关系.这样的话直接用可持久化线段树求解. 好像完了?然后wa了ovoovo 还有一种情况是某个点被删了,但是删之后它是接在树枝上的! 于是它离根很远,还不一定有能搞出祖先关系的解. 于是先爬行到没被删的地方,看两个端点是否在同一棵被删的叶子树上. 如果是就朴素了. 如果不是的话,先求没被删的这一段,再朴素被删的一段. 终于完辣. 从来没写过这种代码.感觉自己萌萌哒.

mhy开了道找规律oovovo 打表找规律良久.最后还是没有O(1)的规律.倒是发现有点像分形,有个log级别的递推式. 怎么来的啊好神奇啊ovoovo