博客

现在是2020年9月18日，周五，下午一点钟。我已经上完了一周的课了（除了周日的军事理论），坐在宿舍的电脑前，回顾一周的学习生活，写下这一篇博客。

学习方面

我的选课在正式开始上课前就已经完成，课表上的所有课都成功选上了（因为是按照推荐课表选的233）。我的所有课包括微积分、线性代数、离散数学、程序设计基础、计算机科学基础、信息科学技术概论、还有体育和英语。

我把课表放出来给大家看看：

可以看到，每天要上的课平均只有两门，上课的时间相比高中来说要少的很多，很多其他时间都是可以自由安排的。我一般就选择回宿舍看会书，写写作业啥的。这里肯定有人会问，啊你为啥不去图书馆或者教室去学呢？？？我确实去过图书馆，先不说得预约这一大堆麻烦事，主要是吧，我买电脑的时候买了个游戏本（虽然现在我也懒的用它打游戏），就是巨沉的那种，不仅风扇声音大而且续航还差，不方便带到图书馆去；而且清华的紫荆公寓宿舍是上床下桌的配置，书桌还挺大（至少比家里都大很多），作为学习环境也不比图书馆差。在宿舍里还可以随时问室友问题，有时候大家一起探讨数学问题，氛围还是蛮不错的（图书馆就略显压抑了），所以我其他时间就安排在宿舍学习，这样用电脑也比较方便。

课程的具体内容想必我就不用介绍了，我还是挺想聊一聊我对于课程的主观感受。

首先谈一谈微积分、线代、离散这三门数学课。我个人感觉线代和离散的难度是比微积分低的，线代和离散主要是一些概念性的东西，什么线性映射啊，矩阵怎么乘向量啊，逻辑联结词之类的，也不太难理解。微积分中新的概念性的东西很少，但是更加抽象，特别是取任意什么什么，再存在什么什么，使任意什么什么的，确实是要动一些脑子的，还有各种证明，也需要些技巧之类的。

程序设计基础这门课对我来说应该还是蛮简单的，毕竟高中有学过信息学竞赛，编个程序还是不成问题的。我大概翻了一下全书，基本上都会，可能个别知识点（比如万恶的指针啥的）上课再听老师讲讲应该就没问题。一些基础性的东西同学不会还可以帮同学答疑，正好也能巩固我自己掌握的情况，挺好的。

计算机科学基础这门课我还是想认真学学的，毕竟竞赛也就教会我编程序、写算法，一些计算机底层的运行机制，还有其他模块的内容我自己也不是很清楚。而这课就刚好能覆盖计算机的方方面面，我相信学完这门课后，我对计算机的理解可能会更加清晰、深刻，而不仅仅只是停留在写程序这一层面。

其他课也没啥可说的，按时完成课程学习，提交作业就行，主要时间还是得研究研究微积分。

生活方面

在清华的生活我差不多都体验到了，整体来讲还算是很舒适了，我在下面分别来讲一下我的感受。

与学习和课程最相关的应该就是“衣食住行”里的“行”了吧。我从家里带了自行车过来，所以就算清华园很大，要去哪还是挺方便的。不过有一点让人比较头疼，就是堵车！！！在上课下课的集中时间点，学堂路上就会出现移动速度极慢的自行车海，而且到哪都不好停车，自行车全停满了，很难找到位置。。。

接着讲一下吃饭的事情吧，清华有好多食堂，虽然用餐高峰时间人非常多，但是饭菜口味还是非常赞的！在这里我要表扬一下清华的麻辣香锅！真的特别香！！而且好像哪里都有！！为了能吃到麻辣香锅，排很长的队也挺值得的！

早饭我懒得去食堂吃了，就买了一箱牛奶和一箱华夫饼，当作早餐还是挺精致的，比我去食堂吃的好一些。这样早上从床上爬起来，吃点华夫饼，喝点牛奶，就不用去食堂排队了，直接去教室上课，也挺好。

在宿舍里不想去食堂吃饭，点外卖也是挺方便的，直接能送到宿舍楼底下，下楼去取一趟就可以了。麦当劳、吉野家、赛百味等等的我都点过了，味道很不错，也挺方便的。

