首图论，是 OI 中一个非常重要的分类，涵盖多种算法、题型
包括但不限于
图的存储DFS (图论)BFS (图论)树上问题有向无环图拓扑排序最短路问题生成树问题斯坦纳树拆点连通性相关环计数问题最小环2-SAT欧拉图哈密顿图二分图平面图弦图图的着色网络流图的匹配Prüfer 序列矩阵树定理LGV 引理最大团搜索算法支配树……
但是，这篇文章提到的，也是 CSP - S 复赛中涵盖的考点，只有
最小生成树
最短路
拓扑排序
最近公共祖先
其中，最短路问题可以通过最小生成树改写，就不过多赘述了。
最小生成树我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。
我们这里主要说 Prim 算法
Prim 算法Prim 算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。
具体做法 算法步骤及总结
...
首本文记录了自年初以来直至今日（2025.11.11）的总结
正文初识 OI今年年初，我正式踏上了我的 OI 之旅 —— 学校要组建一个信息竞赛班。我当时对代码比较好奇，脑子一热，也参加了。前三节课淘汰了不少来混的人，剩下的都是想认真学的了。中途不断有人因坚持不下来而退出，但我没有，可能是因为我在理科方面思维比较活跃、敏捷，我当时并不觉得怎么难 *（PS：考信竞的时候就打脸了 :( ）* 。
追更博客于是，接下来的日子，我跟着老师正常学、正常刷题。直到 2 月（可能是吧，记不清了）月初，一次课程结束后，一位同学跟我说 “你看这个人的主页好漂亮”（其实只是加了点 class，这个 OJ 框架本身有这些 class 集成的样式）。虽然知道这个很简单，但是，我却看上了他主页下面的链接（当时是 zeabur 分发的二级域名，现在已经没了）。回家后，我点开了这个链接，发现链接内的网站是一个类 HEO 主题的个人博客（当然，我当时别说 HEO 了，连博客是什么、网站的部署，甚至连 html 都不太清楚。只知道是一个非常好看的，看起来像是写了很久、花了很大功夫的网站。现在的样式预览： 点我 ...
压行压行，指的是将多行代码压成一行并省略某些符号，多数情况下用于简化代码。
例如：
123for(int i=0;i<n;i++){ cin>>a[i];}
可以压为一行
1for(int i=0;i<n;i++)cin>>a[i];
压行的一些操作循环for / while 循环在循环内只有一行或多行简短代码（如 l++ 等）且 没有（或只有单个）“break”,” return” 这种关键字时可以压行
12for(int i=0;i<n;i++)cin>>a[i],i++,i--;while(q--)// 循环内代码
条件判断if-else 在条件执行内只有一行或多行简短代码（如 l++ 等）且 没有（或只有单个）“break”,” return” 这种关键字时可以压行
12if(n%2==0)cout<<"1";else cout<<"0";
函数1bool cmp(int a, int b){return a>b;}// 别忘了分号
反回合并当某些要求 “没有（或只有单个）” r ...
引前些日子，我买了一块自称 256GB 的不知名 U 盘 （主要是看着便宜，太便宜了，想 捡漏 制裁一下）
买回家一看，典型的三无，上面什么都没有（买的时候没有标注自营，几乎可以肯定是扩容盘）
什么是扩容盘：
扩容盘，指的是一些容量虚标（属性选项卡中显示参数被改了，比如实际只有 32G，改成 256G 去卖）的 U 盘或硬盘
扩容盘的危害：
在拷贝大文件时会丢失 （强烈建议大家一定要确认不是扩容盘，我被这玩意害惨了，手机里几年的数据全没了）
好，那么好，既然是扩容盘，那我倒要看看这个 商家有多黑心 盘能扩容到什么程度
h2testw，走起！
later……
经实测，该盘实际容量仅为 64GB
找商家仅退款成功！白捡一个 64G 的 U 盘，美汁汁~(●ˇ∀ˇ●)
h2testw简介这个东西是一个在 windows 上的工具，非常好用，可以通过写入 / 读取文件来判断该盘是否有问题及实际容量。吃读写速度，吃 U 盘寿命（并没有多少贪吃）
下载提取码 h2t
使用h2testw 是一个 exe，这个 exe 就是工具本身，不是安装程序，不必惊讶~
运行 exe，选择 简体中文
选 ...
关于 BFSBFS，广搜，是一种寻找最短路、连通块的常用算法。我通常用队列实现
框架连通块为例
123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <bits/stdc++.h>using namespace std;#define ll long longconst int dx[8] = {-1,-1,-1,0,0,1,1,1};// 方向，需要遍历的邻居const int dy[8] = {-1,0,1,-1,1,-1,0,1};int main() { // ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin>>n>>m; vector<string>g(n);// 表 for(int i=0;i<n;i++)cin>>g[i]; int ans = 0; queu ...
情景导入有时，我们需要求一个数组的最大子数组和（即连续子数组的和最大），并给出这个和（别问为什么，问就是题目要）。
Kadane 算法的原理首先，我们获得一个数组，并定义两个变量 csum 和 smax 。然后，我们可以开始 kadane 算法。
在算法开始时，将 csum（当前连续子段的和）初始化为数组的第一个元素，将 smax（全局最大子段和）也初始化为该值。接下来，从第二个元素开始，依次向右遍历整个数组。
对于每一个元素 a[i]，我们要判断：如果当前的 csum 加上 a[i] 小于 a[i] （ csum 小于 0），说明前面的子段对总和是负贡献，继续加下去只会让后续的结果更小，所以应当舍弃之前的子段，从当前位置重新开始，也就是令 csum = a[i]。否则，如果 csum 仍然大于等于 0，就说明它对后续仍有正向贡献，我们可以安全地把当前元素加上去，csum += a[i]。
每处理完一个元素，就更新全局最大值：smax = max(smax, csum)。这样，smax 始终保存着从开头到当前位置为止出现过的最大连续子段和。
当遍历完整个数组后，smax 就是整个数组的 ...
前言11 月 1 号，CSP 将开始第二轮的考试（机试），也在此提前祝大家取得自己满意的成绩
第二轮需要用到 NOI-linux 系统，但很多考生第一次接触这个系统，就算已经看过很多遍教程，到了考场上，可能还会紧张，慌乱间忘记教程。那么，你就很有必要来看一看这篇博客
本篇博客教你在你自己的电脑（以 windows11 做示范）中安装虚拟机和 noi-linux 系统，顺带使用教程
开始安装 Vmwarenoi-linux 系统需要在虚拟机环境中运行，这里我用的是 vmware。
进入 vmware 官网，选择适合你的版本，下载安装程序
下载完成后，运行安装程序，配置的话按你自己的需求来。安装
安装完成以后，进入下一步
下载 NOI-linux 映像文件在 官网 下载 NOI-linux 的映像文件
注意，你下载的不是虚拟机，是系统的映像文件，vmware 需要通过映像文件创建虚拟机
安装 NOI-linux 虚拟机打开 vmware ，点击 创建新的虚拟机 ，映像文件中选择你下载的 NOI-linux 映像文件。然后剩下的配置按照你自己的喜好和电脑物理配置来，但注意不要给太低配置， ...
线段树简介什么是线段树线段树是一种数据结构，通常用于处理区间范围内的查询和更新问题。它的主要优点是能够以对数时间复杂度处理区间查询与区间更新。我们通常使用结构体（或数组）来模拟线段树的数据结构。
线段树能干什么线段树主要有两个基本操作：
区间查询（例如：区间求和、区间最值、区间最大公约数等）: 时间复杂度为 O(log n)。
区间更新（例如：区间加法、区间赋值等）: 时间复杂度为 O(log n)。
线段树比树状数组更强大，因为它支持区间更新，而树状数组仅支持单点更新或单点查询。
洛谷 P3372【线段树 1】例题讲解题目描述：
给定一个长度为 n 的数组 a[]，支持两种操作：
区间加法：对区间 [l, r] 中的每个元素增加一个常数 k。
区间求和：查询区间 [l, r] 中所有元素的和。
线段树解决方案我们可以使用线段树来解决此问题，其中：
每个节点存储一个区间的和（例如：区间 [l, r] 的和）。
每个节点还存储一个懒标记（add），用于记录该区间需要被加上的常数值。
关键操作
懒标记（Lazy Propagation）：为了优化区间更新操作，使用懒标记 ...
树状数组介绍是什么一种统计数据的方式（结构为数组）
用处大数据的 点增 & 前缀和
上手实操基本代码初始化 lowbit 点增前缀和全部1234// ------------初始化------------const int N;// 范围int n;ll tr[N];123456789101112// -----------lowbit------------inline int lowbit(int x){return x & -x;}// 求x在二进制下是1的位数的最低位/** * x = 11001000 , lowbit(x) = 4 * ~~~~^~~~ * * x = 10010010 , lowbit(x) = 2 * ~~~~~~^~ * */123456// ------------ 点增 ------------void add(int x,int k){// 第x个数加上k for(int i=1;i<=x;i+=lowbit(i)){ tr[i]+=k; }}12345678//------ ...
关于 ST 表用于ST 表（即稀疏表，以下称 ST 表）可以用于频繁求区间最值的问题，普通算法每次请求复杂度为 O(n)，ST 表预处理复杂度为 O(n+m) ，每次请求复杂度为 O(1)
原理ST 表是将一个数组二分成很多小段，每一段求一个最值。若给出两个端点（ l,r ），一定可以给出两个 ST 表中预处理过的区间，使得这两个区间覆盖了 l,r 间所有的端点，此时将这两个预处理过的区间的最值取一个最值，即可求得 l,r 间的最值
练习 & 实战题目模板题
题目描述
P1816 忠诚题目描述老管家是一个聪明能干的人。他为财主工作了整整 $10$ 年。财主为了让自已账目更加清楚，要求管家每天记 $k$ 次账。由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚。他把每次的账目按 $1, 2, 3, \ldots$ 编号，然后不定时地问管家这样的问题：在 $a$ 到 $b$ 号账中最少的一笔是多少？为了让管家没时间作假，他总是一次问 ...
