DFS与BFS
模板 123456789101112131415161718192021222324252627void dfs(int dep)//dep代表递归层数或要填的第几个空{ if(所有空都填完了) { 判断最优解/记录答案； } for(枚举这个空能填的选项) if(这个选项是合法的) { 记录下这个空（保存现场）; dfs(dep+1); 取消这个空（恢复现场）; }}void bfs(int x){ queue<int> q; q.push(初始状态)//将初始状态入队 while(q.size()) { int u = q.front(); q.pop(); for(枚举所有可扩展状态)//找到u的所有可达状态v ...
单调栈与单调队列
单调栈与单调队列一般存在以下三种形式：存值，存下标，数组实现，数组实现的优点在于在清空栈时只需top=0即可 单调栈 伪代码： 12345678for(i=1->n)//n为元素数量{ ① while(栈非空且入栈元素优于栈顶元素)栈顶出栈//维持栈的单调性 //while结束的两种可能的判断 ② 如果(栈顶元素优于入栈元素)更新一次答案，此时栈顶即为最优解 否则 不存在答案 ③ 将新元素入栈} eg:输入n个数字 输出每个数字左侧距离该数字最近的比它小的元素，不存在则输出-1 in 5 7 8 5 6 7 out -1 7 -1 5 6 1234567891011121314151617181920212223//存值int a[N],ans[N];//a[N]用来存放输入的数字，ans[N]用于存放答案stack<int> stk;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){ ...
图
基本介绍 图(G)是由顶点集(V)和边集(E)组成的有序对，G=(V,E)，可以用|V|，|E|表示图中的顶点数量和边数量 图既可以是有向的，即单向链接，也可以是无向的，即双向链接。 只包含有向边的图称为有向图，只包含无向边的图称为无向图 若边关联了权重/成本，则叫做权重图，反之叫做非权重图 图的属性 一条边的两个端点为同一个顶点，称为自环 同一条边出现了不止一次，称为多重边 不包含自环或多重边的图称为简单图 边的数量 在一个简单图中，给定顶点的数量n(|V|=n) 有向图：0≤|E|≤n*(n-1) 无向图：0≤|E|≤n*(n-1)/2 若图中的边的数量接近最大的可能边数(顶点数量的平方)，则称这个图是稠密的。 若图中的边的数量接近顶点数量，则称这个图是稀疏的。 对图进行处理时，根据图的稠密/稀疏做出决策，如...
前缀和与差分
要对原数组a[N]进行修改与查询，需要用到前缀和数组和差分数组 diff求和——>a 求和——>prefix diff<——a差分<——prefix差分 一维前缀和与差分 前缀和 前缀和可用于求指定区间的和 求出前缀和数组 1前缀和数组的计算:prefix[i] = prefix[i-1] + arr[i] (此处及下文写法i均从1开始，以防止越界问题) 得出区间和 12由前缀和的可加性:sum[1,k] + sum[k+1,n] = sum[1,n]得到sum[l,r] = sum[1,r] - sum[1,l-1]，即sum=prefix[r]-prefix[l-1] 差分 差分可用于修改指定区间的值 求出差分数组 1diff[i] = a[i] - a[i-1]，它具有两个性质，一是可以通过求和得到a[i]，二是可以对后缀区间进行修改 对指定区间[l,r]的值进行修改 12diff[l] += x;diff[r + 1] -= x; 求出diff的前缀和数组，得到修改后的数组 1a[i] = a[i-1] +...
面向竞赛的C++STL
面向竞赛的 C++ STL 介绍 参考链接： https://space.bilibili.com/231911980/lists/4220963?type=season https://space.bilibili.com/498363953/lists/241249?type=season https://blog.csdn.net/weixin_51797626/article/details/123317216?spm=1001.2014.3001.5501 vector 涉及函数:at,back,push_back,pop_back,size,erase,clear,begin,rbegin,end,resize 创建数组 12345vector<int> v//创建int类型的空数组vv.resize(n)//创建后可随时自定义大小vector<int> v(10)//创建int类型的数组v，包含10个元素，所有元素默认初始化为0vector<int>...
Markdown基操
pr一点markdown教程，学会用笔才能写好字，把文章写漂亮 本文pr来源 emoji😊 数学表达式 vscode里的markdown Markdown 语法速查表 Markdown 语法参考手册 / 速查表。 总览 此 Markdown 语法速查表提供了所有 Markdown 语法元素的快速参考。但是此速查表无法涵盖所有极限用法，因此，如果您需要某些语法元素的详细信息，请参阅我们的 基本语法 和 扩展语法 手册。 基本语法 这些是 John Gruber 的原始设计文档中列出的元素。所有 Markdown 应用程序都支持这些元素。 元素 Markdown 语法 标题（Heading） # H1## H2### H3 粗体（Bold） **bold text** 斜体（Italic） *italicized text* 引用块（Blockquote） > blockquote 有序列表（Ordered List） 1. First item2. Second item3. Third item 无序列表（Unordered...