既然谈到了点外卖，那么就不得不讲一讲网购收快递了。快递是不给送进公寓楼的，不过在住宿区附近有个快递暂存点，离宿舍楼也算是比较紧，基本上骑个车几分钟就到了。哦对了，考虑到变速车拿快递不方便，我还特地去修车铺给我的自行车装了个篮子，方便拿东西啥的。

在宿舍里洗衣服也比较方便。洗衣机是微信支付的，只要把脏衣服向里面一扔，倒点洗衣液，盖子一盖就能洗，时间到了去收一下即可。每个宿舍房间也有阳台，晾衣服也不需要太麻烦，干的也快。

晚上在宿舍睡觉的感觉也不错，特别是买了床帘后，睡眠环境就变得更好了。床的梯子上我也卷上了海绵垫，这样爬梯子的时候也不会太硌脚。想象一下，学完一天的习，疲倦地往床上一躺，那感觉绝对是非常舒适的~

后记

尽管这第一周有苦有累，但总体过得还是很满意的！在这里我要特别感谢一位素未谋面的同学，她给予我鼓励，与我分享欢笑，陪我聊天，让我开心地度过了这一周。希望我能在接下来的大学时光里继续认真学习，珍惜身边的一切，不留遗憾地奋斗直到顺利毕业，加油！

韵城之都的管家

2020年9月18日于清华园

差不多六点半吧，我醒来了，是被室友的闹钟叫醒的。先是看了会知乎，然后就从床上不慌不忙的爬起来。昨天晚上我已经去超市买好了早上要吃的面包，还搬回来一箱奶，至少早上就不用和广大新生抢食堂了。洗完脸刷完牙，吃完了早餐，室友们已经出发了，我看了眼表，差不多七点四十，本以为八点半上课，后来看了下课表发现是八点上课，急忙跑下楼，骑上车直奔六教。

大学开学的第一堂课是线性代数，在六教楼下好不容易找到停车位的我赶紧跑进了楼，一下子就找到了教室。走进教室，人都已经差不多到齐了，我环顾了一下四周，挑了个稍微靠后点的位置就坐下了。

关于线性代数，老师基本上也只是开了个头。上完线性代数后，该去上程序设计基础了。幸运的是，这个课也在六教上，只不过是要从C区到A区。教室在第0层，我稍微找了找才找到。教室里人也挺多的，好在空座位还是非常容易找到。程序设计基础这课吧，我基本上差不多都会了，主要就是跟着老师再走一遍，基本不存在学习上的压力，这还是得归功于竞赛基础。说到我的信息学竞赛，没去参加全国赛确实挺可惜的，回归到高三后对高考科目也没有直接作用（不像其他几门竞赛都是高考科目），不过此时就凸显出我学过竞赛的优势了。

中午12:15才下课，而下午1:30就上课了。六教楼下全是人，特别拥挤，我尝试往路上移动，却发现路上也全是人和车。好不容易到了食堂，找到了个停车的位置，却看见进食堂的人都排起了队。食堂里面的状况更不容乐观，各个窗口排起了长队，座位也几乎找不到。没办法，只能先排着了。等到了12:50，我才捧着我点的麻辣香锅，艰难地找到了座位，享用我的午餐。

吃完了午饭后，我又得急忙赶往技科楼上思修课。技科楼几乎位于清华园的东南角，我骑着车，横跨了大半个清华园才来到技科楼。好在之前在技科楼开过班会，我就迅速就找到了教室。由于太累了又太困了，我上课一不小心就睡着了个十几分钟，看来下次就得买点咖啡喝了。

差不多3:05下了课，我打算去C楼买程序设计基础的教材来看，顺便去超市买明天早上的面包。到了新民路上，突然堵起了车来（当然这里堵的是自行车），场面一度非常壮观。每个人以秒速五厘米的速度尝试在自行车海中移动。当我通过了这几百米的拥挤路段，前方的道路才终于宽敞起来。

