博客
归档
友链
关于
博客
归档
友链
关于
BZOJ 3648 寝室管理
这题其实就是点分治的一个扩展。
2020-01-10
阅读全文
BZOJ 3451 Tyvj1953 Normal
此题恶臭,心态被搞了。 考虑SolveSolveSolve算法,每个点有且仅有一次被当做树的根,于是可以将整个算法的期望时间复杂度变成每个点的树的期望大小之和。 想到这里,你还得有一个更加恶臭的想法,考虑如何表示每个点的树的期望大小,记p[i][j]p[i][j]p[i][j]为jjj在iii子树里面的概率。 那么iii子树的期望大小即是∑j!=ip[i][j]\sum _{j!=i} p[...
2019-10-09
阅读全文
P4178 Tree
传送门 考虑点分治,Calc()Calc()Calc()函数如何实现呢?,我们把uuu子树内以根节点为端点的链的长度全部存到一个栈里面,将栈排一个序,令f(i)f(i)f(i)为使得stk[i]+stk[j]≤kstk[i]+stk[j] \le kstk[i]+stk[j]≤k的最小的jjj,考虑把这个式子转换成stk[j]≤k−stk[i]stk[j] \le k-stk[i]stk[j...
2019-07-22
阅读全文
P2634 [国家集训队]聪聪可可
传送门 一道非常模板的点分治,核心函数是Calc()Calc()Calc(),返回当前子树中,经过根节点的链有多少条长度是333的倍数,实现时,记录f0,f1,f2f_0,f_1,f_2f0,f1,f2,分别代表有多少条以根节点为端点的链长度mod 3=0,1,2\mod 3=0,1,2mod3=0,1,2,最后乘法原理相乘即可。 注意容斥原理,要减去两条链共用一条根节点发出的边的情...
2019-07-22
阅读全文