【好东西】ACM在线模版－f-zyj

爱被打了一巴掌 2022-06-16 10:16 85阅读 0赞

# 感谢这位dalao费心血整理了这份模板，谢谢！ #

原链接：http://blog.csdn.net/f\_zyj/article/details/51473493

# ForeWord #

六月六开始（话说，开始的日子真是个吉利的日子）到七月廿六，五十天整，终于将ACM在线模版整理完毕，想想还有点小激动呢~

话说，我为什么执着于整理这个模板呢？既费时又费力，差不多，五十天都在忙这个。   
想来，原因挺多的，毕竟网上模版那么多，如果单单只是其中任何一条存在，我一定不会这样卖力整理。

最直接的原因，上一次的ACM竞赛，让我深深认识到了模版的重要性，也让我感到了不适，比赛时很乏力。

说起来不适，就不得不承认一点，我的知识储备量严重不足，不足以驾驭模版，至于另一点则是对模版不熟悉，无法快速查阅。其实还有第三点原因，这个原因只会出现在我这种人面前，那就是编码规范问题。

很多人，一开始就没有养成严格的编码规范，所以平时看到一些不是太规范的代码也没有什么不适，而像我这种执着于编码规范的人，已经出现了强迫症，看着那些不是太舒服的代码，很容易急火攻心。说起规范，其实有很多种，但是让人最一目了然的，我想一定不是那些能省则省的编码（这是我要自己重新整理的重要原因）。

这样，待到以后ACM竞赛时，我就可以导出此模版，打印好(^o^)/~那么竞赛一定会如虎添翼的，模版出奇迹嘛~~~

说起来间接原因，主要是两点，首先是，通过整理模版，我可以快速建立起知识体系，在整理的过程中，全部是手打，所以对模版的体系很清晰，这也成就了我的知识体系的雏形。其次，在以后的学习、刷题过程中，可以通过这个在线模版快速查找，出现问题和漏洞快速修改，当然也很希望有志同道合的人能够给我提出错误，帮助我完善这份模版。

其实，还有辣么一丢丢小心思是，我的CSDN排名可以提前很多……浏览量也在快速增加，这是一个令人兴奋的事-\_-\#

PS:为避免模版整理后重复性过高，使其冗杂，一律不添加头文件和命名空间。欢迎提出模版修改建议～～～

# Index #

## 分类细则 ##

说起分类准则，我也是很头疼，毕竟对于很多[算法][Link 1]，他并不是单调的，而是多方面的都挂得上钩。所以，从始至终，分类准则一直都是我很纠结的问题。   
经过思量，首先分出比较主流的几类：`Number`、`Graph`、`Network`、`Structure`、`Geometry`；   
接着，考虑到C++是ACM的重头戏，而STL又是其中浓墨重彩的一笔，所以专门分出一类`STL`来总结一下；   
然后又分出`String`一类，毕竟字符串相关算法也是挺多的啊；   
最后，总得有一类`Other`吧！

虽说，分类分好了，可是有的算法真的不知道归到哪一类更合适，因为总有些算法既涉及到数论，也会涉及到[数据结构][Link 1]，或者其他情况也时常有。但是为了避免重复，我只好依自己拙见，把他放在了自己感觉最合适的分类中。

> [STL][]   
> [Number][]   
> [String][]   
> [Graph][]   
> [Network][]   
> [Structure][]   
> [Geometry][]   
> [Other][]

## 目录 ##

### STL 标准模版库 ###

> 1.  [STL 简介][STL 1]
> 2.  [STL pair][]
> 3.  [STL set][]
> 4.  [STL vector][]
> 5.  [STL string][]
> 6.  [STL stack][]
> 7.  [STL queue][]
> 8.  [STL map][]
> 9.  [STL iterator简介][STL iterator]
> 10. [STL algorithm][]

### Number 数论 ###

> 1.  [欧拉函数PHI][PHI]
> 2.  [GCD][]
> 3.  [模线性方程（组）][Link 2]
> 4.  [线性方程组（高斯消元）][Link 3]
> 5.  [素数相关][Link 4]
> 6.  [合数相关][Link 5]
> 7.  [组合数学相关][Link 6] 2016.12.14添加
> 8.  [Polya计数][Polya]
> 9.  [最大1矩阵][1]
> 10. [约瑟夫环问题][Link 7]
> 11. [博弈论][Link 8]
> 12. [大数非四则相关][Link 9]
> 13. [周期性方程][Link 10]
> 14. [阶乘][Link 11]
> 15. [排列组合][Link 12]
> 16. [求逆元][Link 13] 2016.12.14添加
> 17. [FFT][]
> 18. [整数划分][Link 14]
> 19. [A^B约数之和][A_B]
> 20. [莫比乌斯反演][Link 15]
> 21. [Baby-Step Giant-Step][]
> 22. [simpson积分][simpson]
> 23. [多项式求根][Link 16]
> 24. [星期问题][Link 17]
> 25. [所有数位相加][Link 18] 2017.5.4 添加
> 26. [汉诺塔][Link 19]
> 27. [斐波那契数列][Link 20]
> 28. [1/n循环节长度][1_n]
> 29. [矩阵相关][Link 21]
> 30. [反素数][Link 22]
> 31. [数论相关公式][Link 23]

### String 字符串 ###

> 1.  [编辑距离][Link 24]
> 2.  [KMP算法][KMP] 2017.3.23修正 + 2017.4.20修正
> 3.  [扩展KMP][KMP 1]
> 4.  [最短公共祖先][Link 25]
> 5.  [Karp-Rabin算法][Karp-Rabin]
> 6.  [Manacher最长回文子串][Manacher]
> 7.  [strstr函数][strstr]
> 8.  [Sunday Algorithm][]
> 9.  [AC自动机][AC]
> 10. [后缀数组][Link 26]
> 11. [后缀自动机][Link 27]
> 12. [字符串 HASH][HASH]

### Graph 图论 ###

> 1.  [最短路][Link 28]
> 2.  [第K短路][K]
> 3.  [最小生成树（森林）][Link 29]
> 4.  [次小生成树][Link 30]
> 5.  [曼哈顿最小生成树][Link 31]
> 6.  [欧拉路径][Link 32]
> 7.  [DAG的深度优先搜索标记][DAG]
> 8.  [图的割点、桥和双连通分支的基本概念][Link 33]
> 9.  [无向图找桥][Link 34]
> 10. [无向图连通度（割）][Link 35]
> 11. [最大团问题][Link 36]
> 12. [SPFA][]
> 13. [最小树形图][Link 37]
> 14. [一般图匹配带花树][Link 38]
> 15. [LCA][]
> 16. [生成树计数][Link 39]
> 17. [有向图最小树形图][Link 40]
> 18. [有向图的强连通分量][Link 41]
> 19. [双连通分支][Link 42]
> 20. [Tarjan强连通分量][Tarjan]
> 21. [弦图判断][Link 43]
> 22. [弦图的PERFECT ELIMINATION点排列][PERFECT ELIMINATION]
> 23. [稳定婚姻问题][Link 44]
> 24. [拓扑排序][Link 45]
> 25. [无向图连通分支][Link 46]
> 26. [有向图强连通分支][Link 47]
> 27. [有向图最小点基][Link 48]
> 28. [Floyd求最小环][Floyd]
> 29. [2-SAT][]
> 30. [树的重心][Link 49] 2017.3.8添加

### Network 网络流 ###

> 1.  [二分图匹配相关][Link 50]
> 2.  [无向图最小割][Link 51]
> 3.  [最大流][Link 52]
> 4.  [最小费用流][Link 53]
> 5.  [有上下界的流][Link 54]
> 6.  [最佳边割集][Link 55]
> 7.  [最佳点割集][Link 56]
> 8.  [最小边割集][Link 57]
> 9.  [最小点割集][Link 58]
> 10. [最小覆盖问题][Link 59]

### Structure 数据结构 ###

> 1.  [划分树][Link 60]
> 2.  [左偏树][Link 61]
> 3.  [线段树][Link 62]
> 4.  [伸展树][Link 63]
> 5.  [动态树][Link 64]
> 6.  [主席树][Link 65]
> 7.  [Trie树][Trie]
> 8.  [Treap][]
> 9.  [RMQ][]
> 10. [树链剖分][Link 66]
> 11. [二分查找][Link 67]
> 12. [树状数组][Link 68]
> 13. [滚动数组][Link 69]
> 14. [逆序数][Link 70]
> 15. [带权值的并查集][Link 71]
> 16. [快排][Link 72]
> 17. [机器工作调度][Link 73]
> 18. [大数四则运算][Link 74]
> 19. [取第k个元素][k]
> 20. [最长公共递增子序列][Link 75]
> 21. [0-1分数规划][0-1] 修正于2017.4.14
> 22. [最长有序子序列][Link 76] 2017.4.12 修正
> 23. [最长公共子序列][Link 77]
> 24. [最少找硬币问题][Link 78]
> 25. [棋盘分割][Link 79]
> 26. [区间最大频率][Link 80]
> 27. [堆栈][Link 81]
> 28. [莫队算法][Link 82]
> 29. [背包相关][Link 83]

### Geometry 计算几何 ###

> 1.  [Graham求凸包][Graham]
> 2.  [判断线段相交][Link 84]
> 3.  [判断四点共面][Link 85]
> 4.  [判断线段与圆是否相交][Link 86]
> 5.  [求多边形重心][Link 87]
> 6.  [三角形相关重点][Link 88]
> 7.  [平面最近点对][Link 89]
> 8.  [旋转卡壳][Link 90]
> 9.  [半平面交][Link 91]
> 10. [计算几何相关公式][Link 92]
> 11. [Liuctic计算几何库][Liuctic]

### Other 其他 ###

> 1.  [头文件][Link 93]
> 2.  [数据类型的取值范围][Link 94] 2017.2.24 修改
> 3.  [输入输出外挂总结][Link 95]
> 4.  [strtok和sscanf结合输入][strtok_sscanf]
> 5.  [解决爆栈，手动加栈][Link 96]

[Link 1]: http://lib.csdn.net/base/datastructure
[STL]: http://blog.csdn.net/f_zyj/article/category/6261338
[Number]: http://blog.csdn.net/f_zyj/article/category/6261331
[String]: http://blog.csdn.net/f_zyj/article/category/6243657
[Graph]: http://blog.csdn.net/f_zyj/article/category/6243089
[Network]: http://blog.csdn.net/f_zyj/article/category/6261329
[Structure]: http://blog.csdn.net/f_zyj/article/category/6261330
[Geometry]: http://blog.csdn.net/f_zyj/article/category/6261337
[Other]: http://blog.csdn.net/f_zyj/article/category/6243651
[STL 1]: http://blog.csdn.net/f_zyj/article/details/51746310
[STL pair]: http://blog.csdn.net/f_zyj/article/details/51746715
[STL set]: http://blog.csdn.net/f_zyj/article/details/52655609
[STL vector]: http://blog.csdn.net/f_zyj/article/details/51747218
[STL string]: http://blog.csdn.net/f_zyj/article/details/51756852
[STL stack]: http://blog.csdn.net/f_zyj/article/details/51756861
[STL queue]: http://blog.csdn.net/f_zyj/article/details/51756880
[STL map]: http://blog.csdn.net/f_zyj/article/details/51756971
[STL iterator]: http://blog.csdn.net/f_zyj/article/details/51755051
[STL algorithm]: http://blog.csdn.net/f_zyj/article/details/51756977
[PHI]: http://blog.csdn.net/f_zyj/article/details/51776219
[GCD]: http://blog.csdn.net/f_zyj/article/details/51776457
[Link 2]: http://blog.csdn.net/f_zyj/article/details/51783527
[Link 3]: http://blog.csdn.net/f_zyj/article/details/51784887
[Link 4]: http://blog.csdn.net/f_zyj/article/details/51793500
[Link 5]: http://blog.csdn.net/f_zyj/article/details/51810629
[Link 6]: http://blog.csdn.net/f_zyj/article/details/51869775
[Polya]: http://blog.csdn.net/f_zyj/article/details/51872368
[1]: http://blog.csdn.net/f_zyj/article/details/51872987
[Link 7]: http://blog.csdn.net/f_zyj/article/details/51873032
[Link 8]: http://blog.csdn.net/f_zyj/article/details/51873129
[Link 9]: http://blog.csdn.net/f_zyj/article/details/51873907
[Link 10]: http://blog.csdn.net/f_zyj/article/details/51874343
[Link 11]: http://blog.csdn.net/f_zyj/article/details/51876207
[Link 12]: http://blog.csdn.net/f_zyj/article/details/51883386
[Link 13]: http://blog.csdn.net/f_zyj/article/details/51810863
[FFT]: http://blog.csdn.net/f_zyj/article/details/51833020
[Link 14]: http://blog.csdn.net/f_zyj/article/details/52806846
[A_B]: http://blog.csdn.net/f_zyj/article/details/51851501
[Link 15]: http://blog.csdn.net/f_zyj/article/details/51852672
[Baby-Step Giant-Step]: http://blog.csdn.net/f_zyj/article/details/51867606
[simpson]: http://blog.csdn.net/f_zyj/article/details/51868840
[Link 16]: http://blog.csdn.net/f_zyj/article/details/51869697
[Link 17]: http://blog.csdn.net/f_zyj/article/details/51990803
[Link 18]: http://blog.csdn.net/f_zyj/article/details/51990949
[Link 19]: http://blog.csdn.net/f_zyj/article/details/52001741
[Link 20]: http://blog.csdn.net/f_zyj/article/details/52060317
[1_n]: http://blog.csdn.net/f_zyj/article/details/52131342
[Link 21]: http://blog.csdn.net/f_zyj/article/details/52202169
[Link 22]: http://blog.csdn.net/f_zyj/article/details/52226461
[Link 23]: http://blog.csdn.net/f_zyj/article/details/51869349
[Link 24]: http://blog.csdn.net/f_zyj/article/details/52038871
[KMP]: http://blog.csdn.net/f_zyj/article/details/51694610
[KMP 1]: http://blog.csdn.net/f_zyj/article/details/51714412
[Link 25]: http://blog.csdn.net/f_zyj/article/details/51890509
[Karp-Rabin]: http://blog.csdn.net/f_zyj/article/details/51731098
[Manacher]: http://blog.csdn.net/f_zyj/article/details/51721978
[strstr]: http://blog.csdn.net/f_zyj/article/details/51731423
[Sunday Algorithm]: http://blog.csdn.net/f_zyj/article/details/51888213
[AC]: http://blog.csdn.net/f_zyj/article/details/51891363
[Link 26]: http://blog.csdn.net/f_zyj/article/details/51891641
[Link 27]: http://blog.csdn.net/f_zyj/article/details/51891786
[HASH]: http://blog.csdn.net/f_zyj/article/details/51684263
[Link 28]: http://blog.csdn.net/f_zyj/article/details/51596071
[K]: http://blog.csdn.net/f_zyj/article/details/51607555
[Link 29]: http://blog.csdn.net/f_zyj/article/details/51614197
[Link 30]: http://blog.csdn.net/f_zyj/article/details/51614633
[Link 31]: http://blog.csdn.net/f_zyj/article/details/51622517
[Link 32]: http://blog.csdn.net/f_zyj/article/details/51633836
[DAG]: http://blog.csdn.net/f_zyj/article/details/51651160
[Link 33]: http://blog.csdn.net/f_zyj/article/details/51661397
[Link 34]: http://blog.csdn.net/f_zyj/article/details/51661535
[Link 35]: http://blog.csdn.net/f_zyj/article/details/51675383
[Link 36]: http://blog.csdn.net/f_zyj/article/details/51893624
[SPFA]: http://blog.csdn.net/f_zyj/article/details/51894270
[Link 37]: http://blog.csdn.net/f_zyj/article/details/51902377
[Link 38]: http://blog.csdn.net/f_zyj/article/details/51902621
[LCA]: http://blog.csdn.net/f_zyj/article/details/51902688
[Link 39]: http://blog.csdn.net/f_zyj/article/details/51932110
[Link 40]: http://blog.csdn.net/f_zyj/article/details/51932518
[Link 41]: http://blog.csdn.net/f_zyj/article/details/51933859
[Link 42]: http://blog.csdn.net/f_zyj/article/details/51934309
[Tarjan]: http://blog.csdn.net/f_zyj/article/details/51934491
[Link 43]: http://blog.csdn.net/f_zyj/article/details/51937138
[PERFECT ELIMINATION]: http://blog.csdn.net/f_zyj/article/details/51938352
[Link 44]: http://blog.csdn.net/f_zyj/article/details/51938412
[Link 45]: http://blog.csdn.net/f_zyj/article/details/51938424
[Link 46]: http://blog.csdn.net/f_zyj/article/details/51938454
[Link 47]: http://blog.csdn.net/f_zyj/article/details/51938458
[Link 48]: http://blog.csdn.net/f_zyj/article/details/51938460
[Floyd]: http://blog.csdn.net/f_zyj/article/details/51940779
[2-SAT]: http://blog.csdn.net/f_zyj/article/details/51940914
[Link 49]: http://blog.csdn.net/f_zyj/article/details/60877652
[Link 50]: http://blog.csdn.net/f_zyj/article/details/51944040
[Link 51]: http://blog.csdn.net/f_zyj/article/details/51946807
[Link 52]: http://blog.csdn.net/f_zyj/article/details/51951540
[Link 53]: http://blog.csdn.net/f_zyj/article/details/51959120
[Link 54]: http://blog.csdn.net/f_zyj/article/details/51959671
[Link 55]: http://blog.csdn.net/f_zyj/article/details/51963911
[Link 56]: http://blog.csdn.net/f_zyj/article/details/51964008
[Link 57]: http://blog.csdn.net/f_zyj/article/details/51964166
[Link 58]: http://blog.csdn.net/f_zyj/article/details/51964224
[Link 59]: http://blog.csdn.net/f_zyj/article/details/51967410
[Link 60]: http://blog.csdn.net/f_zyj/article/details/51969719
[Link 61]: http://blog.csdn.net/f_zyj/article/details/51984566
[Link 62]: http://blog.csdn.net/f_zyj/article/details/51986511
[Link 63]: http://blog.csdn.net/f_zyj/article/details/51973368
[Link 64]: http://blog.csdn.net/f_zyj/article/details/51975603
[Link 65]: http://blog.csdn.net/f_zyj/article/details/51975700
[Trie]: http://blog.csdn.net/f_zyj/article/details/51990713
[Treap]: http://blog.csdn.net/f_zyj/article/details/51978699
[RMQ]: http://blog.csdn.net/f_zyj/article/details/51970173
[Link 66]: http://blog.csdn.net/f_zyj/article/details/51970413
[Link 67]: http://blog.csdn.net/f_zyj/article/details/51990962
[Link 68]: http://blog.csdn.net/f_zyj/article/details/51991016
[Link 69]: http://blog.csdn.net/f_zyj/article/details/51478119
[Link 70]: http://blog.csdn.net/f_zyj/article/details/51994846
[Link 71]: http://blog.csdn.net/f_zyj/article/details/51995001
[Link 72]: http://blog.csdn.net/f_zyj/article/details/51995123
[Link 73]: http://blog.csdn.net/f_zyj/article/details/51995402
[Link 74]: http://blog.csdn.net/f_zyj/article/details/51996429
[k]: http://blog.csdn.net/f_zyj/article/details/51996643
[Link 75]: http://blog.csdn.net/f_zyj/article/details/51996716
[0-1]: http://blog.csdn.net/f_zyj/article/details/51996929
[Link 76]: http://blog.csdn.net/f_zyj/article/details/51997116
[Link 77]: http://blog.csdn.net/f_zyj/article/details/51997452
[Link 78]: http://blog.csdn.net/f_zyj/article/details/51999409
[Link 79]: http://blog.csdn.net/f_zyj/article/details/52000180
[Link 80]: http://blog.csdn.net/f_zyj/article/details/52001817
[Link 81]: http://blog.csdn.net/f_zyj/article/details/52001828
[Link 82]: http://blog.csdn.net/f_zyj/article/details/52017132
[Link 83]: http://blog.csdn.net/f_zyj/article/details/52207665
[Graham]: http://blog.csdn.net/f_zyj/article/details/52004769
[Link 84]: http://blog.csdn.net/f_zyj/article/details/52004947
[Link 85]: http://blog.csdn.net/f_zyj/article/details/52060576
[Link 86]: http://blog.csdn.net/f_zyj/article/details/52066759
[Link 87]: http://blog.csdn.net/f_zyj/article/details/52005362
[Link 88]: http://blog.csdn.net/f_zyj/article/details/52005692
[Link 89]: http://blog.csdn.net/f_zyj/article/details/52006321
[Link 90]: http://blog.csdn.net/f_zyj/article/details/52024721
[Link 91]: http://blog.csdn.net/f_zyj/article/details/52025144
[Link 92]: http://blog.csdn.net/f_zyj/article/details/52025425
[Liuctic]: http://blog.csdn.net/f_zyj/article/details/52006790
[Link 93]: http://blog.csdn.net/f_zyj/article/details/51745445
[Link 94]: http://blog.csdn.net/f_zyj/article/details/52040832
[Link 95]: http://blog.csdn.net/f_zyj/article/details/51473493
[strtok_sscanf]: http://blog.csdn.net/f_zyj/article/details/51467905
[Link 96]: http://blog.csdn.net/f_zyj/article/details/51467501