计算几何模板详解
1. 简介
计算几何是算法竞赛中的重要内容，涉及点、线、多边形等几何图形的各种计算和判断。本模板提供了完整的计算几何基础设施。
主要特点：
支持泛型，可处理整数和浮点数坐标
提供点、线的基本运算
实现了多边形相关算法
包含半平面交等高级功能
2. 实现原理
2.1 基本概念
向量运算：
点积：两个向量的点积表示它们的夹角关系
叉积：两个向量的叉积表示它们构成的平行四边形面积
点和线：
点用坐标(x,y)表示
线段由两个端点确定
直线可以用端点或者参数方程表示
2.2 核心策略
基础运算：
通过向量运算判断位置关系
使用叉积判断方向和位置
复杂算法：
通过基本运算构建高级功能
使用扫描线等技巧优化效率
3. 模板代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687 ...
模意义下整数运算 (ModInt)
模板详解
1. 简介
ModInt
是一个用于处理模意义下整数运算的模板类，它可以自动处理模运算，避免溢出，并提供了方便的运算符重载。
主要特点：
支持静态模数和动态模数
自动处理模运算和溢出
支持基本四则运算
提供快速幂和逆元计算
包含 Barrett 优化
2. 实现原理
2.1 基本概念
模运算：
所有运算都在模 P 意义下进行
需要保证结果在 [0, P) 范围内
Barrett 优化：
用于优化模乘法运算
避免使用除法运算
2.2 核心策略
模板设计：
使用模板参数指定模数
支持不同整数类型
运算优化：
使用 Barrett 算法优化乘法
快速幂优化幂运算
费马小定理求逆元
3. 模板代码
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868 ...
线性筛法 (Linear Sieve)
模板详解
1. 简介
线性筛法（也称欧拉筛法）是一种高效的素数筛选算法，它不仅可以在线性时间内筛出素数，还能同时得到每个数的最小质因子。
主要特点：
线性时间复杂度 O(n)
可以获得最小质因子
避免重复筛选
可以扩展求解积性函数
2. 实现原理
2.1 基本概念
素数：
只能被1和自身整除的大于1的整数
2是最小的素数
最小质因子：
一个合数的最小素数因子
对素数来说，最小质因子是其自身
2.2 核心策略
筛选过程：
用已知的素数去筛选更大的数
每个合数只被其最小质因子筛掉一次
优化方法：
维护最小质因子数组
按照特定顺序筛选，避免重复
3. 模板代码
1234567891011121314151617181920212223std::vector<int> minp, primes;void sieve(int n) { minp.assign(n + 1, 0); primes.clear(); for (int i = 2; i <= n; i++) { ...
边双连通分量 (EBCC) 模板详解
1. 简介
边双连通分量(Edge Biconnected Component,
EBCC)是指图中的一个极大子图，其中任意两点之间至少存在两条边不重复的路径。本模板实现了边双连通分量的计算，同时可以找出图中的割点(Cut
Vertex)和桥(Bridge)。
主要特点：
支持无向图的边双连通分量分解
可以识别割点和桥
支持图的压缩
时间复杂度 O(V + E)
2. 实现原理
2.1 基本概念
边双连通分量：
极大的边双连通子图
子图中任意两点间至少有两条边不重复的路径
割点与桥：
割点：删除后会增加图的连通分量数的点
桥：删除后会增加图的连通分量数的边
2.2 核心策略
Tarjan算法：
使用 DFS 遍历图
维护时间戳(dfn)和追溯值(low)
通过比较 dfn 和 low 识别割点和桥
压缩策略：
将每个边双连通分量压缩为一个点
构建压缩后的新图
3. 模板代码
12345678910111213141516171819202122232425262728293031323334353637383940414 ...
强连通分量 (SCC) 模板详解
1. 简介
强连通分量(Strongly Connected Component,
SCC)是有向图中的一个极大子图，其中任意两点之间都存在相互可达的路径。本模板使用
Tarjan 算法实现了强连通分量的计算。
主要特点：
支持有向图的强连通分量分解
基于 Tarjan 算法实现
时间复杂度 O(V + E)
可用于缩点构建DAG
2. 实现原理
2.1 基本概念
强连通分量：
有向图中的极大强连通子图
子图中任意两点互相可达
Tarjan算法：
基于DFS的单次遍历算法
使用时间戳和追溯值识别强连通分量
2.2 核心策略
DFS遍历：
维护时间戳(dfn)记录访问顺序
维护追溯值(low)记录可追溯的最早时间戳
栈维护：
使用栈记录访问路径
当dfn[x] = low[x]时找到一个强连通分量
3. 模板代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585 ...
测试数据生成器模板详解
1. 简介
测试数据生成器是对拍过程中的重要组成部分，用于生成随机测试数据来验证程序的正确性。一个好的生成器应该能够产生各种边界情况和随机数据。
主要特点：
可以生成随机测试数据
支持多种数据类型
可以控制数据范围
便于调试和对拍
2. 实现原理
2.1 基本概念
随机数生成：
使用 mt19937 引擎
控制数据分布
文件操作：
输出到文件
便于对拍使用
2.2 核心策略
数据生成：
控制数据范围
生成特殊情况
格式控制：
符合题目要求
保持数据合法
3. 模板代码
1234567891011121314151617181920212223#include <bits/stdc++.h>using i64 = long long;void solve() { // input your code }int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); freopen("in.txt", "r", stdin ...
对拍主程序模板详解
1. 简介
对拍主程序是自动化测试系统的核心，它负责编译源文件、运行程序、比较输出结果，并给出测试反馈。通过不断循环测试，可以快速发现程序中的错误。
主要特点：
自动化测试流程
实时结果比对
错误即时反馈
持续测试能力
2. 实现原理
2.1 基本概念
程序编译：
编译数据生成器
编译标准程序
编译待测程序
结果比对：
运行程序
比较输出文件
2.2 核心策略
自动化流程：
循环测试
错误检测
结果验证：
文件比对
状态反馈
3. 模板代码
123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>using i64 = long long;void solve() { system("g++ -std=gnu++23 stress__Generator.cpp -o stress__Generator"); system("g++ -std=gnu++23 stress__Good.cpp -o stress_ ...
随机数据生成器模板详解
1. 简介
随机数据生成器是对拍系统中的核心组件，用于生成高质量的测试数据。一个好的生成器应该能够产生多样化的测试用例，覆盖各种边界情况。
主要特点：
高质量随机数生成
可控的数据分布
支持多种数据类型
易于定制和扩展
2. 实现原理
2.1 基本概念
随机数引擎：
使用 mt19937_64
基于时间戳的种子
数据生成：
范围控制
分布控制
2.2 核心策略
随机性保证：
使用高质量随机数引擎
避免伪随机性
数据分布：
均匀分布
特殊情况构造
3. 模板代码
1234567891011121314151617181920212223#include <bits/stdc++.h>using i64 = long long;void solve() { std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count()); // input your code }int main() { std::ios:: ...
标准程序模板详解
1. 简介
标准程序是对拍过程中的重要组成部分，它通常采用最简单、最可靠的算法实现，用于验证待测程序的正确性。虽然效率可能不高，但正确性是最重要的。
主要特点：
实现简单直观
保证正确性
易于调试和验证
作为对拍基准
2. 实现原理
2.1 基本概念
暴力算法：
使用最直观的方法
保证结果正确
输出格式：
与待测程序一致
便于结果比对
2.2 核心策略
算法选择：
优先选择简单算法
避免复杂优化
结果验证：
严格按题目要求输出
保持格式一致
3. 模板代码
1234567891011121314151617181920212223#include <bits/stdc++.h>using i64 = long long;void solve() { // input your code }int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); freopen("in.txt", "r", stdin); fre ...
AC 自动机
(Aho-Corasick Automaton) 模板详解
1. 简介
AC 自动机是一种高效的多模式匹配算法，它结合了 Trie 树和 KMP
算法的思想，可以同时匹配多个模式串。
主要特点：
支持多模式串同时匹配
线性的匹配时间复杂度
可以处理带权值的模式串
支持动态内存管理
2. 实现原理
2.1 基本概念
Trie 树：
用于存储所有模式串
每个节点代表一个前缀
失配指针：
类似 KMP 的 next 数组
指向最长的可匹配后缀
2.2 核心策略
构建过程：
先构建 Trie 树
通过 BFS 建立失配指针
累加父节点的权值
匹配过程：
沿着 Trie 树移动
失配时跳转到失配指针
3. 模板代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475constexpr int N = 3e5 + 30, A = ...
