2018年寒假集训

一、时间内容

2018年寒假，学校 ACM 算法实验室。2018年2月18日至2018年3月4日，共计16天，平均每天8小时，约 16 × 8 = 128 小时。

主要以学习算法提高自己的能力为目的，另外要负责17级新生的训练计划安排和辅导工作。

二、体验和经历

刚开始前几天就忙的不可开交，首先是要对17级参加集训的同学根据能力进行分组以适应不同的训练进度。

所以要准备一场分组测试赛，不过由于时间有限题目没有原创，直接用了之前的题目。整体上也算是非常坎坷，由于比赛前没有去实验室测试一下环境，导致501实验室好几天前就连不上网，到比赛当天也没有修复，于是只好紧记处理分配到其他的实验室。

比赛的题目总体上还是不错的，区分度非常好，将实验室划分到了三个组。第一组自然是面向接下来的天梯赛和以后的省赛区域赛的，学习内容主要是数据结构，包含链表栈队列树图论等内容；第二组是程序设计基础学的比较扎实的同学，直接开始学习程序设计下部分的内容（包括结构体链表贪心动态规划等内容），并且在最后学习了数据结构中的栈和一些排序算法。第三组是面向大部分的同学，主要由老师来讲，先进行一段程序设计基础的学习然后学习下部分的内容。

分配任务的时候，自己选了算是比较抽象的动态规划，觉得挺难讲的，但是幸好老师的PPT做的非常详细，加上平时晚上去实验室辅导一下，相信效果应该还可以。

然后就是自己的训练了，主要是比赛和CF训练为主。也算是把自己锻炼到了准紫名水平了。印象中主要学习了概率几何高斯消元。

概率刷的时候发现了一个通用套路，基本上都是用DP的思想去计算概率的，就做题分析方面，我的做法通常是画一颗树型的结构，通过这一次选 a 或 b来分支并计算概率，并通过这棵树发现一些有规律的地方，然后定义DP的状态，找出状态之间的关系，写出递推式并解决问题。大部分时候会发现这棵树有一部分分支是无穷的，举个例子来说：一个人有两道门，其中一道门通往出口，一道门又回到远点，选择一道门并进入要花费A分钟的时间，请问要出去花费时间的期望为多少？可以看出这道题如果画出树型的结构的话有一直出不去的情况，一直留在原地，然后计算这种情况，期望的和是一个变系数的等比数列，然后用高中的知识，等比数列错位相减求和。然后问题就圆满的解决了。

对于计算几何，算是更加系统的了一点。就算不系统的学，那些题也是能做，举个例子从高中以来一直习惯用斜率来表示一条直线，然后这样的话要考虑斜率为0的情况，做数学题的时候计算量非常少，也就是设一两个直线方程，最后特判掉就好了。但是写代码的时候需要一个通用的解决问题方式，做数学的时候只是解决了一个特定的问题，现在是要为一个更加抽象的问题设计算法，所以算法的通用性要优先于易读性。于是考虑用一个点和一个方向向量来表示一个直线更加合理。并且对于判断两直线是否平行用点的点积去计算，用叉积判断两个向量的位置关系等。并且计算几何的一些算法其实很简单容易理解（比起Splay，KDtree这样的数据结构），顺便学习了凸包，实现向量的旋转等，另外这里的旋转其实就是线代里面的一个矩阵，对i，j基向量进行了线性变换。

最后是高斯消元，高斯消元说简单也简单，说难也难，简单的来说，其实就是用矩阵将初中学的多元一次方程组系统化表示并求解。说难的话就是要处理好多的细节，并且一个题要想起来要用高斯消元来解决（这一点可能比较缺乏锻炼，因为之前做的题都是特定的专题里面的），高斯消元具体的来说，就是求解多元一次方程组，或者说是将矩阵化为最简形，求方程组的最大无关组，求矩阵的秩等…一般在代码上会有多种提现，由于计算机使用了浮点数来表示小数的原因，算是和表示整数使用了两种非常不同的形式，所以对于可以接受浮点误差的问题（比如概率期望），可以直接用浮点数去计算。

然后是比赛汇总：

第一场去的是哈尔滨，住了三晚上体验还行，热身赛随便打打的，只切了几个水题，然后热身赛状态算是最爆炸的一次，三个小时才出两个题，本来已经有打铁的打算了，封榜前铜牌倒数第五名。结果比赛完根本没滚榜，然后排名只下滑到了倒数第三，感觉就非常开心了。也算是人生第一块区域赛的牌子吧，不过这次比赛打的是真的惨。

出发前准备的算是挺充分，当时还一直纠结着哈尔滨冷不冷，要带多厚的衣服过去，最后就随便带了几件，然后出发当天去超市买了一堆的东西，给手机缓存了几部动漫（路人女主，末日时，来自深渊，笨女孩…）。得出经验，只需要提前半小时能够到达火车站就好了。

