FrankWkd

Created At 2025-04-15 Updated At 2025-07-15. Upd: 学习笔记，补题。 Trie树 字典树 这里笔者复习的时候因为没写学习笔记吃了大亏，所以赶紧补一下。 Trie树就是你从根从上到下建树，这方面的内容可以看oiwiki的Trie树。 笔者查了半天还很懵的部分：Trie树那个二位数组到底代表什么？ triei,jtrie_{i,j}triei,j​ 代表的是从节点编号为 iii 向下看的为 jjj（实际上是 (char)j+'a'）的字符在 Trie 树中的位置（不如说是在树中的节点编号） 具体看图（from oiwiki）： 在该图中，trie1,atrie_{1,a}trie1,a​ 代表的是从节点 111 向下看的字符 a 在 Trie 树中的位置（节点编号），也就是编号为 222 的节点。即：trie1,a=2trie_{1,a}=2trie1,a​=2. 注释版建树模板: 12345678910111213int a[101010][30]; // 如题int cnt[101010], idx; // 以该节...

青年节快乐！ 单调栈&单调队列 1.单调栈 1.从栈底到栈顶满足单调性的结构。 2.“栈+维护单调性” 3.单调栈作用：把序列中每个元素放到单调栈中维护就可以快速求出区间每个元素的最大/最小值。 性质：元素入栈之前会把栈顶破坏单调性的元素删除，保证元素入栈后栈仍保持单调性。 一般使用单调栈的题目具有以下两点：离自己最近（栈的后进先出性质），比自己大/小/高/低. 其实单调队列相关问题（尤其是单调队列DP）可以用RMQ来解。本质就是以更加优秀的复杂度求区间最大最小值（甚至RMQ还可以求更多满足条件的值） 经验之谈：不要用 stackstackstack 会被卡卡卡卡常。。。 1.奶牛排队 very easy板子走起 12345678910111213#include <bits/stdc++.h>using namespace std;stack <int> s;int n, x;int main() { scanf("%d", &n); for (int i = 1; i <= n; i++)...

这里统一采用复杂度最优的Kruskal+最优性剪枝方法，Prim流消失 板子 12345678910111213141516171819202122232425262728293031323334353637383940/*Kruskal算法思路：先把边从小到大排序，然后从小到大选边，选边后将这两个点在并查集中merge一下，然后如果选边之前这两个点已经联通了（find相同）我们就跳过此次选边（因为选择这个边是没有意义的）*/#include <bits/stdc++.h>using namespace std;//Kruskal//记得输出不连通的情况（orz）int f[101010];struct node{ int x,y,z;}a[1010101];int n,m,ans = 0,cnt,tot;int find(int x){ if(f[x] != x) return f[x] = find(f[x]); return x;}bool cmp(node xx,node yy){ return xx.z &...

Bellman-Ford 前置知识 首先你需要知道图论最核心的一个思路——松弛。 他是啥呢？笔者当时学的时候也花了亿堆时间理解它，就是假如我们现在有一些边，如图： 简单来说，松弛就是不断的更新两个点的距离使得它比之前的答案更优。 在这张图片里，我们将要松弛的 222 个节点为 (A,B)(A,B)(A,B) ，AAA 为源点 那么它的原始距离是 101010 ，那么如果我更新了他的一条路径（松弛成功），这个路径的边权和一定是要比 101010 小的。 好，那我们先来遍历和 BBB 点有直接连边的节点。 先看 C1C_1C1​ 那我们知道现在点 C1C_1C1​ 到点 AAA 的距离是 222 ，那因为 C1C_1C1​ 到点 BBB 的距离是 999 ，所以 AAA 到 BBB 经过点 C1C_1C1​ 的距离就是 2+9=112+9=112+9=11 ，很显然，这个答案是比当前已知答案要差的。所以这次松弛并没有成功，我们选择放弃当前绕路的边权和。 再看 C2C_2C2​ 那我们知道现在点 C2C_2C2​ 到点 AAA 的距离是 333 ，那因为 C2C_2C2​ ...

