抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

动态 DP 学习笔记

前言 动态 dp 一般用来解决树上的 dp 问题,同时需要支持修改点权/边权的操作。 前置知识:矩阵乘法,树链剖分 模板题 题意 洛谷 P4719 【模板】动态 DP 带修改点权的树上最大独立集, n 点, m 次操作 不带修改操作 没有上司的舞会嘛不就是。令 f_{i,0} 表示 i 子树内不选 i...
OInotes

Lucas 定理

前言 本文主要介绍了 Lucas 定理及其扩展,并附以若干道相关习题。 公式可能偏多,但是只要静下心来慢慢读还剩可以读得懂的 qwq。 本文用到了的前置知识: 简单的排列组合 普及~提高的数论知识 二项式定理 简单的生成函数知识 乘法逆元 中国剩余定理(CRT) 欧拉定理(可选,习题涉及) 整除分块(习题涉及其思想) 普通 Lucas(模数为质数) 问题描述 求 \binom n m\...
OInotes

分块相关

基本思想 将序列上的元素分成若干个块,然后在这些块上面预处理信息从而优化暴力。 一般来说,对于一段序列,将其分块后,处理区间操作就考虑将整块的整块处理,两端的直接暴力修改或查询。 一般地,做分块题时可以考虑预处理出某元素所在块的编号 bl[i],以及一些其他的按照整块预处理的信息。 12int a[maxn], bl[maxn], tag[maxn], block; 1234int n = ...
OInotes

DP 优化合集

斜率优化 模板题 P3195 [HNOI2008]玩具装箱 题意:将一段序列 c_i 分成若干段,每一段的代价为 (j-i+\sum_{k=i}^jc_k-L)^2 ,求最小总代价。 不难发现状态转移方程为 f_i=\min_{j<i}\lbrac...
OInotes

后缀数组

基础 定义 本文的字符串下标从 1 开始。“后缀 i ”指代从第 i 个字母开始的后缀。 后缀数组由两个数组构成,一个是 sa[],一个是 rk[]。 sa[i] 表示的是后缀排名后第 i 小的后缀的编号,rk[i] 表示的是后缀 i 的排名。 即 sa 告诉我们排第几的是谁,rk 告诉我们谁排第几。 不...
OInotes

Link-Cut Tree 学习笔记

参考资料 https://www.zybuluo.com/xzyxzy/note/1027479 https://www.cnblogs.com/candy99/p/6271344.html https://www.cnblogs.com/flashhu/p/8324551.html https://oi-wiki.org/ds/lct/ 鸣谢以上博客的作者们。 简介 Link/Cut Tr...
OInotes

树上问题笔记(点分治,dsu,长链剖分)

点分治 概述 用来处理树上路径问题,对于一棵树,指定一个根 rt 之后,所有的路径无非分为两类: 经过根的路径 不经过根的路径 当我们处理完所有经过根的路径之后,删除根,不难发现可以这样子对于每棵子树继续分治下去,所有的路径都能划归到第一种情况。 算法的流程: 找到当前树的重心,设为根节点 处理所有经过根的路径 删除根节点 对于所有的子树,重复上述步骤 每次处...
OInotes

matrix-tree

主要用于解决生成树计数相关问题。 前置知识:行列式 定义一个矩阵 \boldsymbol A 的行列式 \det\boldsymbol A 为 \det \boldsymbol A = \sum_{P\text{ is a permutation}} (-1)^{\operatorname{sgn}(P)}\prod_{i = 1}a_...
OInotes

多项式合集

拉格朗日插值 问题背景 给出 n 个点 (x_i,y_i) ,令这 n 个点确定的多项式为 L(x) ,求 L(k)\bmod 998244353 的值。 ...
OInotes

线段树进阶应用

维护较复杂信息 一般在维护较复杂信息的时候,为了代码的简介易懂,一般将线段树定义为一个结构体: 12345struct node{ int val, val2, tag;//........这里放信息} t[maxn << 2]; 然后可以重载加号,这样子方便需要返回一个节点的 query() 函数。 区间最大连续子段和 维护最大前缀和,后缀和和子段和。合并时注意跨越端点的...
OInotes




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme