Skip to main content

竞赛

竞赛（Contest）板块涵盖信息学奥林匹克竞赛相关的基础知识、常见题型、解题思路，以及代码模板和参赛经验。

内容聚焦实际竞赛环境，强调算法技巧、编程实践和竞赛能力的综合提升。

参考资料​

知识汇总​

模拟法、枚举、暴力、双指针、前缀和、差分、快速排序、归并排序、计数排序、基数排序、二分查找、二分答案、分治法、快速幂、贪心算法、深度优先搜索（DFS）、广度优先搜索（BFS）、回溯法、剪枝优化、迭代加深搜索（IDS）、双向BFS、A*算法、IDA*算法、线性DP、背包DP（01背包、完全背包、多重背包、分组背包）、区间DP、树形DP、状压DP、数位DP、记忆化搜索、DAG上的DP、概率DP、插头DP、图的存储（邻接表、邻接矩阵）、最短路径（Dijkstra、Bellman-Ford、SPFA、Floyd-Warshall）、最小生成树（Prim、Kruskal）、拓扑排序、强连通分量（Tarjan、Kosaraju）、双连通分量、欧拉回路、哈密顿回路、网络流（最大流、最小割、费用流）、二分图匹配（匈牙利算法、KM算法）、LCA（最近公共祖先）、并查集、RMQ（Range Minimum Query）、线段树、树状数组、ST表、分块、莫队算法、主席树、字典树（Trie）、AC自动机、后缀数组（SA）、后缀自动机（SAM）、KMP、Manacher、字符串哈希、滚动哈希、FFT（快速傅里叶变换）、NTT（数论变换）、高斯消元、矩阵快速幂、逆元、中国剩余定理（CRT）、欧拉定理、费马小定理、BSGS（大步小步算法）、Pollard-Rho质因数分解、Miller-Rabin素性测试、线性筛、容斥原理、卡特兰数、斯特林数、莫比乌斯反演、生成函数、博弈论（SG函数、Nim游戏）、计算几何（凸包、点积、叉积、旋转卡壳、半平面交）、三分法、模拟退火、随机化算法、启发式合并、CDQ分治、整体二分、斜率优化、四边形不等式优化、树链剖分、点分治、虚树、支配树、仙人掌图、最大团、最小树形图、2-SAT、DLX（舞蹈链）、斯坦纳树、哈夫曼编码、基环树、回文自动机、后缀树、块状链表、替罪羊树、KD树、李超线段树、笛卡尔树、圆方树、动态树（LCT）、可持久化数据结构、莫比乌斯函数、线性基、多项式运算、牛顿迭代、拉格朗日插值、线性规划、卢卡斯定理、扩展卢卡斯定理、二次剩余、Cipolla算法、多项式复合函数、快速数论变换

目录​

Last updated on