CF494D Birthday 题意 一个1为根的带边权有根树，每次询问给定两个点 \(u,v\) 求 \(\sum_{x\in S(v)} d(u,x)^2-\sum_{x\not\in S(v)}d(u,x)^2\) 其中 \(d(u,v)\) 表示 \(u,v\) 简单路径长度， \(S(u)\) 表示 \(u\) 的子树内点的集合。 思路 考虑 \(u\) 在 \(v\)...

CF833B-线段树优化DP 题意 将一个长为\(n\)的序列分成\(k\)段，每段贡献为其中不同数字的个数，求最大贡献和。\(n\leq 35000,k\leq 50\)。 思路 此处感谢@gxy001 聚铑的精彩讲解 先考虑暴力DP，可以想到一个时空复杂度\(O(n^2k)\)的方法，即记录前i个数字分成了j段。我们现在来思考几个问题来优化这个操作： 对于一个数字，它对那...

CF896D Nephren Runs a Cinema 题意 售票员最开始没有纸币，每次来一个顾客可以给她一张、拿走她一张或不操作。求出不出现中途没钱给的情况 \(n\) 名顾客后剩余钱数在 \(l\sim r\) 的方案数。 思路 这是我们一道模拟赛题。 解法 1：套路组合计数。先不考虑不操作的顾客，那么就相当于是求二维平面不过一条直线到达一点的方案数。直接枚举操作顾客数，...

我之前一直记的迪杰斯特拉的翻译导致我把 dijkstra 写成了 dijstra 或者 dijskra…… 我以后叫她迪杰克斯歘！ dijkstra 是用来在有向图或者无向图中寻找任意两个点的最小距离的算法。但是无法处理带负环的图和求最长路。 dijkstra 的核心思想是由已找到的最短路的点集每次扩展一个点的最短路。 dis 数组代表由起点到其他点的最短路，初始化其为 \(I...

非全面讲解，仅供记录笔记 Dirichlet卷积 \[(f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d})\] \[\varepsilon =\mu \ast 1 \iff \varepsilon(n) = \sum_{d\mid n} \mu(d)\] 其中\(\varepsilon\)卷任何函数等于其函数本身。 莫比乌斯函数\(\...

GCD SUM 求 \[ \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) \] 将原式变换得到 \[ \sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1] \] 别着急莫比乌斯反演，我们知道 \[ \varph...

Guass消元 约旦·高斯消元法 求线性方程组 我们用一个\(n*(n+1)\)的矩阵存储线性方程组各项系数和零次项系数。 每一次找到一个未知数系数最大的方程，交换当前行方程和该方程，并将其他行该未知数的系数化为零。 重复n次即可。 最后第\(a[i][i]\)个数就是第i个未知数的系数，\(a[i][n+1]\)是等式右侧的数，用后者除以前者即可。 当化第i个方程时...

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。 问题：求 a 字符串与 b 字符串中子串相同的串首位置。 暴力就不说了，设 a 长 \(m\)，b 长 \(n\)，每次枚举比对每个字符，复杂度 \(O(nm)\)。 KMP 主要思想：如果一个字符串的子...

LCT维护一个森林，即把每个节点用splay维护，可以进行许多操作： 查询、修改链上的信息 随意指定原树的根（即换根） 动态连边、删边 合并两棵树、分离一棵树 动态维护连通性 等 主要性质 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。 每个节点仅包含于一个splay中。 边分为实边和虚边...

P1040 加分二叉树 \(n\) 很小，可以树形 dp 或者区间 dp 。 设 f[i][j] 为从 \(i\) 到 \(j\) 的最大加分值，则有 f[i][j]=max(f[i][k-1]*f[k+1][j]+f[k][k])。 有一个小技巧，将 f[i][i-1] 全部设置为 1，这样的话搜索到叶子就也可以按照通式 dp 了。 对于输出前序遍历（根，左树，右树）我们再...