代码模板合集
2025/7/28大约 112 分钟
最短路算法流程
代码示例
使用示例
#include<bits/stdc++.h>
using namespace std;
/*Shortest Path Code*/
int main(){
cin>>n>>m;
init();
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
solve();
for(int i=1;i<=n;i++)
cout<<(dis[i]==inf?-1:dis[i])<<'\n';
return 0;
}2025/7/27大约 7 分钟
最短路算法流程
1. Floyd（，多源最短路径）
2025/7/26大约 4 分钟
2025/7/26大约 3 分钟
素数筛模板
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
// 线性筛法获取sqrt(r)以内的素数（时间复杂度O(n)）
vector<int> linearSieve(int limit) {
vector<bool> isPrime(limit + 1, true);
vector<int> primes;
for (int i = 2; i <= limit; ++i) {
if (isPrime[i]) primes.push_back(i);
for (int j = 0; j < (int)primes.size() && i * primes[j] <= limit; ++j) {
isPrime[i * primes[j]] = false;
if (i % primes[j] == 0) break; // 确保每个合数只被其最小质因数标记
}
}
return primes;
}
// 获取区间[l,r]内的所有素数
vector<int> primesInRange(int l, int r) {
if (l < 2) l = 2;
if (l > r) return {};
int sqrtR = sqrt(r);
vector<int> smallPrimes = linearSieve(sqrtR); // 使用线性筛预处理小素数
int m = r - l + 1;
vector<bool> isPrime(m, true);
// 用小素数标记区间内的合数
for (int p : smallPrimes) {
int k = max(2ll, (l + p - 1) / p);
for (int j = k * p; j <= r; j += p) {
isPrime[j - l] = false;
}
}
vector<int> result;
for (int i = 0; i < m; ++i) {
if (isPrime[i]) result.push_back(l + i);
}
return result;
}
signed main() {
int l, r;
cout << "请输入区间[l,r]的左右端点(l r): ";
cin >> l >> r;
vector<int> primes = primesInRange(l, r);
cout << "区间[" << l << "," << r << "]内的素数有: ";
for (int p : primes) cout << p << " ";
cout << endl;
cout << "共有 " << primes.size() << " 个素数。" << endl;
return 0;
}2025/7/24大约 1 分钟
浅谈 LCA
作者：Gemini 2.5 flash
简介
在图论中，最近公共祖先（LCA） 是指在一棵树中，距离两个给定节点最近的公共祖先节点。寻找LCA是树结构算法中的一个经典问题，在很多应用中都有重要作用，比如在计算基因序列的相似性、文件系统路径查找等方面。
1. 朴素算法
实现思路
朴素算法通常指的是最直观、最简单的暴力解法。对于LCA问题，一种朴素的思路是：
- 提升深度一致：将两个节点中深度较大的节点向上移动，直到它们与深度较小的节点处于同一深度。
- 同时上移：两个节点再同时向上移动，直到它们相遇。相遇的节点就是它们的LCA。
2025/7/23大约 18 分钟
2025/7/17大约 2 分钟
2025/7/14大约 5 分钟
前缀和/差分
提示
本文中，若无特殊说明， 代表原数组， 代表前缀和数组， 代表差分数组， 和 分别代表二阶前缀和数组和二阶差分数组。
本文中，若无特殊说明，数组下标为 的位置值是 。
2025/7/9大约 1 分钟
2025/6/1大约 11 分钟