2017年暑假集训

一、时间内容

2017年暑假，学校 ACM 算法实验室。对一个月集训的总结，也算是应付一下学校的社会实践作业。时间为7月24日至8月26日，总共五周34天。

时间差不多是早上8点就得到实验室，不过这次不像寒假集训那样每天要签到，结果日常迟到，刚开始几天还好，之后都是迟到个10几分钟…

老师对集训的安排是周一至周六全天训练，周日休息一天，除周二以外每天上午自己去刷专题学习算法，下午就进行组队赛，周三是一天都是学习算法和补题。周六是上午+下午两场个人赛，一周下来总共六场比赛，除去个人赛三个小时外，每场比赛都是5小时，训练强度可以说是挺高的了。

二、体验与经历

这里就以时间为顺序写一下集训的趣事和重要经历好了。

我是在集训开始前几天就来学校刷了一会专题，搞了搞数论，算是弄懂了逆元、中国剩余定理、扩展欧几里得算法…对于基本的数论题算是没问题了，然后对数论不像之前那么怕了，讲道理我到时非常想仔细研究一下数论来着，毕竟算是数学中的皇后、最纯粹的数学了，然而图论真的是太有意思了～

然后过了几天就开始正式集训了，刘老师首先开始讲话，看参加集训的人数，大概有个100+人，看刘老师说是分算法组和数据结构组两部分，算法组的基本上就是面向比赛的集训队队员了，数据结构组，看刘老师的意思是想要把我们学校整体的水平提高上来，整个计院差不多700人，这样相当于有个1/6人都在大一结束的时候就完成了数据结构的学习，如果进展的好的话，可以说是非常恐怖了。

对于数据结构组我不太清楚，刘老师说了一下对算法组的安排，就是上面说的那样了，然后张老师在 VJ 上抓了 kuangbin 的专题，算是我们学习的大纲了。

接下来防不胜防的，刘老师说要开一场个人赛，算是让我们找到状态，当时就整个人就方了。

然后第二天上午就开始比赛了，由于过去一个多月了，记得也不是太清楚了，反正刚开始就是一堆的水题，唯一用到数据结构也就是单调栈和线段树，当时状态还不错，不过单调栈看了紫书才敲出来 ORZ 。最后 A 完7题后，就在看一个类似约瑟夫环的题，刚开始还以为是一个纯数学题，不过之前刷了很多的线段树的题，然后用朴素的思想想了一下，维护下标这个信息，突然发现用线段树可以搞，于是最后半个小时就非常开心的敲起了线段树，不得不说金桔的线段树的板子真的好用，然后自信的交上去，给了一个 Wrong Answer，然后比赛还有不到十分钟，本来没怎么有希望了，然后又去查了一下代码，区间更新 lazy 标记直接覆盖掉了，没累加，改掉之后交上去居然 A 了，非常开心，这时候也就五分钟了，于是和后面机位的 xuanhuang 聊了起来。开始第一场比赛 AK 可以说是非常开心了。

比赛结束后，就是日常的训练了，不过刚开始我们队比赛状态并不怎么好，经常前两个小时 A 完题，就咸鱼了，三个人坐着没事干。

然后就是每周的个人赛了，第一周的搜索算是非常开心，自己本身刷紫书的题的时候做了不少的搜索题，底子算是还可以，然后印象比较深的时候是一个题从 TLE 加剪枝优化，慢慢调成了 AC，非常开心，两次排名都是 Rank1。

组队赛的时候，非常幸运可以参加多校赛，也算是去见识下区域赛的题型，发现数学题居多，上来就是莫比乌斯反演、矩阵快速幂、快速傅里叶变换、卷积…刚开始打的一脸懵逼，感觉也就是做前几到简单题就尽力。然后感觉对于区域赛，感觉也只能思维活跃一点，把直接力所能及的题，做出来就好了。然后区域赛尽可能去拿一个铜牌甚至是银牌，如果是银牌的话，那就非常稳了，整个大二就可以平稳的去刷金牌题和知识点了（幻想ing）。

之后几个周都是一样的安排，整天不是刷题就是比赛，非常单调，值得一提的是最短路的测试赛又体验了一下 AK 的感觉，感觉自己对最短路理解也算是比较深了。

集训前几天一直在搞图论，先去学了下网络流，裸的 FF 算法， EK 算法， Dinic 算法都看了一下，网络流专题也算是刷了一半。感觉网络流算是图论里面一个比较重要的知识点了，之前区域赛的网络赛中经常有网络流的题。刷网络流的时候顺便去看了一下二分图匹配的问题，感觉匹配这个东西有点神奇，好多看起来和图论无关的问题，都可以转化到二分图的模型上，然后跑最大匹配就能解决好多问题。

之后因为实验室要开算法讲堂，然后就被叫去讲强连通缩点，于是用了一个星期咸鱼突刺了一下，算是弄清了强连通、边-双连通、点-双连通，然后就开始填算法讲堂的模板了，反反复复修正了得一两天，最后填的也不怎么样，等学离散数学的时候，一定要好好在图论上扩展一下！

最后只能就这样将强连通了，感觉讲的算是比较失败的了，没学过的估计没听懂，学过的也基本上不用听的。对比之前学长讲的树链剖分，当时我只看卿学姐的视频学了一下概念，然后听学长讲的居然听懂了，然后拿着板子去切了几个题，也算是会基本的树链剖分了，其实树链剖分实质上就是一种映射，目的是将一条链上的点映射到若干段连续的区间上，然后对于链上的修改，就对这几段连续的区间进行修改，对于连续的区间修改可以用线段树进行维护。于是这样树链剖分的题重点还算是在线段树上。

其他有意思的事情就是被派去辅导数据结构组的刷题了，然后发现他们是在做的 CCCC 的题，之前天梯赛训练的时候刷过的，然后给一个同学讲了一下树的同构的判断，发现直接好久没写过的指针了，我本以为给他写一个指针的比较好理解来着，最后写起来发现数组的好些太多了。另外一个就是看了一下目录树，之前在白书上面看到过，上面说的是静态排错，手写一个简单 shell ，也算是一个大模拟题了。看起来还是比较容易，记得天梯赛的时候，这个题曾经水过了20+分。

最后就是结训赛了，其实也都是比较水的题，大家都当做娱乐来做的，其实也挺娱乐的，最开心的是做出来了一道区域赛的 DP 题，感觉还可以，最后罚时有点多Rank2，还可以。

三、一些感悟

一个多月以来，基本上都是自学算法，学习新算法也是自己去百度找资料、翻书，比起之前集训都是学长来讲内容，感觉自己的自学能力算是提高了不少。学习能力也是提高了不少，比如匈牙利算法，当初只用了一上午不到，就学完并刷了好多例题了。

另外一个重要的提升是，最近比赛的时候不再像之前那样，每次前两三个小时做出来题，之后就没事干了，现在基本上五个小时都在看题，尤其是最近一场比赛，前三个半小时都是爆零，知道三个半小时后才切掉了第一题，之后半小时又切了一题，最后十分钟队友又切了一道 KMP 的题，顿时咸鱼翻身。

之后也是打算继续搞算法竞赛，目测会打到大三吧。