开篇 区间和：前缀和 区间加减值：差分（离线） 区间最值：RMQ，单调队列 单点修改，区间查询：树状数组 单点/区间修改，区间查询：线段树。 Updated at 2025.05.21 Updated at 2025.05.25 线段树 O(nlogn)O(nlogn)O(nlogn) 的复杂度内完成 nnn 个数的区间修改 单点修改复杂度 O(logn)O(logn)O(logn) 线段树采用完全二叉树的方法存储，数组存储，数组长度要开 4×n4\times n4×n。 建树 123456789101112//递归建树(a为原始数组，tr为线段树)int tr[101010], a[10];void build(int k, int l, int r) { //分别对应：节点标号，对应数组的的区间的左右下标 if (l == r) { tr[k] = a[l]; //如果是叶子节点 return ; } int mid = (l + r) >> 1; build(k * 2, l, mid);//构造左子树 build...

About 有向无环图（DAG） 有向图：由顶点和有向边组成的图，边具有方向性。 无环图：图中不存在任何有向环路。 拓扑排序：只适用于有向无环图（DAG），用于确定顶点的线性顺序，使得对于每一条有向边 (u,v)(u, v)(u,v)，顶点 uuu 在顶点 vvv 之前。 拓扑排序的定义 给定一个有向无环图 G=(V,E)G = (V, E)G=(V,E)，拓扑排序是将图中所有顶点排成一个线性序列，使得对于每一条有向边 (u,v)(u, v)(u,v)，顶点 uuu 在顶点 vvv 之前。 示例 假设有以下有向图： 1231 -> 2 -> 31 -> 44 -> 3 一个合法的拓扑排序是：1, 2, 4, 3 或 1, 4, 2, 3。 拓扑排序的原理 拓扑排序的核心思想是通过不断移除入度为 0 的顶点，并更新其邻接顶点的入度，直到所有顶点都被移除或无法继续移除。 算法步骤 初始化： 计算每个顶点的入度（即指向该顶点的边的数量）。 将所有入度为 0 的顶点加入队列。 处理队列： 从队列中取出一个顶点，将其加入拓扑排序结果。 遍历该顶点的...

Tarjan求SCC学习笔记 网上看了几篇博客，还有OI Wiki，觉得整合度不够，于是特意写了篇博客。 参考资料 Cnblogs@miaopan 全网最!详!细!Tarjan算法讲解。 强连通分量(SCC)与缩点 强连通分量 - OI Wiki 正文 在学习强连通分量和缩点之前，请务必理解邻接表。 以下有OI Wiki的内容，有大佬博客里的内容，也有我自己的内容。 强连通分量 引入 强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。 强连通分量（Strongly Connected Components，简称SCC）的定义是：极大的强连通子图。 举一个简单的例子。下面是一个有向图。 在这个图中， 1和2互相有路径可以到达对方，所以这两个点强连通； 1、2和3中任意两个点都连通，它们是这整个有向图的强连通分量。 求强连通分量。 下面我们介绍使用Tarjan算法求强连通分量。 我们举个例子说明这个算法是怎么运作的。图片取自《算法竞赛进阶指南》。 从 ①①① 进入，dfn[1] = low[1] = ++index == 1 入栈 ①①①，此时的栈中元素为 ①①①，...

【位运算】801. 二进制中1的个数 使用 lowbit 查找出二进制中 111 的个数 123int lowbit(int x){ return x & -x;//-x具有较高优先级} 每次进行 lowbit ，然后减去 lowbit(x) 直到为 000。减的次数即为答案。 12345678910111213141516//学校垃圾评测机需要吸氧O3#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin>>n; while(n--){ int k,a = 0; cin>>k; while(k > 0) k -= (k&-k),a++;//内嵌lowbit cout<<a<<" "; }} ...

树的DFS遍历 先用链式前向星存，然后DFS遍历一遍。 板子如下： 123456789101112131415161718192021222324#include <bits/stdc++.h>using namespace std;int n,x,y,z,pre[110],k;struct node{ int to,len,nxt;}a[220];void add(int u,int v,int l){ a[++k] = {v,l,pre[u]}; pre[u] = k;}void dfs(int x,int fa){ for(int i = pre[x];i;i = a[i].nxt){ if(a[i].to != fa) dfs(a[i].to,x); }}int main(){ cin>>n; for(int i = 1;i < n;i++){ cin>>x>>y>>z; add...

RMQ 之前博客有过 【一本通提高篇RMQ】数列区间最大值 & 【省选基础数据结构 RMQ】[Usaco2007 Jan]Balanced Lineup排队 两个题都是RMQ板子，直接求就行，第二题需要求两遍。 Code【一本通提高篇RMQ】数列区间最大值 12345678910111213141516171819202122232425262728#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;const int N = 1e6+10, L = 20;int f[N][L];int a[N], n, k, lg[N];int l, r;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; f[i][0] = a[i...