一些算法笔记
May 23, 2025
Table of Contents
Table of Contents
一些算法笔记
记录一些做题中不太知道的，免得丢掉印象。
Enum class
enum class Gesture
{
C, // 石头
J, // 剪刀
B // 布
};对于 enum class 结构，调用的时候得用 Gesture::C 这种格式。
Map - low_bound
在 map 里面有一个很好用的 low_bound 函数，在map中查找第一个不小于（也就是大于或等于）给定的 key 的元素。
根据这个函数，可以实现一个区间的映射建立
std::map<int, char> gradeMap = {
{59, 'F'}, // 0-59分 -> F
{69, 'D'}, // 60-69分 -> D
{79, 'C'}, // 70-79分 -> C
{89, 'B'}, // 80-89分 -> B
{100, 'A'} // 90-100分 -> A
};
char getGradeFromMap(int score) {
// 如果分数小于0或者大于100，直接返回无效
if (score < 0 || score > 100) {
return '?';
}
// 查找第一个不小于score的键值对
auto it = gradeMap.lower_bound(score);
// lower_bound 找到了一个合法的区间上限
if (it != gradeMap.end()) {
// it->first 是上限分数，it->second 是对应的等级
return it->second;
}
// 如果没找到（比如分数大于100，虽然我们已经处理了），则为无效
return '?';
}
Set
set 调用的时候得用 auto，迭代器。
用 insert 插入值，迭代器输出值，迭代器是指针，所以得 *it 用来解应用。
见 week 2 12拼写检查。
set<ll>s;
for(ll i=0;i<n;i++){
ll x;
cin>>x;
s.insert(x);
}
ll count=0;
for(auto it=s.begin();it!=s.end()&&count<k;it++){
count++;
cout<<*it<<" ";
}并行
先把“并行”的本质想清楚：一个任务最早能开工的时间 = 它所有前置任务的“完成时间”的最大值。
所以你不需要显式“合并时间”，只要维护“最早开始/完成时间”，并在拓扑序里用 max 推进，并行的效果自然出现。 见 luogu P1113
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
//依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。
// 互相没有关系的杂务可以同时工作
// 有些杂务必须在另一些杂务完成的情况下才能进行。
// 有需要完成的 n 个杂务的清单，并且这份清单是有一定顺序的，杂务 k (k>1) 的准备工作只可能在杂务 1 至 k−1 中。
// 一道拓扑排序题，找到所有入度为0的点，更新其邻接点的入度，直到所有点都被更新完，但是并行计算时间是一个难点……
// 有些任务不需要第二个任务完成，但是下一个任务需要第二个和第三个共同完成，且第二个任务完成时间比第三个短的话，特殊任务不能计入计算……
// 难点是找到并行时间最大值。
struct task
{
int id;
int time;
vector<int>next;
int inDegree=0;
};
int main(){
int n;
cin>>n;
vector<task>tasks(n+1);
for(int i=1;i<=n;i++){
int id,t;
cin>>id>>t;
tasks[id].id=id;
tasks[id].time=t;
int k=-1;
while(cin>>k,k!=0){
tasks[k].next.push_back(id);
tasks[id].inDegree++;
}
}
vector<int>start(n+1,0); // 每个任务的最早开工时间，我该做线性统计而非归并计算……
vector<int>end(n+1,0); // 完成每个任务的最早时间
for(int i=1;i<=n;i++){
if(tasks[i].inDegree==0){
end[i]=start[i]+tasks[i].time;
for(int v:tasks[i].next){
start[v]=max(start[v],end[i]);
tasks[v].inDegree--;
}
//当入度为0，可以和现有线性时间的标记终止时间做比较了……
}
}
//最后终止的时间就是最短时间。把时间当作线性看待是关键。
cout<<*max_element(end.begin(),end.end())<<endl;
return 0;
}Kahn 拓扑排序
🟢 模板 1：固定源点 + 已知 u < v
（比如洛谷 P1807，保证输入边满足 u < v）
const long long NEG = -(1LL << 60);
vector<long long> dist(n+1, NEG);
dist[src] = 0;
for (int u = 1; u <= n; ++u) {
if (dist[u] == NEG) continue; // 不可达跳过
for (auto [v, w] : adj[u]) {
dist[v] = max(dist[v], dist[u] + w);
}
}- 适用：题面保证 u < v，编号就是拓扑序。
- 结果：
dist[v]是从源点出发到 v 的最长路。
🟡 模板 2：固定源点 + 不保证 u < v
需要自己跑 Kahn 拓扑
const long long NEG = -(1LL << 60);
vector<long long> dist(n+1, NEG);
dist[src] = 0;
queue<int> q;
vector<int> indeg(n+1, 0);
// 读边时统计 indeg[v]++
for (int i = 1; i <= n; ++i)
if (indeg[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
if (dist[u] != NEG) { // 源点可达才转移
for (auto [v, w] : adj[u]) {
dist[v] = max(dist[v], dist[u] + w);
if (--indeg[v] == 0) q.push(v);
}
} else {
for (auto [v, w] : adj[u])
if (--indeg[v] == 0) q.push(v);
}
}- 适用：无 u < v 保证，但题目给的是 DAG。
- 结果：
dist[v]是从指定源点到 v 的最长路。
🔴 模板 3：全图最长路径（任意源 → 任意点）
先找所有入度 0 的点作为源
const long long NEG = -(1LL << 60);
vector<long long> dist(n+1, NEG);
queue<int> q;
vector<int> indeg(n+1, 0);
// 读边时统计 indeg[v]++
for (int i = 1; i <= n; ++i) {
if (indeg[i] == 0) {
dist[i] = 0; // 多源起点
q.push(i);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
if (dist[u] != NEG) {
for (auto [v, w] : adj[u]) {
dist[v] = max(dist[v], dist[u] + w);
if (--indeg[v] == 0) q.push(v);
}
} else {
for (auto [v, w] : adj[u])
if (--indeg[v] == 0) q.push(v);
}
}
long long ans = *max_element(dist.begin(), dist.end());- 适用：要求整个 DAG 上的最长路。
- 结果：ans 就是最长路径的长度。
📌 小提示
- 记得用 long long，避免路径和爆 int。
- NEG 要足够小，不然会被 +w 误更新。
- 如果要输出具体路径，可以额外记录
pre[v]来回溯。
欧拉路径
建模触发器
题面一旦出现：“把每个单词都用一次、能连就连、输出整条链” → 下意识联想到：欧拉路径（边全用一次）
- 点 = 字母（a..z）
- 边 = 单词（s[0] → s.back()，边上带着单词）
先验判定（能不能存在）
有向图欧拉路径充要条件（忽略方向连通 + 入出度条件）：
- 忽略方向后，所有出现过的点在同一连通分量（否则必然“断链”）。
- 入/出度：
- 欧拉回路：所有点 in = out
- 欧拉路径：恰有一个点 out = in + 1（起点），一个点 in = out + 1（终点），其余 in = out
- 其他情况 → 不存在
起点怎么“自己选”
- 若存在路径（非回路）：起点 = out = in + 1 的点（唯一）。
- 若是回路：理论上任意有边的点都可做起点。 为了字典序最小的成链，你的做法（每个点的出边按字典序取最小）已保证整体最小；起点通常选最小字母且出度>0就行。
为啥“对起点做 DFS 就对了”
核心是 Hierholzer 算法（欧拉路/回路的标准构造）：
- 在当前点反复“取一条尚未用过的出边”走下去（你按字典序取最小）；
- 没路可走就回溯，把刚走完的边对应的单词压入答案；
- 因为边是“走完才收录”，最后得到的是逆序，所以要 reverse。
正确性的直觉：像在一个区域里“抽线”，抽到抽不动了就封口记录，最终把所有边都抽走一次，拼起来就是欧拉路；你按最小边优先走，得到的就是字典序最小。
为什么“dp/最短路/拓扑”都不合适
- 要求“每条边恰好一次”是欧拉问题的专属信号；
- 拓扑/最短路/DP关心的是“点/路径权值/次数”，不是“边使用一次且全覆盖”。
- 所以这题不是“找最优”，而是“找一条恰好覆盖全部边的道”，自然落在 Hierholzer。
可复用“推导清单”
- 点=字母，边=单词（首→尾），边上存字符串
- 统计 in/out，并记录出现过的点
- 忽略方向做连通性检查
- 判度数：路径态/回路态；
- 起点：out=in+1 的点；若回路选最小出度>0 的点
- 各
adj[u]升序，遍历时用 back()+pop_back() - 跑 Hierholzer（递归/栈），收集边，逆序输出用 . 相连
- 验证边数是否都用到（
res.size()==n） 见 luogu P1127
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
void dfs(int u,vector<vector<string>>&adj,vector<string>&res){
while(!adj[u].empty()){
string s=adj[u].front();
adj[u].erase(adj[u].begin());
dfs(s.back()-'a',adj,res);
res.push_back(s);
}
}
int main(){
// 一个欧拉路径遍历的图？
int n;
cin>>n;
vector<string>str(n);
for(int i=0;i<n;i++) cin>>str[i];
vector<vector<string>>adj(26);
for(string &s:str){
adj[s[0]-'a'].push_back(s); //存单词去建立映射关系
}
for(auto &v:adj) sort(v.begin(),v.end()); //保证字母序
vector<int>indegree(26,0),outdegree(26,0);
for(int i=0;i<26;i++){
for(string &s:adj[i]){
outdegree[i]++;
indegree[s.back()-'a']++;
}
}
// 欧拉路径必要条件：有一个起点满足 outdegree-indegree=1，有一个终点满足 indegree-outdegree=1，其余点indegree=outdegree
int start=-1,end=-1;
for(int i=0;i<26;i++){
if(outdegree[i]-indegree[i]==1){
if(start==-1) start=i;
else { //多于一个起点
cout<<"***"<<endl;
return 0;
}
}
else if(indegree[i]-outdegree[i]==1){
if(end==-1) end=i;
else { //多于一个终点
cout<<"***"<<endl;
return 0;
}
}
else if(indegree[i]!=outdegree[i]){
cout<<"***"<<endl;
return 0;
}
}
vector<string>res;
if(start==-1){ //没有起点，说明是回路，从任意点开始
for(int i=0;i<26;i++){
if(outdegree[i]>0){
start=i;
break;
}
}
}
dfs(start,adj,res);
if(res.size()!=n){ //没有遍历完所有边
cout<<"***"<<endl;
return 0;
}
reverse(res.begin(),res.end());
for(int i=0;i<res.size();i++){
cout<<res[i]<<(i==res.size()-1?"":".");
}
return 0;
}DP
“我设了个
dp[..]，但是它到底在帮我算什么？目标到底是什么？为什么转移方程就是这么写？”
🌱 动态规划的“核心三问”
每次遇到题目时，可以强迫自己回答这三个问题：
-
状态是什么？
- dp[i] / dp[i][j] 代表什么量？
- 一句话清晰描述：它是“前 i 个物品的最优解”还是“走到 (i,j) 的最短路径”？
-
目标是什么？
- 我要的最终答案是 dp[n]、还是 max(dp[..])、还是 dp[n][m]？
- 把“输出需要什么”先对齐，避免“我设的状态跟目标无关”。
-
转移怎么来？
- 当前状态能从什么子问题转移而来？
- 每次写转移的时候，心里要对应一个“小故事”：比如“第 i 件物品选/不选”，“从左边或上边走过来”。
🌰 举个小例子
最经典：爬楼梯问题。每次可以走 1 步或 2 步，问走到第 n 层的方案数。
-
状态：
- dp[i] = 到达第 i 层的方案数。
-
目标：
- 我要求的是 dp[n]。
-
转移：
- 走到第 i 层，要么从 i-1 走一步上来，要么从 i-2 跨两步上来。
- 所以：dp[i] = dp[i-1] + dp[i-2]。
这个故事就非常清晰：每个状态对应一个问题，每个转移对应一个选择。
🔑 小技巧
-
一定要“写文字定义”：比如在草稿纸/注释里写清楚
dp[i][j] = 用前 i 件物品、放入容量为 j 的背包时能得到的最大价值。
——这样你每次写转移的时候，就能检查：我写的推导是不是跟定义一致。 -
目标不清晰时，回到题目最后一句：“要求的是……”。 把它翻译成对应的 dp 状态。
所以“每次设定 dp 目标不清晰”，其实就是第 2 步没对齐。 解决方法就是：
- 明确状态定义；
- 明确我要的答案在哪个状态里；
- 再来写转移。
卡特兰数
经典栈序列。
- n 个元素入栈出栈，每一步只能“入”或“出”，且出栈数从不超过入栈数（否则栈空）。
- 这等价于括号序列或 Dyck 路径计数：合法序列数量 = Cₙ。
三种常用公式
-
递推（DP，最常见，也就是你代码里的式子） 时间 O(n^2)。
-
闭式（组合数） 适合用大整数或高精度库。
-
线性递推（从前一项滚动推后一项） 每步一次乘除，注意整除无误差；实现时最好用大整数或先约分。
小表（前几项） n: 1,2,3,4,5,6,7,8,9,10 Cₙ: 1,2,5,14,42,132,429,1430,4862,16796
整型范围提示 • int 最多到 ；C₁₉=1,767,263,190 还勉强能放，C₂₀=6,564,120,420 就溢出了。 • long long 可安全到 n=35（C₃₅≈3.116×10¹⁸ < 2⁶³−1）。更大就要高精度。
二维矩阵
二维矩阵题给人的压迫感，往往不在代码量，而在于：
• 坐标系的混乱：到底是 a[x][y] 还是 a[y][x]？从 1 开始还是从 0 开始？
• 遍历方向的多样：上下左右、斜对角、跳马步，容易漏掉或写错。
• 边界条件的麻烦：是不是越界？是不是访问过？是不是要回溯？
• 可视化困难：在脑子里想“点和点的关系”比一维复杂很多。
看到矩阵题会害怕，其实是大脑在提醒你“这类题细节多、容易掉坑”。
怎么化解这种“二维恐惧症”？
技巧
一些很实用的小技巧：
- 固定模板 先写好一个方向数组，比如走 8 个方向：
int dx[8] = {1,1,1,0,0,-1,-1,-1};
int dy[8] = {1,0,-1,1,-1,1,0,-1};或者像马跳的 8 个方向：
int dx[8] = {1,1,-1,-1,2,2,-2,-2};
int dy[8] = {2,-2,2,-2,1,-1,1,-1};以后只要 for(int d=0;d<8;d++){ nx=x+dx[d]; ny=y+dy[d]; }，再加边界判断。这样就不会一边想题一边还要写乱七八糟的 if/else。
- 边界判断写成函数
bool inside(int x,int y,int n){
return x>=1 && x<=n && y>=1 && y<=n;
}这样比直接写条件判断要清晰、少 bug。
-
先手动画一张小图 比如 3×3、4×4，用笔画出来，标记 BFS 的扩展顺序，你会发现很多规律更直观。
-
小数据先跑暴力 先写 BFS/DFS 版本，在 n=5,k=2 这种小范围跑出来，打印过程，心里就踏实多了。
心态
二维矩阵题 不是 DP 的专利，它可以是 BFS（可达性）、DFS（连通块）、模拟（翻格子）、数学（对称性）。你害怕其实是因为没把“矩阵”当作普通的图。把矩阵想成一个图，格子是节点，四周/八周/马步是边，其实问题就清爽了。