iinattr

2022年7月24日

$$\huge{今天有些累了，明天再开始努力吧!}$$

GarsiaWachs

2022年7月24日

GarsiaWachs算法流程1.找到满足 $q_{k-1} \lt q_{k+1}q$的最小下标 kk2.找到满足$q_{j-1} \gt q_{k-1} + q_kq$的最大 $j \lt kj<k$3.从列表中清除$q_{k-1}, q_kq$4.在$q_{j-1}q$ 之后插入 ...

2022年7月24日

（今天本想讲LCT 但本人TCL 所以大概率讲完会的还是会不会的还是不会所以将点简单的巨神们可以去切题了）引入想必大家都已经十分熟悉二叉搜索树了它是很好用的数据结构但二叉搜索树仍存在问题即当插入数据单调时搜索树退化成一条链这时我们使用一种称为平衡树的数据结构来优化它想必大 ...

2022年7月24日

首先应该清楚三点 1 endpos数组只是我们为了说明后缀自动机性质的辅助数组我们在建造自动机时并不需要知道endpos是啥只需要明确建出的自动机满足endpos即可 2 利用parent树说明后缀自动机只是为了证明它的某些性质后缀自动机和parent树或许有半毛钱关系 3 后缀 ...

2022年7月24日

澡堂游记 DAY1-1概要5.1日上午内容主要为序列、区间dp 5.1日下午主要内容为背包动归概论动态规划本质上是记忆化搜索即将搜索过程中的遇到的已搜索结果保存并转移因省去递归结构减少常数时间复杂度所以核心是如何标记并存储状态并从较小规模答案得到较大规模答案例题1.求长度为 n ...

2022年7月24日

5月2日主要内容为树形dp与状压dp ##感觉今天讲的也没什么可写的qwq但是插头dp我是真没听懂在此做一些整理本篇依例题https://www.luogu.com.cn/problem/P5056【模板】插头dp讲解插头dp是为了解决网格链接性问题的一种算法由某thu爷发明 ##要 ...

2022年7月24日

5.3日以考试为主 T1签小 D 对细胞分裂很感兴趣，现在小 D 发现了一种魔法细胞，一个魔法细胞在第二天会分裂出 x−1 个新的细胞（同时原细胞依然存在）。初始容器中有 0 个魔法细胞，现在小 D 会在第 i 天往容器中加入 i 个魔法细胞，现在小 D 想知道，在第 n 天，培养皿中会有 ...

2022年7月24日

s洛谷网校SX2数论一知识整理1 取整函数的性质1.1对于正整数n，1到n中d的倍数有$\lfloor\frac n d\rfloor$个显而易见 1.2对于任意x与正整数a,b$\lfloor\frac {\lfloor\frac x b\rfloor} a\rfloor= ...

2022年7月24日

万字长文·三维偏序/cdq分治cdq分治静态区间问题cdq分治是一种解决区间统计问题的常用方法点分治相当于吧cdq分治挪到树上 cdq分治即把一个序列分为两部分区间统计的量分为跨中点的左边的右边的（一下所说统计均指在区间中点）先递归处理左边的和右边的然后再寻找某种$O ...

2022年7月24日

万字长文·动态树分治/动态动态规划/ddp入门经典这东西好像有人叫它ddp 其实应该是动态树上dp吧这类题往往是一个画风正常的树上dp问题加上修改并且修改次数极多注意到树上dp往往一个点权的修改只会更改它到根的路径上的答案所以我们可以每次在根的路径上求解可通过一 ...