在火车上一晚上看完了笨女孩，然后白天的路上看完了末日时。期间还有打打王者荣耀和斗地主，感觉好颓啊，最逗的是一个别的队的傻子，和我们斗地主积分输成负的时候，就要清理下手机的数据，重新变成1000分。路上还算是挺好的，不过一天三顿吃泡面有点绝望，发现买的零食都不怎么好吃。另外值得一提的就是路上遇到了一个别人家的熊孩子，特别烦。

到了哈尔滨刚下车也不算太冷，在火车站刚下车就见识到了东北的民风彪悍，门卫大爷开玩笑都是 “你过来，看我不揍你！”。然后晚上就搭车去旅馆了，还算是顺利。（不过我们的房间厕所没有门是几个意思啊？！）

晚上一起去吃了夜宵（算是？），没好吃的然后回宿舍订了外卖，发现外卖能直接送到酒店的房间里，体验贼好！

第二天睡到了九点半（晚上终末少女的旅行更新了，然后看了一集），发现步行只需要半小时就到学校了，报名领取发票也挺顺利的，然后在门外的牌子前面合影就去吃饭了。伙食感觉还行，至少有不少肉，能吃饱…米饭给的是有点少。

下午就是一个关于游戏开发的演讲，然后不知不觉的睡着了…

回去的时候就没什么意思了，因为时间问题结果没去成中央大街，只买了点超市里散卖的红肠。

然后第二场紧接着去的秦皇岛，坐的火车居然和去哈尔滨的一样。感受就是这是去过最好吃的食堂，又便宜又好吃。热身赛没有什么印象了。然后正式赛的体验就是感觉在打一场 5 小时的 CF，几乎用不到数据结构。算是非常接近银的一次了，最后 A 题卡住了，没有 A 出了，明明思路和做法都有了，不知道哪里错误…比赛后也是感觉非常可惜，最后算是铜首吧。

第三次青岛站，感觉正式赛的题还没有热身赛有意思，热身赛遇到了一个字典树上维护信息，当时想到了可以这样做，复杂度什么的都证明的很正确，感觉挺爽的，虽然没敲出来，比赛回来就找了一个类似的题补掉了。热身赛算是毫无比赛体验了，前期两个水题，然后一个本来是字符串 Hash 的中档题大家都水了过去，最后三题凭罚时银了…热身赛的时候还是打算先练练手了，最后排名好像是在银牌区，算是认真打了下。最后在想 C 题，突然奇想用线段树的维护信息方式去写字典树，然后好像就可以做了，不过到比赛结束还没有调出来有点可惜，回来的后补掉了一个类似的题。

正式赛惯例还是我来敲签到题，这两场的发挥还算正常，做完签到题能够在银牌区，不过出打印图形的题的时候算是失误了一下，出的比较慢，当时好像在 90 名左右。之后就去看那个字符串题了，按照后缀数组的暴力做法让队友敲了一个半小时才调过了样例，然后我试了下造的大数据，发现 1000 的数据两就差不多 TLE 了，然后就交，这时候我一直在想简单的算法，感觉 A 的人那么多，不可能这么多队都会后缀数组，然后写了一个最差情况下可能 T 的算法，交上去就 A 了。这时候排名 50 左右，银牌是肯定稳了，毕竟一个小时不可能滚上去 50 多个队。最后一小时读了一个题，然后一点思路都没有，最后一个小时算是很绝望了

这场比赛感觉题出的是真的不好，前三题是一点难度都没有，只要手速快点，胆子大点就莫名其妙的前 100 名了，这样随随便便就拿到的名次感觉都对不起平时的训练。不过有银牌还是非常开心的，自我评价我们队的水平也就是介于铜牌和银牌之间。

第四场，CCPC Final，可以说是体验最好的一次了，在哈尔滨待了四天，逛了中央大街松花江教堂。热身赛差点爆零，当时就感觉这场比赛难度好恐怖了。正式赛体验还行，前期水题卡的时间有点长，不过后面中档题出的还算比较快，甚至还冲到了银牌区，不过还没居然卡在了我最喜欢的图论上…查分约束之前都没怎么刷过，感觉很可惜。如果能切掉这个题的话，可能也有银牌了。可以说是打的比较好的一次比赛了，中间和 dalao 们的排名差距很小。

最后是 ECL Final，食堂特别难吃！又贵又难吃，还一点肉都没有！热身赛这次爆零了，体验不是很好。正式赛前期简直爆炸，最简单的水题错了 3 发才过。到比赛中期感觉才上来，连过了几题才到了 100 多名。感觉会做的都做出来了，后面的题是真的心有余而力不足了。这次比赛感觉前面题的代码量太少，只靠思维猜结论…最后也是稳铜了。

感悟

总的来说还是先提升自身能力吧，接下来也没有组队的比赛了，补一下自己不擅长的数学几何之类的。然后比赛下来发现卡的并不是知识点，而是 CF 的那种题，明年之前打上紫名？另外队伍配合的并不好，比赛的时候一种感觉是在两个人打比赛…