DDP 学习笔记
DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。 我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独...
DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。 我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独...
先记个模板，以后再写。 题目链接#include <algorithm> #include <iostream> #include <cstring> #include <climits> #include <cstdlib> #include <cstdio> #include <vector> #incl...
定义维基百科 - 后缀数组 让我们来看一下 wiki 上的定义： 在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。 令字符串 $ S=S[1]S[2]...S[n]$， $S[i,j]$ 表示 $S$ 的子字符串，下标从 $ i$ 到 $ j$。$S$ 的后缀数组 $ A ...
本文使用符号 $\vec{a_i}$ 来表示向量。定义基 是线性代数中的一个概念，它是描述，刻画线性空间的一个工具。在 OI 中经常和异或运算扯上关系。前置芝士向量空间向量空间 - 维基百科定义 $(F,V,+,\cdot)$ 为向量空间，其中 $F$ 为域，$V$ 是向量，$+$ 是向量乘法，$\cdot$ 是标量乘法，并且运算满足 8 条公理。（摘自维基百科）线性无关线性无关 - 维基百...