买完了教材，离吃晚饭的最早时间还有一个多小时，我准备去图书馆学一会，顺便熟悉一下图书馆预约座位什么的流程，体验一下。我在馆外扫码，发现二层就有空座位，于是乎预约成功，提醒我尽快签到，否则违约。我刷了卡，进了馆，来到二层。馆内鸦雀无声，每个人都在专心学自己的习，氛围确实很合适。学了差不多一小时，我写完了线代的作业，预习了下之后的章节，翻了翻程设的教材，就赶去吃晚饭了。

考虑到我的电脑很沉，不方便携带，晚上我就回宿舍学习了，整理整理白天所学的内容，再翻翻教材，也挺好。大学上课的第一天确实忙了一点，不过也确实成功度过了。希望之后的大学生活也能充实一些，把知识学懂学扎实，争取能取得好成绩吧。

大概高考完之后，我就有了买一台服务器的想法。

之前的韵城游戏主页（http://app.yczddgj.bid）是用的虚拟主机，只能用来搭个网站啥的，而且不能用服务器，还不能备案，能实现的功能有限。正好高考完了之后偶然听说阿里云的服务器有学生特惠，了解了一下，发现真的很便宜，一年才要九块钱，配置也凑合用，我就买了几年，顺便也注册了个.com顶级域名。

拿到服务器后不知道该干些啥，于是就先搭个博客吧，我用了宝塔面板来管理，也把服务器的环境差不多配置好了，备了案，装了个wordpress，用起来还挺方便的。

其实在这个网站建立前，我就已经在博客园写过一些博客了，主要是关于高中参加的信息学竞赛的一些心得体会什么的。但博客园的博客上可自定义的东西太少，于是我就把这些文章搬到这个网站上了，发布时间也尽量还原当时的写作时间，以后可以再回顾回顾。

这个博客也可以用来记录一下大学生活的点点滴滴，偶尔写一下心得体会啥的，记录一下学习课程的进度，一些感悟，以后也可以进行参考。

希望这个博客可以陪伴我大学四年的生活，并在之后的人生中一直伴我前行。

Day 0

报到去了，拿了一些材料和胸牌，还有一件酷酷的衣服，之后去酒店办入住了，晚上领了参赛的密码条，早早就睡觉去了。

Day 1

正式比赛的第一天，因为抱着已经退役就来玩玩的心态，还不算特别紧张，心想只要别空手而归，拿到奖就好。和同学聊了会天就前往考场了。

我所在的考场是篮球馆，只不过因为考试的缘故，摆放了一排排的电脑。我迅速找到自己的座位后，就翻开了纸质版试题。惊喜地发现竟然有一道提交答案题，看来今天的比赛有得玩了。

先看第一题吧，第一题的题意是，给定一个n*m*l的三位长方体，一个位置是极大的当且仅当该位置上的数，比至少有一维坐标相同的位置上的数都大。现将1至n*m*l这些数填入这个长方体，求恰好有k个极大位置的概率。

拿到这题后，感觉自己有点思路，又好像什么都写不出来，算了，先看第二题吧。

第二题的题意是，给定n个[1,D]的随机变量，求其中至少有m对变量值相同的概率。

怎么又是一道概率题？？不过相比于第一题，这一道题感觉更好做一点，于是花了一小会时间就写出了一个可以拿到48分的O(nD)的DP，发现递推式可以矩阵乘法加速转移，可以多获得12分，先放着，等之后有时间了再写。又发现了m=0和m=1这8分的特殊情况，好像非常简单，就把这8分拿到手了。

第三题是一道提交答案题，题意是，给定n个矩形，这些矩形可以不重叠随意摆放，也可以旋转90度，有两种问题类型。第一种是要求你给出一个范围，以及这n个矩形的放置方法，使得所有矩形都在你给出的范围之内，范围面积越小得分越高；第二种是给定一个范围，让你尽可能多的把矩形塞到这个范围里去，塞的矩形越多，得分越高。

这道题一共十个测试点，都已经给选手了。我先打开了第一个点，发现可以手玩出这个点，于是花了大约十多分钟，把这个点玩出来了，获得10分。

