算法竞赛竟有如此魅力——Markyyz退役记
去年打完ICPC杭州站就想写退役记了，但一直懒得写。可以说的实在是太多了，而且无法按时间顺序叙述，我尽量写的有条理一些。
〇、杂谈
算法竞赛吸引我的点在于趣味性、专业性、公正性。
趣味性：学会某个算法后，非常具有成就感。每当看到Accepted的那一刻我都会感到无比的喜悦，而这种喜悦我已经体验过2000多次了。
专业性：学习内容与专业强相关，竞赛并非应试，考察专业能力，需要重要的编码能力和算法能力。
公正性：纯机器判题，没有任何主观因素，赛场上所有选手处于完全公平公正的竞赛环境，三个人一台电脑，完全正确就是Accepted，部分错误就是Wrong Answer，超时就算Time Limit Exceeded，超内存就算Memory Limit Exceeded，运行时错误就算Runtime Error。这里就不提大家都知道的三人三机、获取并提交逐字符相同代码、厕所战神等事件了。我校向来严格要求自己，对作弊行为零容忍，一旦发现任何作弊，开除出集训队无商量余地（亲眼见证三例了），同学互相之间也有监督，哪场codeforces/比赛打得不正常，总会有学长学姐、教练的眼睛盯着你。
刘春英教练一开始就说，打ACM的结束了要叫退役，因为和别的竞赛不一样，XCPC需要你花的时间必然是用一年两年三年来计算的，而不是几个月参加一下。从入坑到退役，我向着ICPC区域赛奖牌的目标，一刻不停地学习。我为之付出的是我大一大二几乎所有的课余时间，我不参加任何校内的课余活动，不参加任何社团、学生工作，不出校玩耍，几乎不聚餐。高考前都每天想玩一会儿游戏的我，也完全没有了玩游戏的兴趣。每天从早到晚只要有空，就在刷题，特别是大一上学期，为了快速入门，我每天上课（非重要的课）、下课、午休、晚自修都在刷题，周一到周五一天6小时起步，周末更是早8到晚10。
我只是想说明我是这样的，并不是推荐大家都这样，毕竟人是要休息和社交的，每个人的精力状况都不一样，一天内的过度学习也会导致第二天的精神不足，大家要选择适合自己的节奏。我的两位队友入坑没有我这么快，也照样能学的很好。
我之所以一上来就这么努力地学习，是因为我能看到自己和其他人的差距。我的竞争对手不仅仅有校内的几十位OI省奖、省队、国家队的选手，更多的是全国各大高校的强队。试想一下，一场区域赛一两百所高校，每所高校派出一支甚至多支强队，赛场上有几十个OI高手队，数百个努力了1~3年的大学零基础队伍，ICPC金牌需要rank35，银牌需要rank105，铜牌需要rank210，能报名的队伍大多都你一样经过大量训练，你怎样才能打出前排的rank？自我感觉良好的时候，一上赛场，看到别人遥遥领先的题目数和罚时，就能体会到自己和别人的差距。
我自认为是很有竞技精神的人，心态良好，不管是打电子竞技还是算法竞赛，比赛必坚持到最后一秒。哪怕我知道你比我强很多，我也要尽全力咬紧比分，就算我们都正常发挥，我不可能战胜你，我也绝不允许你有放松和大失误的机会。而人不像机器，经常会有失误，一旦前面的人有一部分发挥失误，那么机会就来到了我的手里。
在暑假前，我认识了我的队友并组队。老刘说组队就像自由恋爱，互相要认可对方的水平，比赛需要配合，但是没有个人实力，就不要谈配合。我们组队前都不认识，组队后还算比较配合得不错。能够和一群志同道合的同学一起向着目标努力，简直就是梦幻一般的幸福生活。
我们队伍几乎没有过合照，几乎没有聚过餐，除了群里讨论题目、VP、正式参赛，就没有一起干过别的事情，除了上面这张退役后特意拍的，其他合照都是OMS监考系统赛前认证。。。
当时我们讨论了队名，讨论了风格，是霸气风格（如“逆十字”、“杀戮降临”），还是蒟蒻风格（如“重生之我是菜狗”），后来选择叫做”HDUNchar66“
队名的解读：HDU=杭电，Nchar=牛叉，66=玩得溜，char66='B'，Nchar66=NB。并没有采用三人英文字母组合，是因为不知道如何组合三人的字母。大小写+数字整体形态较和谐。char66带有专业性双关，且队名具有一定的娱乐性，符合比赛的风格。
一、入坑过程
2020年9月14日报道杭电，第一周考进计科实验班，认识了ACM学长班助以及OI选手SGColin，被他们成功带入坑。虽然从未参加过任何竞赛，也一直都不喜欢竞赛，但我刚接触就对此非常感兴趣，便开始快速入门。9月18日还是什么时候，我成功通过了hdoj的多测A+B（当时还是记事本编辑C语言）。我加入了新生群，认识到了校内竞争的激烈，在入学第二周就从早到晚刷题上手。
9月28日，我第一次参加codeforces Div3，AC了两道题
这是10月1日入学两周的刷题量，我深知笨鸟先飞的道理，只有充分利用每一分钟的时间，才有可能弥补我和OI基础同学的差距。大一第一学期我没有早八，我每天早上7点多起床，买了煎饼回来写题，写到9：40去上课，11：35或者12：25下课后，买了煎饼回来边吃边写题，写道1：15去上课，4：00下课了回来些题，吃个晚饭再去晚自修教室写题，8：50晚自修下课回寝室继续写题。周末更是有可能早8到晚10。数学分析+高等代数正常听，水课写数学课作业，C语言课课上AC掉作业题边听课边写题。
国庆假期我学了背包DP和dfs/bfs，休息了一天。又过了一个月，下图是截至11月1日的刷题量
新生ACM选拔赛3题rank28，教练要求4题进队，我成功落选，但我知道第二轮选拔必能进，果然不出所料。下图为第二次选拔赛，我给这张图起名为《树形充电》，我的插线板是图右下角的根节点，好在质量不错。
看到名单中的50人里有30信奥得奖者，我更是加快了脚步。经过了大一下半学期的多轮pk/淘汰赛，codeforces分数以及校赛成绩，这一届留下了20多人，我作为零基础仅剩的8人，成功留在了集训队。而暑假集训过后，作为校内排名10/14的队伍，获得了参赛资格。
二、学习过程
基础：高中浙江选考技术，有VB基础，会冒泡、选择、插入排序，其他啥也不会。
大一9月：刷C语言基础题、前缀和/差分、 线性DP
10个月：背包DP、dfs、bfs、栈、队列、二分答案
11个月：并查集、kruscal最小生成树、单调栈、单调队列、归并排序、floyd最短路、质因数分解、埃拉托斯特尼筛、乘法逆元、快速幂、矩阵快速幂、组合博弈
12个月：树状数组、邻接表、堆优化dijkstra最短路、线段树
寒假：LCA、Trie树、可持久化线段树、状态压缩DP
第二学期：01Trie、可持久化01Trie、轻重链剖分、扩展欧几里得算法、（扩展）中国剩余定理、线性筛、欧拉函数、树形DP、区间DP、二叉堆、ST表、二分图最大匹配、平衡树入门(Treap)、生成函数、差分约束、Tarjan（SCC/EDCC缩点）、2-SAT、高斯消元、KMP、数位DP、FFT、Dinic最大流、SPFA最短路、Edmond Karp最小费用最大流、线性基、AC自动机
暑假：计算几何基础、极角排序、凸包、线段树优化DP、cdq分治（其实现在都不会）、树上启发式合并、点分治、整除分块、线段树合并、splay
第三学期：树套树、旋转卡壳、计算几何更多的基础，仙人掌圆方树
寒假：后缀数组、长链剖分
第四学期：LGV引理、狄利克雷卷积、莫比乌斯反演、kruskal重构树、扫描线、笛卡尔树、线段树上二分、虚树DP、（广义）容斥定理、可持久化并查集、可撤销并查集、字符串哈希、kruskal重构树
暑假-第五学期：后缀自动机、manacher、回文自动机、线段树分裂、link-cut-tree、杜教筛、min25筛、矩阵树定理、数学/计算几何/博弈/数据结构/图论更多内容
我整理了一份184页7800行latex源码的算法模板，总结了我们队的所有科技，当然这也只是表面的东西，真正重要的是我们大量训练后掌握的灵活的解题思路，算法模板只是偶尔需要抄一下的东西。
我的刷题量：codeforces、hdoj大量专题训练和杭电多校比赛没有计入账号、牛客41场比赛大多没有记入账号，还有PTA的很多题，总计大约2000题，现在看起来大部分是简单题，但做的过程中，对当时的我来说都是很有难度的。
做过的最难的几个题（部分）：
1、洛谷P6292 区间本质不同子串个数 https://www.luogu.com.cn/problem/P6292
询问离线后link-cut-tree在SAM的parent tree上access，用线段树更新、查询区间贡献
2、codeforces 487E tourists： https://codeforces.com/problemset/problem/487/E
无向图点双连通分量缩点，建广义圆方树，multiset维护方点最值，树剖线段树维护/查询链上最值，
3、#572. 「LibreOJ Round #11」Misaka Network 与求和 ： https://loj.ac/p/572
莫比乌斯反演后整除分块HashTable记忆化杜教筛套min25筛
在此还要特别感谢刘春英教练、SGColin、ZigZagK、Comld、DDosvoid，以及所有帮助过我的同学，没有他们的帮助，我也很难有那么高的学习效率。我还没写过博客，因为一方面觉得不需要整理，记在脑子里才有意义，另一方面也没时间和心情写。有几位同学的博客内容非常丰富，在此附上他们的博客链接。
SGColin：http://blog.gyx.me/
ZigZagK：https://zigzagk.top/
Comld：https://www.cnblogs.com/ZH-comld/
DDoisvoid：https://ddosvoid.github.io/
三、参加过的训练赛和非XCPC比赛
codeorces round 116场，大一几乎全勤，晚上22：3500：35是熟悉的时间，codeforces virtual participation三四十场各地区域赛，参加其他学校校赛若干
校内比赛：自动化学院新生赛（入学两个月学了矩阵快速幂后刚好考到，喜题一等奖）、校新生赛（三等奖）、计算机学院debug杯、两次校赛
多校集训：两年各10场牛客多校、10场杭电多校，杭电多校在暑假的每周二、四，牛客多校在暑假的每周一、六，两个暑假实际放假时间大约一星期。大一暑假后，我们队的校内排名是10/14，大二暑假后，我们队的校内排名是4/14
团体程序设计天梯赛：大一250，大二220，大三237（总分相等难度不等，大三打的最好），本想最后一战抢下先锋，赛前一周板刷了100多道天梯赛的题，赛场上前半段确实发挥的很好，20分钟AK了L1，1小时AK了L1和L2，可惜L2没有抢到一血，而L3又卡太久了。
蓝桥杯C++软件类大学A组：大一省一（国赛和校赛冲突，放弃参加国赛），大二国二，实力确实差点，现在看来的简单题当时都不会，国赛还是很难打的。
CCF CSP等级认证：500分，杭电刚设立考场，我参加了第一场就AK了，运气真好，压轴题考点恰好和我一周前训练过的HDOJ 6967（I love data structure，2021杭电多校集训）一样，线段树维护线性变换矩阵乘法tag先乘后加，花了一个多小时成功秒掉。
某个国家级的比赛：和室友一起参加的夏季赛，当时确实实力不够，树上SAM板题不会做，又不搜题，差一题，喜提银奖。毕竟参赛的大部分人在群里讨论、搜题、换题，反正没有人管，div1E tourist大神都没有做出来的困难网络流原题被500多人AC了。
2023杭州师范大学校赛：这是我唯一参加过的线下赛，也是我们的省赛选拔，我们队三线卡题，成功排名校内倒数第一，正好也想退役了。我拍了一些视频，但是一直没空剪辑。
我们负责了2023年的校新生赛和计算机院赛的出题，我接下来估计会为今年的杭电多校集训贡献两道（不够难的）题。
四、参加过的XCPC正式赛
2021年CCPC威海站铜奖：
大二第一次参赛，感觉差距非常大，好在签到成功签上，KMP成功签上，惊险地拿下铜奖。
2021年ICPC澳门站铜奖：大二下学期教练又给了我们一次机会，可惜极角排序精度炸了（使用了atan2没用整数向量叉积）、FFT精度也炸了（没有预处理单位根，或者没有改用大模数NTT），两题卡死。可以说是学得不够精，网上找学习资源需谨慎，遗憾获得铜奖。
2022年浙江省大学程序设计竞赛金奖：成功签到6题后，两个金牌题主席树+计算几和构造，我各写出一个惊天bug，好在队友一人帮忙debug出一个，最后半小时AC两题惊险拿下金奖
2022年CCPC威海站银奖：
前期找规律题卡太久，罚时过高，时间也不够，最后一题差一口气，但就算AC也是银，感觉CCPC太难啦
2022年ICPC西安站金奖：
轮流上机切签到题，一小时一发AC了6个题，再花3小时通过2个题，罚坐一小时后喜题金奖。特产很香！
2022年ICPC杭州站银奖
签到过的稳健，可惜中档题卡了两道，考到了我们都不会的东西，喜题银奖。知味饼礼真的很好吃！
五、经验分享
1、保持良好的健康状态，才能有力气高强度学习。保持阳间作息，多运动。
2、多刷题，刷题量是最能代表水平的。感觉没有提升？一定是没好好刷题。不知道怎么快速上手？先刷50题吧。学了感觉不会用？再刷到到感觉会了为止。建议一开始广泛学基础算法，有一定基础后可以继续深入。当然一直刷简单题没有任何帮助，必须不断地AC自己原先不会做的题。
3、参加各种训练赛，可以挑选喜欢的参加，例如codeforces、atcoder、牛客训练赛、洛谷训练赛、各大高校校赛等。通常来说正式ACM训练赛的考点较广，质量高，能帮你找到盲区。赛后一定要补题，哪怕补一题或者只看个思路，不补题就没收获，等于没参加，浪费时间。
4、建立抽象思考能力，学习某个新的算法时，通常需要举个具体的例子，但是你需要从例子中获得算法的抽象思维，即对于任意的情况，该算法均能处理。算法可视化也是很有助于理解的，可以看一下网上的视频，但也不能依赖于别人做得很好的可视化，你可以尝试在脑子里“可视化”。例如：考虑使用线段树时，我的眼前仿佛出现了一棵线段树，需要处理更新操作的时候，眼前的这颗线段树从根节点向下的两条链不断地在变为高亮；考虑到拓扑排序时，我的眼前仿佛出现了一个具有一般性的DAG，且眼前的这张DAG正在进行拓扑排序，结点上的数据正在从一个传向另一个；考虑使用splay树时，眼前的一棵二叉平衡树正在把一个结点伸展到根。
5、掌握算法的通用性。学习一个算法并做了一个题时，你学会了用算法解决这个问题，刷了5个或者10个题后，你应该学会的是对于相似的问题，可以考虑用这个方法解决，而非仅仅用该算法解决这5个题。讲一个反面教材，我的一个室友思考问题的方式是这样的：“这题能不能用LCA解决？这题能不能用拓扑排序解决？这题能不能用最短路解决？”这是非常错误的思考方式，对于一个特定的问题，你如果不能直接联想到一些可能有关的算法，那就说明你并没有真正掌握这些算法。
6、锻炼自学能力，打ACM几乎完全靠自学，网上资源很丰富，题解、博客等优质学习资料应有尽有，足够学习的。
7、算法竞赛需要你对算法有足够的兴趣。别人学习ACM是吃苦，我学习ACM是享受，别人学完需要玩游戏，我学习就是玩游戏。学弟跟我说“学ACM痛并快乐着”，我觉得是这样子。一开始确实学的比较吃力，但有一定成效后，你就会觉得这些付出都是非常值得的，而且训练到后面，参加训练赛/正式赛，就像是打了一把游戏，非常有娱乐的感觉。
