codeforces-go

README

codeforces-go 💭💡🎈

算法 Algorithm

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

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

• 对该算法的基本介绍（核心思想、复杂度等）
• 参考链接或书籍章节（讲的比较好的资料）
• 模板代码（可以包含一些注释、使用说明）
• 模板补充内容（常见题型中的额外代码、建模技巧等）
• 相关题目链接（模板题、经典题、思维转换题等）

算法目录

• 数据结构
  • 单调栈 monotone_stack.go
  • 单调队列 monotone_queue.go
  • 双端队列 deque.go
  • 堆（优先队列）heap.go
    • 支持修改、删除指定元素
  • 并查集 union_find.go
    • 点权
    • 边权（种类）
    • 持久化
    • 回滚操作（动态图连通性）
  • 稀疏表（ST 表）sparse_table.go
  • 树状数组 fenwick_tree.go
  • 线段树 segment_tree.go
    • 延迟标记（懒标记）
    • 动态开点
    • 线段树合并
    • 线段树分裂
    • 持久化（主席树）
  • 左偏树（可并堆）leftist_tree.go
  • 笛卡尔树 cartesian_tree.go
  • 二叉搜索树公共方法 bst.go
  • Treap treap.go
  • 伸展树 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
    • 普通莫队
    • 带修莫队
    • 回滚莫队
    • 树上莫队
• 字符串 strings.go
  • 字符串哈希
  • KMP
    • 最小循环节
  • 扩展 KMP（Z algorithm）
  • 最小表示法
  • 最长回文子串
    • Manacher 算法
  • 后缀数组（SA）
  • 字典树 trie.go
    • 持久化
    • AC 自动机
  • 异或字典树 trie01.go
    • 持久化
    • Hack：构造一组数据，最大化树上的节点数
• 数学
  • 数论 math.go
    • 最大公因数（GCD）
    • 类欧几里得算法 ∑⌊(ai+b)/m⌋
    • Pollard-Rho 质因数分解算法
    • 埃氏筛
    • 线性筛
    • 欧拉函数
    • 原根
    • 扩展 GCD
      • 二元一次不定方程
    • 逆元
      • 线性求逆元
    • 中国剩余定理（CRT）
      • 扩展中国剩余定理
    • 离散对数
      • 大步小步算法（BSGS）
        • 扩展大步小步算法
      • 二次剩余
      • Jacobi 符号
    • 组合数学
      • 卢卡斯定理
      • 卡特兰数
      • 默慈金数
      • 那罗延数
      • 斯特林数
        • 第一类斯特林数（轮换）
        • 第二类斯特林数（子集）
      • 贝尔数
    • 莫比乌斯函数
    • 数论分块
    • 杜教筛
    • 容斥原理
  • 快速傅里叶变换 FFT math_fft.go
  • 快速数论变换 NTT math_ntt.go
    • 包含多项式全家桶（求逆、开方等等）
  • 快速沃尔什变换 FWT math_fwt.go
  • 连分数、佩尔方程 math_continued_fraction.go
  • 线性代数 math_matrix.go
    • 矩阵相关运算
    • 高斯消元
    • 行列式
    • 线性基
  • 数值分析 math_numerical_analysis.go
    • 自适应辛普森积分
    • 拉格朗日插值
  • 计算几何 geometry.go
    • 线与点
    • 线与线
    • 圆与点
      • 最小圆覆盖
        • 随机增量法
      • 固定半径覆盖最多点
    • 圆与线
    • 圆与圆
    • 圆与矩形
    • 最近点对
    • 多边形与点
    • 凸包
    • 最远点对
      • 旋转卡壳
    • 半平面交
  • 博弈论 games.go
    • SG 函数
• 动态规划 dp.go
  • 背包
    • 0-1 背包
    • 完全背包
    • 多重背包
    • 分组背包
    • 树上背包（依赖背包）
    • 字典序最小方案
  • 线性 DP
    • 最大子段和
    • LCS
    • LPS
    • LIS
      • 狄尔沃斯定理
    • LCIS
    • 长度为 m 的 LIS 个数
    • 本质不同子序列个数
  • 区间 DP
  • 环形 DP
  • 状压 DP
    • 旅行商问题（TSP）
    • 高维前缀和（SOS DP）
    • 插头 DP
  • 数位 DP
  • 倍增优化 DP
  • 斜率优化 DP（CHT）
  • 树形 DP
    • 树的直径个数
    • 在任一直径上的节点个数
    • 树上最大独立集
    • 树上最小顶点覆盖
    • 树上最小支配集
    • 树上最大匹配
    • 换根 DP（二次扫描法）
