最短路算法详解
最短路 图论基础知识——有向图、无向图 有向图： 即单向边，ij有边不一定满足ji有边 无向图： 即双向边，ij有边一定满足ji有边 主要是根据题目要求来建单向边还是双向边 如果是双向边，我们只需要把他拆成ij和ji的两条单向边就行 无论是
二分图的一点点建模例题
全体集合https://ac.nowcoder.com/acm/contest/11220/F 题目描述： 给出 n 个点 m条边 的无向图，给出 k 个点，这 k 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），
启发式搜索 ：A*算法详解
A\算法 A\算法,AStar算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。 算法中的距离估算值与实际值越接近，最终搜索速度越快。 回顾：BFS、Dijkstra 对于求两个点之间的最短路 普通的BF
有依赖的背包问题「树上分组背包」
有依赖的背包问题 题目描述： n个物品，容量为m,物品之间有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大 求最大价值 思路： 如果考虑每个子
差分约束系统详解
差分约束系统 什么是差分约束系统 差分约束系统指的是解决如下的多元一次不等式组的一种方法，其中y1,y2...yn是常数，叫做差分的原因是多元一次不等式组的每一个不等式都是关于两个自变量做差的关系 !\公式\https://www.zhih
什么是SPFA？SPFA怎么判负环？怎么判正环？
什么是SPFA SPFA是在BellmanFord的基础上进行的一种优化，BellmanFord的思路是进行n1次循环，每次循环都遍历每一条边来更新最短路，复杂度是 On\m，不难发现每次遍历边uv去更新disv时，当且仅当disu被更新过
尺取法、双指针
模版 Subsequencehttp://poj.org/problem?id=3061 题目描述： 求一个子区间的数字和大于等于m的区间长度的最小值 洛谷 p1638 逛画展https://www.luogu.org/problemnew
并查集加速区间修改例题
E Packing Under Range Regulationshttps://atcoder.jp/contests/abc214/tasks/abc214e 题目描述： n个球，每个球只能放在l,r的任意一个盒子中，每个盒子只能放一个
树形dp
树形dp 树形dp，即在树上进行的 dp。由于树固有的递归性质，树形 DP 一般都是用dfs来递归进行的。 主要的思路就是计算子树，然后合并 模版大概是这样的 题型一般分为两种：选择节点类、树形背包类 选择节点类 选择节点式的题，首先前提条
势能线段树
板子 势能线段树模板题一https://ac.nowcoder.com/acm/contest/19917/D 题目描述： 对区间进行开根号及向下取整操作 求区间和 思路： 所有数字开根号的势能上限都是6，也就是说最多开6次，就会变成1，然
01trie树
01trie树顾名思义，是trie的一种特殊形式，树上只有0和1两种值，主要用于解决点与点甚至是区间的异或和最大、最小问题。 建树插入数字的时候和普通的trie树一模一样，而求一个数x与树上所有数的异或最大值时主要是用到贪心与二进制的思想：
前缀和的n个神奇操作
前情回顾 前缀和的基础用法戳这里—传送门https://blog.csdn.net/weixin51216553/article/details/112384331?spm=1001.2014.3001.5501 众所周知，简单的前缀和解决
字符串读取的六种函数
综述： 字符串或字符的输入有好多个函数，scanf、getline、cin.getline、cin.get、gets、getchar等 如果输入是不带空格的字符串，那用什么都可以了，建议用scanf或cin 如果输入带空格，那scanf、c
二分图之匈牙利算法
二分图定义 二分图又称作二部图，是图论中的一种特殊模型。 设G=V,E是一个无向图，如果顶点V可分割为两个互不相交的子集A,B，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集i in A,j in B，则称图G为
树状数组题单
注：本题单并非按照难度升序排的，而是按照个人做题时间排的 敌兵布阵https://vjudge.net/problem/HDU1166 单点修改 区间查询 求和 P3374 【模板】树状数组 1https://www.luogu.com.c
「板子」组合数取模
组合数取模 对于C^{m}\{n}%p的，根据n，m，p的数据范围来用不同的方法来求 1<=m<=n<=1000, p任意 数目比较少，而且a,b的值也比较小我们可以用递推的方法,利用性质3. Ca,b=Ca1,b1+Ca1,b. 1<=m
KMP算法
前言 KMP算法是一种字符串匹配算法，其重中之重是next数组的构建，其代码的简洁与神奇使其广受关注。 但不难发现，acm中学到的KMP和数据结构里面学到的KMP并不一样o︶︿︶o 之前我写过acm版的KMP，戳这里https://blog
关于SPFA——他死了……
单源最短路奇技淫巧之SPFA算法 !【洛谷日报16】SPFA算法教学https://pic4.zhimg.com/v24c9799ea33fb1fafe422e886674e067c1440w.jpg?source=172ae18b 引入
最小生成树之Kruskal算法
最小生成树之Kruskal算法 定义： 对于无向有环图，如果任意两个顶点都联通并且是一棵树，那么我们就称之为生成树 对于代权值的图，那么权值之和最小的生成树即为最小生成树 Kruskal算法 说白了，Kruskal算法就是大贪心！ 对于m条
区间dp
石子合并https://www.acwing.com/problem/content/description/284/ 题目描述： 设有 NN 堆石子排成一排，其编号为 1，2，3，…，N1，2，3，…，N。 每堆石子有一定的质量，可以用一
Dilworth定理
Dilworth定理 优美的Dilworth定理 Dilworth是针对偏序集的组合数学的一个重要定理，可以解决导弹拦截等问题（不要问我为什么优美.jpg 内容 偏序集上最小链划分中链的数量等于其反链长度的最大值。 理解 我来描述一下： 首
单调栈
dequeue双向队列 单调队列 问题： 对每个长度为k的滑动窗体，求其最大值和最小值 思路1: 使出秘技dequeue （STL赛高！） 这里根据雨巨生动形象的例子，我来简单描述一下下： 题意：给出各届acmer的实力，众所周知大学基本上
经典博弈论
博弈论 威佐夫博弈黄金分割比 经典例题: 有两堆石子，有两个绝顶聪明的人在玩一个游戏，每次每个人可以从一堆石子中取任意数量但不少于1个的石子，或从两堆中同时取走相同数量的石子，最后一个取完石子的人获胜。 面对博弈题，最重要的找出必败点 0,
「板子」ACM快读 && int128读入
快速读入int 快速读入longlong 快速读入string 快速读入double 128输入输出
「图论」判环、求环、最小环
判断是否存在环 无向图 并查集不仅能判环，还能判奇环，即利用带权并查集 dfs标记法 SPFA（给边加权值的方法来通过判正负环进行判环） Tarjan锁点，如果存在双联通分量则存在环 有向图 dfs标记法，用fa数组来记录 拓扑排序，跑完拓
二分查找&&二分答案
二分查找 Question 问题背景：ljz在宿舍和舍友打保皇，在发牌阶段，ljz取牌插牌的速度很慢，而其他五个舍友取牌插牌手速很快，导致他的下家总是在等他取牌。 对此，lzj进行了反思：面对手中已然排好序的牌，ljz对于一张新来的牌x只会
严格次小生成树
次小生成树 即不等于最小生成树的生成树的值的最小值 方法是考虑每条不在最小生成树上的边，连上这条边以后会在树上形成一个环，我们需要在这个环上找一个不等于刚连起来的边的最大值，然后删掉它 这里用的是倍增LCA来维护树上链的最大值和次大值 我们
二维费用的背包问题
二维费用的背包问题https://www.acwing.com/problem/content/8/ 题目描述： N件物品，容量是V的背包，背包能承受的最大重量是M 每件物品只能拿一次，体积是vi，重量是mi，价值是wi 问在容量和重量允许
珂朵莉树详解
珂朵莉树的起源？ 珂朵莉树原名老司机树Old Driver Tree，ODT，由2017年一场CF比赛中提出的数据结构，因为题目背景主角是《末日时在做什么？有没有空？可以来拯救吗？》的主角珂朵莉，因此该数据结构被称为珂朵莉树。 什么是珂朵莉
贪心算法知识总结
区间贪心 最小点覆盖问题https://www.acwing.com/problem/content/907/ 题目描述： 给n个区间，再数轴上选尽量少的点，使得每个区间至少包含一个选出的点 思路： 按区间右端点从小到大排列 取一个当前点p
唯一分解定理及其扩展
定义 任何一个大于 1 的数都可以被分解成有限个质数乘积的形式 其中p1<p2<...<pm，为素数，C\i为正整数 显然 n 最多仅有一个大于 \\sqrt{n}的质因子（若有两个的话，他们的乘积就大于 n 了） 试除法 枚举因子，将当前
并查集——最优美的数据结构之一
并查集 简介： 最简洁而优雅的树形数据结构之一（没有之一 用于处理一些不交集（即一系列没有重复元素的集合）的合并及查询问题 支持两种操作： 查找：确定某个元素处于哪个子集 合并：将两个子集合并成一个集合 为什么并查集是树形结构？ 因为并查集
最长公共子序列的长度与数量
最长公共子序列 思路： On^2的暴力与 当ar\i\ == br\j\，dp\i\ \j\ = maxdp\i 1\ \j 1\ + 1, dp\i\ \j\ dp\i\ \j\ = maxdp\i 1\ \j\, dp\i\ \j 1\
图论——连通性
定义 割点：对于一个点x，如果从图中删去x以及与x相连的所有的边，图不再联通，则称x为割点 割边：对于一条边e，从图中删去e，图不联通，则称e为割边 一个图如果不存在割点，则它是一个点双连通图，一个图的极大点双连通子图是他的点双连通分量 一
字符串截取函数substr() 的用法
substr的用法 substr函数是用于字符串的截取的函数，只适用于string类型，并不适用于字符数组。 当len的长度大于串的长度或者省略参数len时，会默认返回到字符串的结尾，当传参出现负数的时候会RE 1022.成语接龙https
c++ bitset用法
C++ bitset——高端压位卡常题必备STL bitset储存二进制数位，和bool数组差不多，不过有空间优化，bitset中一个元素只占1bit，相当于一个char元素所占空间的八分之一。 bitset中的每个元素都像数组一样单独访问
trie树题单
trie树 trie树又称前缀树，是一种有序树，常用于检索字符串、AC自动机、维护异或极值、维护异或和、01trie树、可持久化字典树等等 对acmer来说是个比较常见的东西，特别是涉及到前缀之类的字符串题 他的主要思想就是共享前缀，达到快
逆序对（归并排序 || 离散化加树状数组）
P1908 逆序对https://www.luogu.com.cn/problem/P1908 归并排序大法好 一般来说，求逆序数的第一反应应该是归并排序（难道不是冒泡暴力吗 归并的过程就是递归的过程，每次归并都分成左右两部分，无限分，左右
线段树题单
P3372 【模板】线段树 1https://www.luogu.com.cn/problem/P3372 区间修改 区间查询 求和 P3373 【模板】线段树 2https://www.luogu.com.cn/problem/P3373
浅谈扩展欧几里得算法
什么是拓展欧几里得？简单的说，就是求关于x,y的方程 ax + by = gcda,b 的所有整数解 现在我们来解决四个问题 什么是裴属定理，如何证明裴属定理？ 怎么用扩展欧几里得来求ax + by = gcda,b 的特解？ 怎么求由特解
拓扑排序详解
什么是拓扑排序？ 先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！ 拓扑排序说白了其实不算一种排序，但又像是一种排序（我是不是说了个废话qwq） 他其实是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线
单源最短路之迪杰斯特拉算法Dijkstra
单源最短路之迪杰斯特拉算法（Dijkstra） 问题定义： 求解单源点的最短路径问题：给定带权有向图G和源点s，求点s到图G中其他点的最短路径 可以采用迪杰斯特拉算法（Dijkstra），或者SPFA算法，这里我先介绍一下第一种Dijkst
拓扑排序
拓扑排序 定义： 拓扑排序指的是有向无环图所有顶点的线性序列 该序列需满足俩个条件： 每个顶点只出现一次 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面 有向无环图（DAG图）才有拓扑排序，且可能不止
万字背包详解
前言： 古有陈天华万字血书抗沙俄，今有本剧蒻万字背包虐dp 本文介绍了01背包、完全背包、多重背包、混合背包、分组背包等背包，并对其进行透彻的剖析，并附上了板子题，供您白嫖，以及一些奇葩变式，颇有意思，供你琢磨玩弄。此外绝大部分题都有二维数
最长上升子序列（LIS）
最长上升子序列（LIS） 定义： 最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。假设我们有一个序列 b i，当b1 < b
优先队列
优先队列之朴素版 合并果子https://ac.nowcoder.com/acm/problem/16663 题意： n个果子，数目为tr\i\，进行n 1次合并操作，每次都消耗两堆果子的重量和的体力，耗费的总体力等于每次合并所耗费的体力和
差分 - 前缀和
差分 前缀和 一维数组前缀和 为什么要学前缀和呢？学前缀和有什么用呢？ 让我们先看一下1657题http://www.acmicpc.sdnu.edu.cn/problem/show/1657来感受一下前缀和之“神奇” 题意： 给你n个数，
并查集
并查集找爹算法 定义 并查集是一种树形的数据结构，由两部分组成： 合并（Union）：把两个不相交的集合合并为一个集合。 查询（Find）：查询两个元素是否在同一个集合中。 算法概述 用集合中的某个元素来代表这个集合，该元素称为集合的代表元