Light up the sky - good job

一月 01, 2022

dsu on tree前置知识 dfs建树轻重链剖分核心思想对于以 u 为根的子树 ①. 先统计它轻子树(轻儿子为根的子树)的答案，统计完后删...

十二月 01, 2021

KMP算法前提介绍KMP算法是一种看模式串在主串中出现次数的优化算法复杂度为O（n+m）这个算法理解了不难，不理解只背模板早晚会挂，而且容易忘，建议从...

十二月 01, 2021

四边形不等式定义对于形如 f_{i,j}=min(f_{i,k}+f_{k+1,j})+s[i][j];的式子，若s满足四边形不等式，则 w_{i,...

十二月 01, 2021

数位DP数位DP问题关键：一般会问某一个区间里面满足某种性质的数的个数技巧一： $[x,y]$ = $f(y)-f(x-1)$ 类似前缀和的方式技巧二...

十二月 01, 2021

矩阵矩阵的定义：一个n*m的矩阵可以看作是一个二维数组设A是$n m$矩阵，B是 $m p$矩阵则C就是$n * p$ 矩阵并且 \sum ...

十二月 01, 2021

莫比乌斯反演例题原理： f(x)=\sum_{d\mid x} g(d) \iff g(x)=\sum_{d\mid x} \mu(d)f(\dfrac...

十一月 03, 2021

树链剖分要求已知一棵包含 N 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从$x$到$y$结点最短路径...

十一月 02, 2021

AC自动机AC 自动机可以理解为在多个串上的 KMP，利用 Trie 树来维护这些串，nxt 数组变为 fail 指针。 fail 指针的构造思想如下： ...

十一月 01, 2021

AC自动机概念描述：AC自动机：（一种可以自动AC的机器），指的是一个文本串和若干个模式串看看这些模式串是否在文本串上被匹配（不需要管有几次，只要出现过就...