• 图论 graph.go
  • 链式前向星
  • 欧拉回路和欧拉路径
    • 无向图
    • 有向图
  • 割点
  • 割边（桥）
  • 双连通分量（BCC）
    • v-BCC
    • e-BCC
  • 最短路
    • Dijkstra
    • SPFA（队列优化的 Bellman-Ford）
      • 差分约束系统
    • Floyd-Warshall
    • Johnson
    • 0-1 BFS（双端队列 BFS）
    • 字典序最小最短路
  • 最小环
  • 最小生成树（MST）
    • Kruskal
    • Prim
  • 单度限制最小生成树
  • 次小生成树
  • 曼哈顿距离最小生成树
  • 最小差值生成树
  • 最小树形图
    • 朱刘算法
  • 二分图判定（染色）
  • 二分图找奇环
  • 二分图最大匹配
    • 匈牙利算法
  • 带权二分图最大完美匹配
    • Kuhn–Munkres 算法
  • 拓扑排序
  • 强连通分量（SCC）
    • Kosaraju
    • Tarjan
  • 2-SAT
  • 基环树
  • 最大流
    • Dinic
    • ISAP
    • HLPP
  • 最小费用最大流
    • SPFA
    • Dijkstra
  • 三元环计数
  • 四元环计数
  • 仙人掌
  • 树上问题 graph_tree.go
    • 直径
    • 重心
      • 点分治
    • 最近公共祖先（LCA）
      • 倍增
      • ST 表
      • Tarjan
      • 树上差分
    • 树链剖分（重链剖分，HLD）
    • 长链剖分
    • 树上启发式合并（DSU）
    • 树分块
    • Prufer 序列
• 其他
  • 位运算笔记 bits.go
    • bitset
    • 区间位运算 trick（含 GCD）
  • 二分 三分 sort.go
    • 0-1 分数规划
    • 整体二分
  • 搜索 search.go
    • 枚举排列
    • 枚举组合
    • 生成下一个排列
    • 康托展开
    • 逆康托展开
    • 折半枚举
      • 超大背包问题
    • 枚举子集
      • Gosper’s Hack
  • 随机算法 rand.go
    • 模拟退火
  • 杂项A common.go
    • 算法思路整理
    • 前缀和
    • 离散化
  • 杂项B misc.go
• 快读模板 io.go

如何选择题目 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

这一阶段要想上分，应以 DP 为主，图论和数据结构为辅。难度范围选择同上，可以根据自己在该项的能力上下调整。

我的 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 编程提交了。

算法竞赛入门经典（第二版）

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

算法竞赛入门经典训练指南（升级版）

算法竞赛进阶指南

算法竞赛入门到进阶

OI Public Library（含国家队论文）

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

算法竞赛课件分享 by hzwer

算法第四版 Java 源码

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

OI Wiki

CP-Algorithms

洛谷日报

All the good tutorials found for Competitive Programming

Codeforces Problem Topics

GeeksforGeeks 上的算法合集

Pepcy 模板

F0RE1GNERS 模板

【模板整合计划】目录

算法学习笔记（目录）

洛谷模板题（建议按难度筛选）

能力全面提升综合题单

Luogu Problem List

洛谷原试炼场

Links of ICPC/CCPC Contests from China

高级竞赛算法

算法进阶课

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

AtCoder 版！蟻本 (初級編)

AtCoder 版！蟻本 (中級編)

AtCoder 版！蟻本 (上級編)

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

待整理

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

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

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

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

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

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

其他 Others

My GoLand Live Templates and Postfix Completion settings

Useful Tools

Draw Geometry

Draw Graph

OEIS

Wolfram|Alpha

UpSolve.me

Codeforces Upsolving Helper

Contests Filter

Codeforced

Codeforces Visualizer

Codeforces Solve Tracker

Another Codeforces Solve Tracker

Rating and Difficulties

Open Codeforces Rating System

How to Interpret Contest Ratings

Codeforces: Problem Difficulties

Elo rating system

Stay Healthy

Exercises!