相关文章推荐
性感的小蝌蚪  ·  Codeforces Visualizer·  6 月前    · 
性感的小蝌蚪  ·  Personal History ...·  6 月前    · 
性感的小蝌蚪  ·  EndlessCheng/codeforce ...·  6 月前    · 

Repository files navigation

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

算法 Algorithm

由于算法知识点繁杂,将自己学习到的算法、做过的题目分类整理好是有必要的。

一个算法模板应当涵盖以下几点:

  • 对该算法的基本介绍(核心思想、复杂度等)
  • 参考链接或书籍章节(讲得比较好的资料)
  • 模板代码(代码注释、使用说明)
  • 模板补充(常见题型中的额外代码、建模技巧等)
  • 相关题目(模板题、经典题、思维转换题等)
  • 不了解 Go?快速入门教程

  • 集合论与位运算
  • 单调栈 monotone_stack.go
  • 单调队列 monotone_queue.go
  • 二维单调队列
  • 双端队列 deque.go
  • 堆(优先队列)heap.go
  • 支持修改、删除指定元素的堆
  • 前缀中位数
  • 滑动窗口前 k 小元素和
  • 并查集 union_find.go
  • 点权并查集
  • 边权并查集(种类并查集)
  • 可持久化并查集
  • 回滚并查集 & 动态图连通性
  • 稀疏表(ST 表)sparse_table.go
  • 树状数组 fenwick_tree.go
  • 差分树状数组(支持区间加、区间求和)
  • 二维差分树状数组
  • 树套树 & 三维偏序
  • 线段树 segment_tree.go
  • 线段树二分
  • 延迟标记(懒标记)
  • 线段树合并
  • 线段树分裂
  • 持久化(主席树)
  • 0-1 线段树 segment_tree01.go
  • 左偏树(可并堆)leftist_tree.go
  • 笛卡尔树 cartesian_tree.go
  • 二叉搜索树公共方法 bst.go
  • Treap treap.go
  • 前 k 小元素和
  • 伸展树 splay.go
  • 动态树 LCT link_cut_tree.go
  • 红黑树 red_black_tree.go
  • 替罪羊树 scapegoat_tree.go
  • k-d 树 kd_tree.go
  • 珂朵莉树(ODT)
  • 数组版 odt.go
  • 平衡树版 odt_bst.go
  • 根号分治、分块 sqrt_decomposition.go
  • 莫队算法 mo.go
  • 位运算(基础/性质/拆位/试填/恒等式/思维)
  • 图论算法(DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径)
  • 🔥 动态规划(入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
  • 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
  • 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
  • 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
  • 链表、二叉树与一般树(前后指针/快慢指针/DFS/BFS/直径/LCA)
  • 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)
  • 欢迎关注 B站@灵茶山艾府

    如何选择题目 How to Choose Problems

    Rating < 2100

    这一阶段主要目标是提高对问题的观察能力。做构造题可以针对性地训练这一点。

    选择难度在自己 rating 到 rating+200 范围内的构造题 (tag: constructive algorithms),按照过题人数降序做题,比如 [1700,1900] 区间的就是下面这个链接:

    https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900

    通过大量的构造题训练,提高观察能力,快速找到切题入口。具体见我在知乎上的这篇 回答

    Rating >= 2100(个人训练用,仅供参考)

    见识更高的山、更广的海。

    按人数从高到低,做 2200+ 的题目。 建议不设置难度上限 !由于按人数排序,难度分不会太高, 不设上限可以避免错过高分好题

  • 按照洛谷通过人数排序的 CF 题单
  • 构造题 2200+ :锻炼手玩能力。
  • DP 2200+ :几乎每场都有 DP。
  • 数学综合:数论、组合数学、概率期望等 2200+ :包含 6 个 tag。
  • 图论综合:图论+树上问题 2200+ :包含 7 个 tag。
  • 字符串 2200+ :数据结构题不好筛选,可以找树状数组/线段树的题单,这里只单独筛选字符串的题。
  • 交互 2200+ :偶尔做做,了解一些解题套路。
  • 博弈 2000+ :也适合锻炼手玩。由于题目比较少,从 2000 开始筛选。
  • 我的 Codeforces 账号

    测试及对拍 Testing

    编写一个 run(io.Reader, io.Writer) 函数来处理输入输出。这样写的理由是:

  • main 中调用 run(os.Stdin, os.Stdout) 来执行代码;
  • 测试时,将测试数据转换成 strings.Reader 当作输入,并用一个 strings.Builder 来接收输出,将这二者传入 run 中,然后就能比较输出与答案了;
  • 对拍时需要实现一个暴力算法 runAC ,参数和 run 一样。通过 随机数据生成器 来生成数据,分别传入 runAC run ,通过比对各自的输出,来检查 run 中的问题。
  • 具体可以见 Codeforces 代码仓库 main ,所有非交互题的代码及其对应测试全部按照上述框架实现。

    例如: 1439C_test.go

    交互题的写法要复杂一些,需要把涉及输入输出的地方抽象成接口,详见 interactive_problem

    学习资料及题目 Resources

    注:由于入门经典上选了很多区域赛的题,一部分题目可以在 GYM 上找到,这样可以就可以用 Go 编程提交了。

    算法竞赛入门经典(第二版)

    算法竞赛入门经典训练指南

    算法竞赛入门经典训练指南(升级版)

    算法竞赛进阶指南

    算法竞赛入门到进阶

    《算法竞赛》配套题单

    国家集训队论文列表

    算法竞赛 (ICPC, OI, etc) 论文,课件,文档,笔记等

    算法竞赛课件分享 by hzwer

    算法第四版 Java 源码

    数据结构和算法动态可视化

    OI Wiki

    CP-Algorithms

    The Ultimate Topic List (with Resources, Problems and Templates)

    A Huge Update on The Ultimate Topic List

    All the good tutorials found for Competitive Programming

    Codeforces Problem Topics

    The Ultimate Topic List(with Tutorials, Problems, and Templates)

    GeeksforGeeks 上的算法合集

    Pepcy 模板

    F0RE1GNERS 模板

    https://github.com/hh2048/XCPC 含 jiangly 模板

    https://www.cnblogs.com/alex-wei/p/contents.html

    【模板整合计划】目录

    算法学习笔记(目录)

    洛谷模板题(建议按难度筛选)

    能力全面提升综合题单

    Luogu Problem List

    洛谷原试炼场

    Links of ICPC/CCPC Contests from China

    AtCoder 题目分类

    AtCoder 版《挑战程序设计竞赛》

    AtCoder 版!蟻本 (初級編)

    AtCoder 版!蟻本 (中級編)

    AtCoder 版!蟻本 (上級編)

    AtCoder 版!蟻本 (発展的トピック編)

    【杂文】记一些有用的神奇网站

    偶然在 GitHub 上发现的超长列表

    算法竞赛训练中较难的部分

    算法竞赛中可能不太会遇到的论文题

    [杂谈]OI/ACM中冷门算法

    Things I don't know

    [meme] If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

    https://blog.csdn.net/calabash_boy/article/details/79973483

    https://github.com/zimpha/algorithmic-library

    https://www.luogu.com.cn/blog/command-block/blog-suo-yin-zhi-ding-post

    https://wcysai.github.io/

    https://www.luogu.com.cn/blog/Troverld/index

    C++ @cache

    其他 Others

    My GoLand Live Templates and Postfix Completion settings

    Useful Tools

    GeoGebra

    Draw Geometry

    Draw Graph

    Wolfram|Alpha

    ACD Ladders

    Contests Filter

    Codeforced

    Codeforces Visualizer

    Codeforces Solve Tracker

    Another Codeforces Solve Tracker

    AtCoder Problems

    AtCoder Companions

    AtCoder-Codeforces Rating converter

    在线 Markdown + LaTeX

    Rating and Difficulties

    Open Codeforces Rating System

    How to Interpret Contest Ratings

    Codeforces: Problem Difficulties

    Elo rating system

    Stay Healthy

    Exercises!