动态规划数位dp数位dp是一种经典的dp模型，它的主要应用场景是与大整数及其数码有关的问题。这种问题比较好辨认，一般具有这几个特征： 要求统计满足一定条件的数的数量（即，最终目的为计数）； 这些条件经过转化后可以使用「数位」的思想去理解和判断； 输...

前缀和作用：快速求区间和 公式:$s[i]=s[i-1]+a[i]$,其中$s[i]$表示前$i$项的和 例：给定一个$n$项的数列$a$，共$m$次询问，每次询问给出两个数$l,r$，求区间$[l,r]$的和 分析：区间$[l,r]$的和...

凸包在平面上能包含所有给定点的最小凸多边形叫做凸包。可以理解为用一个橡皮筋围住所有给定点的形态。 凸包是周长最小的能围住所有点的凸多边形。 Andrew 算法 将点排序 x 为第一关键字，y 为第二关键字 从左向右维护可以得到凸包的上半部分（上凸包）...

位运算常用操作： $n*2^k$ :n<<k $n/2^k$:n>>k $2^k$:1<<k $n$在二进制下最后一位的数（奇偶）:n&1 $n$在二进制下的第$k$位： 先把第$k$位...

二分图 二分图：当一个图的顶点可以被分为两个集合，且任意一条边的两个端点属于不同集合时为二分图 即：相邻两个点位于不同集合内 一个图是二分图当且仅当图中不含有奇数环（长度为奇数的环） 染色法可以把二分图看作染色 用途：判断二分图 做法：循环，若一个...

Trie作用：高效地存储和查找字符串集合的数据结构 例：存储abcdef,abdef,aced,bcdf,bcff,cdaa,bcdc 存储：用$trie$数组记录节点，第一维为节点编号，大小为字符串总长度，第二维记录当前节点的对应字符的子节点，大...

KMP作用：字符串匹配 例：给定一个$m$位字符串$s$，一个$n$位模式串$p$，求出$p$在$s$中所有出现的位置的起始下标 分析： 暴力算法： 1234567891011char s[N],p[N];for(int i=1;i<=m;i+...

dp 技巧总结P1020 [NOIP1999 提高组] 导弹拦截以最长不下降子序列为例，时间复杂度为 $O(n \log n)$ 的一种算法： 记录每个长度的最长不下降子序列的结尾的最小值，可以发现有单调性，因此对于每个数二分查找可以接在哪一段后，更...

Dancing Links X(DLX)作用：优化搜索 题型： 精确覆盖 重复覆盖（配合IDA*） 前提：1的个数较少 存储：十字链表:每个数指向上下左右第一个元素 12int l[N],r[N],u[N],d[N],s[N],row[N],...

CYaRon 文档CYaRon 是一个可以帮助你快速生成随机数据的工具库，目标是实现帮您5分钟内生成一组测试数据。 使用CYaRon CYaRon 使用 Python 编写。在安装好 Python 的计算机上，下载 CYaRon 并放置在合适的目录下...