又看到了第四个点，这个点给出的矩形长宽都在一和四之间，给出的范围也是高度为4，感觉把边长出现3的矩形拼一拼就可以了，花了二十多分钟，获得10分。

接下来的点手玩就有点麻烦了，我就写了一个随机化算法跑其他的点。我先将所有矩形随机排序，随机旋转，然后把他们按顺序放入范围中，然后重复这个过程多次，取过程中最大值。

实际使用起来效果还不错，第二个点，第三个点和第六个点各跑出来了9分，第八个点和第九个点分别跑出来了4和5分，第5,7,10个点数据太大了，跑不出来，就0分。

最后总共得了10+10+9+9+9+5+4=56分，感觉还不错，今天就已经有112分了。

最后一个小时又回过头来看了看第一题，感觉第一题要是爆零感觉不太好，于是终于想出来一个30分暴力算法。

最后评测完发现，真的一分没丢，142分全部拿到，感觉考的应该还行？？

Day 2

既然day1考的还不错，那day2就稳一点吧，把所有暴力分拿到就收手吧。

去了综合教室考试，那里的电脑都是内嵌在桌子上的，感觉好奇怪，没见过。

翻开第一题，题意是，给定n条平面直角坐标系上的线段，求把这些线段包起来的最小长度。

糟糕，不太妙啊，一大早上来了个计算几何题，凸包的求法我也快忘了啊，于是我就暴力求凸包，配合状压DP枚举子集获得30分，又写了个随机乱搞上去，希望能得到比30分更多的分数。

第二题是给定一个整数m，以及字符串S，定义一个与S等长，并且字典序小于S的字符串是好串，让你求长度为m的串中，无限循环后存在子串是好串的串的数量。

没啥思路，只能获得10分，直接看第三题。

第三题题意挺长的就不说了，反正又是一道概率题，看了几个小时一筹莫展，获得0分，真的一点分都拿不到，我是不是凉了啊。。。

评测完了，第一题乱搞失败了，就获得30分，其他也一分没丢（就这么点分还能怎么丢啊？？），获得40分。

两天总分182，董哥总分200多。

Day 3

颁奖典礼。

感觉表演的节目效果不错，就是颁奖的时候一个个念名字也太蠢了。得知铜牌线九十多分，银牌线一百四十多分，金牌两百多分，我离金牌只差20多分，感觉d1t3和d2t1能搞出更多分就能金了。董哥有点幸运啊，正好就比金牌线多两分。希望接下来的APIO也能获得不错的成绩~

