bzoj

bzoj都3k道题了ovo hnoi的题好强. 这个题就建反图然后跑topsort就行了.每次选能选的里最大的扔进去.最后倒过来输出. 我也是猜的然后交上去居然是对的. 为什么呢?好神奇?

三维算几ovo给mhy和idy跪烂. 三维凸包算是一种比较简单的三维算几吧.首先有一些基本的公式比如算四个点的体积就是一个底*高.不过变成了一个面的法向量点乘另一个向量. 然后就用随机增量法每次替掉一些面就好了. 然后有一种可能是所有点都共面.这种时候就随机把一些点乱移动一下让它们形成一个高度和纸一样薄的凸包再来算就行了. 感觉也不是特别恶心啊ovo

在颓废了一天之后决定写一个题解.因为我觉得这题挺有意思. 我们需要转化一下式子.把原来的a,b改成A,B.设d=gcd(A,B),A=ad,B=bd. 那么(a+b)d | abd2,即(a+b)|ab*d. 又因为gcd(a,b)=1,所以(a+b)一定与a,b都互质.于是(a+b)|d. 设t*(a+b)=d.那么因为bd≤n,所以t(a+b)*b≤n.那么b是sqrt(n)级别的.且我们只需要统计三元组(a,b,t)的个数就行了. answer=∑b∑a(n/b)/(a+b)(gcd(a,b)=1)然后这个玩意看上去好像是个长得怪异一点的狄利克雷卷积啊. 于是就是要求[l, r]中与b互质的数的个数?这个玩意等于∑i|bu(i)*(r/i).然后发现可以把b分解质因数.而且只留下u不为0的.于是就能出奇迹辣好厉害ovo

好玩的数论题。想想发现可以像快速幂一样跑。然后就是思考如何转移优化。 发现模数比较奇怪。居然是fnt的模数ovo那就要用fft喽？可是这里是乘啊。木有关系喽，因为m是素数，所以它一定有原根。于是可以取原根的幂次，就变成加辣。 这种东西我自己当然想不出来ovo 同余系下的东西真有趣ovo

之前听说是异或高消？好神的感觉。 然后可以树形dp嘛！为啥网上题解这么误导ovo 就是f[u][i][j]表示u这个点有没有亮，有没有被按开关。完了嘛。 无语了辣。

比较神奇的数学题.首先你得听说过一个东西叫Mertens函数.于是你可以找到一篇论文.然后你发现它是英文的.试图理解了很久没有成功. 然后终于有人良心贴出了一个blog.这回懂辣开心ovo 其实就是那一个公式:F(n) = ∑一堆约数 + ∑k=2nF([n/k]) 然后发现mu和phi的左边一堆都是可以O(1)算的辣.右边强行记搜可以做到O(n2/3)的辣. 然后手写个hash啥的就能跑得飞快的辣.

比较神奇的dp题.其实也不能算dp辣ovo 有一个神奇的事情是,塔的高度与底层的宽度是负相关的. 所以就变成了问塔底最窄的时候塔有多高. 用f[i]来表示用从第i个砖块到第n个砖块搭起来的塔的最窄底层宽度.用s[i]来表示宽度的前缀和,然后得到一个式子: f[i] = min(s[j-1]) - s[i - 1] (f[j] ≤ s[j - 1] - s[i - 1], j > i) s是单调的.看上去很像是dp呢. 然后就变成了求s[j - 1] - f[j] ≥ s[i - 1]时的最大的s[j - 1].于是开单调队列搞吧ovo

自从会了sam,似乎已经不知道acam该怎么写了ovo 这个题就是强行用ac自动机记录匹配到某个位置的时候的状态.然后如果走到一个终态的话就可以强行删掉一段,然后把当前状态变为上一个状态. 最初没有想到有可能会连续删除,于是挂了很久.最后用官网上的数据还是过不了第9个点,然后交bzoj居然过了.好神奇.我猜想是迅雷挂了hhh毕竟usaco的数据用wget根本搞不下来好伤心. 所以我还是太弱ovo

idy居然会开1d-1d这个坑ovo之前听讲的时候也只是觉得很神奇,没有真正手写过,所以不明觉厉. 这个东西需要实际问题实际分析.总的思路就是利用决策的单调性. 对于这题,设f(x)=sqrt(x-j)+a[j].那么显然它是凸的.然后若干个它还可以拼成一个奇怪的凸壳状的分段函数.然后我们要取每段的极值.怎么有种半平面交的变形的感觉. 然后发现每次插入的函数的j单增,既x单增.于是只需要开一个双端出的队列就好了.然后每次二分一下两个函数的交的x坐标.其它时候可以完全单调性搞定. 然后算的时候用double会方便很多. 似乎很有意思啊hhh

明明就是usaco的水题嘛有啥好写的ovo只是想mark一下刚自己想出来的非递归的正常版的tarjan. 这题思路灰常简单.就tarjan缩scc然后在dag上找一下最长路就完了. 然后就是非递归的tarjan.考虑平时用栈建树的dfs序的方法,既把一个点的所有儿子扔进栈再递归.然而这个方法不能直接套进tarjan的dfs.因为它的一个儿子可能会对另一个儿子造成影响,有可能甚至直接改变dfs的顺序. 所以如果更新的时候一个点连出去的点还没有被访问,那么不管它是否已经在栈里,都再把它扔进去一次.这样就保证了访问的顺序.而在再次访问的时候只要判断一下是否已经访问就行了. 然后对于两个更新,首先如果直接low[p]=dfn[p]的话是不需要专门去用dfn来取min的.然后考虑倒着更新.每个点被退visit栈的时候去更新它的父亲就好.因为它的父亲一定还没有出栈.然后如果是只更新不递归那就直接访问. 这样的话空间复杂度会变成O(n+m),不过妈妈再也不用担心我暴栈了.而这个方法也比强行模拟系统栈要方便一些. 开心ovo