JustRaincoat Notebook

菜单

JustRaincoat Notebook OI/ACM 算法竞赛笔记

归档

2026 年 06 月

矩阵

2026-06-28

数据结构
矩阵 用于快速进行递推，常与快速幂结合使用。 矩阵作为一种存储向量的方式，是一种必须的数据结构。 Code 注意（重载输入输出流时）： 要记得返回 istream 或 ostream，并且仔细思考，哪些需要引用传参，哪些不能使用引用传参。 struct
并查集（DSU）

2026-06-28

数据结构
并查集（DSU） 用于快速判断元素是否属于同一个集合。 支持操作 将两个元素放到同一个集合中。 查询两个元素是否属于同一个集合。 代表元素思想 选择一个元素作该集合的代表元素，其他需要添加的元素作为这个代表元素的儿子，形成一颗树。 把判断集合与元素间的从属转化为集合与集合间的关系，通过递归查找。 实
双连通分量（DCC）—— Tarjan

2026-06-28

图论
双连通分量（DCC）——Tarjan 原理 和 SCC 一样都是在 dfs 生成树上记录 dfn 和 low，在环中编号最小的。 需要做一下概念上的区分： SCC（强连通分量） 是针对有向图的概念。一个SCC内的任意两个节点都可以互相到达（即存在双向路径）。 DCC（双连通分量） 是针对无向图的概念
线段树

2026-06-28

数据结构
线段树 问题 区间信息的维护与查询 写有哪些运算可以使用线段树来维护？ 线段树是一种非常强大的数据结构，它的核心功能是高效地处理区间查询和区间更新操作。线段树能够维护的运算必须满足一个关键性质：结合律。 核心要求：运算满足结合律 对于一个二元运算 ⊕
重链剖分（HLD）

2026-06-28

图论
Heavy-Light Decoposition 重链剖分 什么是重链剖分？ 树链剖分 树链剖分是指，将一棵树分成若干条链，使得这些链具有某些性质，使得树上操作变为链上操作和跳链操作（链间操作）。 重链剖分（Heavy-Light Decomposition，简称 HLD）是一种把树分解为若干条链的
强联通分量（SCC）—— Tarjan

2026-06-28

连通性
强联通分量（SCC）—— Tarjan 定义 强连通： 在一个有向图 G=(V,E)G = (V, E)
最近公共祖先 LCA

2026-06-28

树
最近公共祖先 LCA 什么是 LCA 最近公共祖先（Lowest Common Ancestor，简称 LCA）是树上最基础的问题之一：在一棵有根树中，两个节点的所有公共祖先里，深度最大（离根最远）的那个节点，就是它们的 LCA。 举个例子：对于查询 (u,v)
最小生成树（MST）—— Kruskal

2026-06-28

图论
最小生成树（MST）—— Kruskal 贪心策略：每次选择权重最小的边加入生成树，同时避免形成环路 可用于解决最小网络，最低价联通之类的问题 例题 P3366 【模板】最小生成树 #
树的直径

2026-06-28

图论
树的直径 定义 树的直径是指树中任意两个节点之间的最长路径的长度（边数或距离）。直径的两个端点称为直径端点。 性质与应用 图论基础：用于分析树的结构特征 网络优化：数据中心、通信网络中的延迟评估 算法设计：分治、动态规划的基础 竞技编程：树形DP问题中的常见模式 算法步骤 方法一：两次BFS/DFS
最短路算法

2026-06-28

图论
最短路算法 Introduction SPFA Dijkstra Floyd 最短路算法的应用 图论最短路算法核心比较表 特性 Dijkstra (优先队列优化)</
上一页 3 / 4 下一页