模板练习

木棉絮123 · 2024-10-23 16:55:57 · 个人记录

模板练习

CSP-S

数论

[x] 快速幂：5min7s
[x] 线性素数筛：8min40，不够熟练。

一些不是洛谷上的模板但也顺便练习一下的筛子（在线性筛的基础上练习）

[x] \sigma 函数，即因数个数线性筛：10min17s，也不够熟练
[x] \phi 函数筛：14min43s

如果实在写不出来可以~~背结论~~，\phi(mn)\phi(\gcd(m,n))=\phi(m)\phi(n)\gcd(m,n)

以上筛子的思路是先找质数，不是质数也要试着乘一下做标记，直到遇到其最小因子然后特殊处理（跟质数筛不一样）后 break;

[x] 线性逆元：9min45s，下次记得开 long long。
[x] exgcd：

显然当 b=1,a=0 时 x=gcd(a,b),y=0。

假设已经递归的找到了 bx'+(a \bmod b)y'=gcd(a,b) 的一组解。有 a \bmod b=a-b\times\Large\lfloor\frac{a}{b}\rfloor，代入，得到 bx'-b\lfloor\dfrac{a}{b}\rfloor y'+ay'=gcd(a,b)，分别提取公因子，得到 ay'+b(x'-\lfloor\dfrac{a}{b}\rfloor y')=gcd(a,b)。所以 x=y',y=(x'-\lfloor\dfrac{a}{b}\rfloor y')。Q.E.D

[x] Lucas定理：记得预处理阶乘

数据结构

[x] 线段树1：12min42s，中间写唐了但是还是在15分钟内写完了
[ ] 食物链（种类并查集）：
[ ] CDQ：

树论

[x] 倍增LCA：30min……奇耻大辱，明天再写一遍
[x] 树剖LCA：18min……不够熟练明天看一下细节
[x] 树链剖分：44min11s；记得给线段树赋初值时按点位置的映射赋值。

upd11/6：34min18s，一次过了。

[x] 树的直径：两次 DFS 即可

图论

[x] 强联通分量：20min33s

do
{
    id[stk[top]]=cps;
    instk[stk[top]]=0;
    col[cps]++;
    top--;
}while(stk[top+1]!=u);

注意到要判断的是刚处理的元素和栈顶是否相等。

[x] 点双：18min45s

点双有关点是不是搜索树的根节点的分讨好繁琐啊~~不像边双~~。记得弹栈的时候按 v 为栈顶弹，因为 u 是点双不能把它弹走了。

[x] 边双：23min56s

其实没比强联通分量慢多少~~以及调试花去不少时间~~。

当访问到一个点没有被访问过时，走的是树边，先判断其能否。所以可以

[ ] 缩点

字符串

[x] KMP：11min56s，真心不太熟……

NOIP

数论

[x] 快速幂：这个不可能不会吧。
[x] 线性素数筛：4mins32s
[ ] \sigma 函数，即因数个数线性筛：
[ ] \phi 函数筛：
[ ] 线性逆元：
[x] exgcd：之前模拟赛打过
[ ] Lucas定理：

数据结构

[x] 线段树1：10mins42s。笑死不说是谁线段树没有开四倍。
[x] 树状数组1：5mins21s。笑死不说是谁函数不加返回值类型。空间开小。
[ ] 食物链（种类并查集）：
[ ] CDQ：

树论

[ ] 倍增LCA：
[x] 树剖LCA：下面这个都打出来了显然会。注意前面比 top_u 的深度最后比 u 的深度。
[x] 树链剖分：46mins47s每日幽默
[x] 树的直径：两次 DFS 即可

图论

[ ] 强联通分量：15mins30s。笑死不说是谁点边不分。
[ ] 点双：
[ ] 边双：
[ ] 缩点

字符串

[ ] KMP：
[x] 字符串 hash：