(后续：APIO2019和APIO2018一样，都拿了个铜牌

Day -4

市里训练的模拟赛，T1压根没看懂题，就先跳过看T2，T2裸的构造，半个小时就搞出来了，写了个正反鸡爪。T3是个限制条件挺多的DP，暴力写炸了，T1一直就没看懂题，不知道出题人想说啥，表示理解不了。最后就T2A了，获得100分。

Day -3

第二次模拟赛，T1题意是一个网格图，让你设定炮塔，炮塔可以选择横着打或竖着打，还有镜子可以反射炮弹，求方案让炮塔覆盖所有空地，且不会互相攻击。好像是个网络流，捣鼓了一会，发现好像不能表示选横着打还是竖着打，暴力只有状压DP有分，还挺难写的，于是跳过。

T2是完全图边权矩阵生成树什么求和，一看就不可做，什么多项式弄来弄去的，可能还得矩阵树一波，不会写，打了40分暴力，收手。

T3是给定一个图，问是否能将边黑白染色，使得黑白边都各自不成环。看完题依然先把暴力打了，发现了一个有趣的性质：只要存在一个导出子图不合法，整个图就不合法。逆命题好像也成立，利用这个性质配合最大权闭合子图写出了拿到95分的错误算法，跟正解仅有一步之差。

总分135，排名还挺高的。

Day -2

第三次模拟赛，T1是给定一个n*m矩阵，求左上角走到右下角经过数的积大于给定数的路径条数。拿到题就想到了一条性质，最多只会乘log次，围绕这个性质想了想，感觉值不会太多，就拿vector暴力转移，本地随机数据感觉快的飞起。

T2是统计路径条数，没想到点分治，就把40分的链写了。

T3是很显然的一个DP，加了点剪枝优化到了n方，应该能拿40分。

总分74，T3数据问题只拿到了34分。不过好像大家T2全A了！？有点丢人。。。第三题好像是什么wqs二分，我也不会。

Day -1

没有模拟赛 ，拿了十二省联考Day1的题给我们做，把T1异或粽子写了调了就溜了，下午听听讲课后就回家了。

Day 1

正式省选第一天，T1是给一个有残缺位的数字串，和一些匹配串，每种匹配串每次匹配都会使当前数乘上匹配串的权值，最后的权值是出现的匹配串的权值的积开总匹配次数次方，输出使最后权值最大的数字串。第一眼就是AC自动机上DP，写了半天突然发现好像转移有点问题，没法维护开n次方，突然想到将权值取对数就变成了求平均数问题，想到自闭也没想出来如何维护平均数，换了暴力DP分交上去了。

T2是什么斐波那契数列和一个神秘数列的组合数区间求和问题，没发现什么性质，加上T1心态有点爆炸，就写了10分就交上去了。

T3是一个网格图，有一些加墙和删墙的操作，询问两点之间扶着墙走的距离，这题暴力就写的我恶心的很，而且就10分，写完了过了样例交上去了。

最后T1暴力获得15分，T2 10分，T3果然暴力写炸了，总分就25分了，感觉凉成尸体了。T1维护平均数只要分数规划二分答案即可，考场上脑袋想炸了也没想到二分答案，想到了这题就做完了不是吗？？如果获得110分就勉强活了。。

Day 2

T1弱智DP，开场AC，本机跑的飞快。打开T2，光在镜子间无限反射问题，高斯消元法n三次方能搞出50分，写完了发现矩阵挺稀疏的能优化到n方，搞到70分收手了。T3从打开题到考试结束都没有想出任何靠谱多项式算法，都被自己hack了，写了7分问号复杂度暴力交上去了。

嗯，还挺稳。。写了177分就拿到了177分。不过，好像T2也是个弱智题，全场AC的那种，高斯消元矩阵稀疏到甚至能线性复杂度解方程，甚至还有更弱智的做法。T3正确的贪心好像能有47分，人均200+，屈辱退役。。看来还是我太菜了。。只能安心搞文化课了（哭哭。。

偶然在知乎上看到的一篇文章中提到了用动态树优化Dinic的思路，遂记录此随笔方便之后学习。

Dinic算法是一个非常优秀的解决网络流模型的算法，然而时间复杂度上界是O(V²E)，有可能会被毒瘤出题人卡掉。

使用LCT可以优化Dinic算法来达到优秀的O(VElogV)的复杂度上界。

我们只需要实现4个操作就可以实现快速增广了。

1、加边：每次增广时加边直到源汇点在一颗树内

2、寻找路径最小值：找到增广路后寻找增广路上余量最小的边

3、路径修改：将增广路上的边全部减少增广的流量

4、删边：删去余量为零的边

以上四个操作用LCT化边为点即可完成。

北京冬令营

冬令营的题是杜教出的，难度很大。我首先花了半个小时理解了一下题意，三道题的规则看起来都很类似，并且难度都很难。既然看不出难度顺序那就按部就班从第一题开始思考。

第一题是给出现有方案问最小改变几步即可让现有方案合法。我首先看了一眼部分分，还是有一些可以拿到的。我先试着自己出了几组小数据，了解了一下题目，尝试着先总结出一些规律，但是确实这一题没有任何规律可言。既然找不出规律那就先写暴力吧，看看后两题之后还有没有时间推敲一下正解。暴力已经打好了，样例调了半个小时，可是确实复杂度太高了，真的是n*m的n*m次方的广搜，但是得分太少了，我准备拿一些部分分再去看后两题，于是我写了一个特殊数据暴力就去看第二题了。

第二题是让你直接构造一组方案，并且合法性判断由加法变为异或了。拿到这题后真的是除了最暴力的暴力一点头绪也没有，打了一个暴力走去第三题了。

第三题是让你求出类似总方案数的值，此时还有一个半小时就结束了，而且这一题的暴力貌似非常好打，于是先把暴力打上，样例过了，然后尝试想正解。这种难度的考试要是A了一道题立马就能前几名了。但是杜教的题哪能这么简单让你A？我耗尽了时间也没能想出一点靠谱的方法，查了查文件名就只好交卷了。

结果我有点记不清了，好像是我拿了两个暴力分，一共30分，也就二十来名吧，省选努力A点题吧。

省选一试

抱着A题的信心步入赛场。

拿到题后立马看到了第三题，树上路径求和，打了多年树剖板子的我立马花了半个小时就打好了，样例一次就过了。心想这肯定正解了啊，复杂度肯定O能过啊，于是写了暴力和对拍保证了正确性后开始攻战前两题。

第一题是给你一个二进制的串，每次两个操作，修改某一位的值和查询一段区间有多少子串在重新排列后是三的倍数。我一想这重新排列其实有关的就是0和1的个数问题，马上打了个表把规律找出来了，那怎么利用规律呢，想到了n三次方预处理，那就是暴力分啊，于是赶紧了一下每次修改O1，每次查询On，总共复杂度n平方级别的，足够拿到前百分之五十的点了，那今天就已经有了150分了。处理完第一题已经过去两个小时了。

第二题是图染色问题，找了一个小时的规律，实在是找不到，于是打了一个最暴力的暴力，期望得分20分。

还有一个多小时，突然想到第一题带修改，查询，那么莫队应该可行！于是我立马开始思考这道题的莫队应当怎么实现。眼看着这题马上就能A了，但是我还是在处理一个细节时发生了问题。原来是变量定义的问题，我应当定义别的意义的变量。修改后开始调样例，调了一个半小时没调过！我这才发现莫队算法在这题的实现上有着致命的漏洞，有一些值是没有办法维护的，我只能放弃了写了一个多小时的莫队算法，交了50分的n平方算法。期望得分有170分。

吃饭时突然想到，第三题貌似树剖是nlogn的，我套的树状数组也带着一个logn，总体下来有nlog方n，最大的点三十万，再乘上题目里的常数可能会T！同学最后算了log方理论上是能过的，但是我蠢了，明明可以O1前缀和维护的，我却没看见没有修改操作而写了一个logn树状数组，当时还想着我还可以把树剖套的线段树改成树状数组常数可能小，简直是有点蠢了。

最后结果下来时，我看到我第三题其实是A了的，这我才放心了。但是下一秒，我看见了第一题的0分，我立马就悲剧了，讲题是我才明白这题细节贼多，而我考虑到的只差了一个细节，正好样例还不包含这个细节，一下50分变0分，悲剧了。第二题也因为图的染色细节丢了第二个点的暴力分，只得到了10分，讲题时说这道题部分分使用特判写的，也是贼恶心，正解也是贼恶心。省选一试就拿了110分，三十名。只有明天A道题来翻盘了。

省选二试

A题说的容易，做出来是真正困难。

拿到题后我惊奇地发现第一题是一道提交答案题！提交答案题非正解就是比谁更能手玩数据了呗。再一看题面，是一道纯种智商题，题意就是两个人猜数，裁判生成两个数，把两个数的积告诉A，和告诉B。A和B只要说了几次不知道就能猜出这两个数。让你出两个数，能让A和B说出指定次数的不知道。看完题我就有想法了，这不就是乘积和和有几种拆分的问题嘛。可惜这题思维含量太高了，我低估了这道题。A和B的思维是互相影响的，就是说A必须要猜到B的想法，而B也要根据A的回答脑补一堆情况。两层我就已经快要想不明白了，最大的层数有15层，那岂不是得和出题人心有灵犀才能A掉这道题啊？于是我把我认为的两层的解打出来了，之后就去看第二题了。

第二题是一道数据结构题，就是给你一条链，每次两种操作，把u到v的路径上的值都加上d和查询长度为l到r的路径的和的和。一开始我想用线段树维护维护，但是这个想法立马就被我否决了，每个点对于l到r的加权不一致，且每次询问的l，r也都不尽相同。要是真用线段树维护，那也得建n个线段树，空间时间保准爆炸。于是我先打了加了预处理每个点对于每个长度的加权，最后查询时On处理，总复杂度n平方，能拿到40分。我先去看看第三题。

第三题是一道期望题，期望题我做的不是很多，处理方法也只是略知一二。我开始研究这道题的概率DP方程。经过一个小时的奋战，成功推出了式子。既然推出了式子就可以尝试A掉这道题了，于是我开始展开这个式子，突然发现fn是关于fn+1到f0的，就是这些式子之间不能用递推来算f值。我又突然落入迷茫之中，既然无法递推这个式子，那么我不但写不了正解，连暴力都很难打出。我一直在想这道题暴力应该如何打，但就是因为这些式子互相影响，就算记忆化搜索也是无限递归下去的。但是这道题总不能不做，我开始对n小于等于3的数据每一组进行手动计算，也就2*2*3*3=36种。大概算到五六种时，突然发现我这就是在浪费时间！真正要算完全部36种结果两个小时也不为过，我急忙写了一些特判就关掉了第三题。我应当考虑如何在我现有的水平下拿到更多的分。于是距离结束还有一个小时的时候，我又重新关注了第二题的大数据部分分。其中确实有一些简单就能拿到的部分分，拿了大约10分左右的部分分，检查了文件名就交卷了。

第一题智商题我明显对于某些情况讨论错误，40分两层的分数中我只拿到了12分，而第二题是最坑的，由于是一条链，我就直接拿线性结构直接维护了。但是路径上的两个端点可能是逆序的，你需要swap一下即可拿到40分。于是第二题我只拿到了特殊数据的5分，只能说在今后的学习与竞赛过程中再长点记性吧。第三题我的特判就是完全失败了，屈辱爆0。讲题时我才知道这一类期望题的暴力是可以拿高斯消元法来解式子的，只能说我还是太年轻了。

总结

其实这次省选我的联赛分数并不突出，再加上缺乏对于真正难题的思考，这次省选我就屈辱滚粗了。希望在2018年还是要多刷题，见识多了，做题的方法才能显现出来。下次联赛和省选还是努力吧，争取明年光荣进队而不是屈辱滚粗吧。

在竞赛过程中一个对拍程序可以帮你排除许多错误，如果担心自己写的正解被一些小数据卡掉，我们通常会写个对拍程序来检查正解的正确性，通过大量数据观察正解与暴力的输出是否相同。

我们首先拿出我们写的可能会超时但是可以保证绝对正确的暴力程序，称作bf.exe，然后拿出我们写的待检测的正解，称作std.exe，接着我们写一个随机数据生成程序，用来一次生成一组自制随机数据用来检测输出，称作gen.exe，

然后我们来写一个利用windows批处理的对拍程序。在你的程序的根目录下新建一个称作check.bat的文档，用编辑软件打开这个批处理文件，添加如下代码：

@echo off
:loop
gen.exe > data.in
std.exe < data.in > std.out
bf.exe < data.in > bf.out
fc std.out bf.out
if not errorlevel 1 goto loop
pause
goto loop

第一行echo off作用是关闭多余显示，这样可以只让对拍程序显示对拍信息。第二行loop作用是循环，一直进行下面的操作。大于号代表输出重定向，可让运行的程序的输出结果输出在特定的文件中。小于号代表输入重定向，可让运行的程序从特定的文件读取输入信息。第六行fc操作代表对比两个文件，结果会显示在控制台中。第七行代表如果没有拍出错误就再返回第二行loop进行下一次对拍。第八行pause就是c语言中sysem(“pause”)的操作。第九行可以在pause之后进行第二轮对拍。

写完了这个批处理程序就可以保存退出运行对拍了。

祝大家在竞赛中拿到好成绩！