Rust 编程竞赛算法

这是一组经典的数据结构和算法集合，强调实用性、美观和清晰，而不是全面性。因此，不应将其视为一个黑盒 库，而应将其视为一个白盒 食谱，展示算法的设计和实现。希望它能对学生们、教育工作者以及算法编程竞赛爱好者有所帮助。

本仓库遵循 MIT 许可协议。竞赛提交不需要包含许可协议文本。祝您使用愉快！

面向学生和教育工作者

在学习新算法或数据结构时，看到或操作具体的实现通常很有帮助。因此，这个仓库收集了几个经典算法的最简单形式。

此外，Rust 语言具有出色的教学属性。它的编译器就像一位教师，在强制执行严格纪律的同时，指出了构建逻辑的更清晰方式。

面向编程竞赛

这个项目的原始目的是建立一个编程竞赛的参考。因此，它包含了一些在工具箱中非常有用的算法，强调代码简洁且在时间压力下易于修改。

大多数竞技程序员依赖 C++ 来获得其快速的执行时间。然而，C++ 以其不安全性而闻名，需要参赛者花费大量时间和精力来防止错误和调试。Java 是下一个最受欢迎的选择，它在牺牲一些编码和执行速度的情况下提供了一些安全性。

令我高兴的是，我发现 Rust 消除了整个类别的错误，同时减少了视觉混乱，使得剩余的错误更容易被发现。而且，它非常 快。当然，学习曲线是存在的。但是，熟练的 Rust 程序员可以获得竞争优势，并获得更愉快的体验！

支持 Rust 的某些竞赛网站和在线评测系统

• Codeforces
• AtCoder
• Kattis
• SPOJ
• LeetCode
• HackerRank
• Timus

以下支持2018年之前的Rust版本

• Google Kick Start和Code Jam

要了解如何开始，您可以查看我的一些过去提交。

编程语言倡导

我的另一个目标是吸引那些感觉受到古老（但仍然是主流）编程语言限制的开发者，通过展示现代技术的强大功能。

与其试图用言语说服您，这个存储库旨在通过实例展示。如果您想学习这门语言，我推荐官方书籍或《Programming Rust》。

内容

图

图表示

• 基于整数索引的邻接表表示
• 并查集

基本图算法

• 欧拉路径和回路
• Kruskal的最小生成树
• Dijkstra的单源最短路径
• DFS前序遍历

连通分量

• 连通分量
• 强连通分量
• 桥和2边连通分量
• 割点和2顶点连通分量
• 拓扑排序
• 2-SAT求解器

网络流

• Dinic的阻塞最大流
• 最小割
• Hopcroft-Karp二分匹配
• 最小费用最大流

数学

数论

• 最大公约数
• Bezout恒等式的规范解
• Miller素性测试

通用FFT

• 快速傅里叶变换
• 数论变换
• 卷积

算术

• 有理数
• 复数
• 线性代数
• 安全模算术

排序和搜索

• 为PartialOrd的比较器
• 二分搜索：C++的lower_bound()/upper_bound()的替代品
• 合并和归并排序
• 坐标压缩
• 在线凸包技巧（更新和查询一系列线的上凸包）

关联范围查询

• 静态分配的二元索引ARQ树（即具有惰性传播的通用segtree）
• 动态分配ARQ树，可选稀疏和持久
• Mo算法（即查询平方根分解）

扫描器

• 用于舒适读取输入数据的实用程序
• 文件和标准I/O示例

字符串处理

• 通用字典树
• Knuth-Morris-Pratt单模式字符串匹配
• Aho-Corasick多模式字符串匹配
• 后缀数组：使用计数排序的O(n log n)构造
• 最长公共前缀
• Manacher的线性时间回文搜索