@

GDKOI2021 爆炸记

前言

害，我果然还是好菜。

不会的照样不会，会打的还因为一堆奇奇怪怪的问题错了一大堆。

普及（Day 1~3）

Day one

比赛

拿到题目先看题。

第一题看了一下，第一样过去人都蒙了。
啊？这不是普及吗，怎么一个表的函数的呢？
然后仔细看了几眼，发现只要简单模拟一下然后分类讨论就可以了。

第二题，看到题目暴力很容易就出来了。
然后想了想发现要快速求一个点左边比它高的一个和右边比它高的第一个。
然后想了想没想到有什么算法。

第三题，想了一会，发现它的数据 \(n\) 到了 \(1e6\)，而且觉得有点贪心，但是还没有完整的想法。
然后想了一下，就去看下一题。

第四题，一开始看了一会发现了一定是拿全部钱去买通行旅票的性质，然后就陷入和每次都要跑一个图会超时的思考。
然后就滚去先敲第一题了。

然后看题大概看了 \(15\) 分钟左右。

然后先去搞第一题，因为思路完整，很快就写出来了。包上检查细节，大概用了 \(20\) 分钟。
然后先去写第二题的暴力，就直接枚举两边第一个比它高的位置，然后前缀和算空间大小。大概用了 \(20\) 分钟。
然后第三题还没有思路，就先去打第四题的暴力。然后打完暴力想了一下，发现可以离线处理，想弄最小生成树的样子，边按权值排序，然后依次处理出答案。
（这个时候大概是过了 \(70\) 分钟）

然后就去写，大概又写了 \(20\) 分钟，就写出来了。

接着去想第三题，想了想，想到用最大加最小，然后具体的贪心方案也想了出来，就打。
因为比较好实现，弄个 \(10\) 分钟就弄好了。

接着去看第二题，做的时候一时间忘记了可以用单调队列找序列中第一个比它大的数，然后想来想去，最后用了二分+线段树来弄。
然后这里大概又搞了二十分钟左右。

然后全部打完了，就开始对拍。
首先觉得第一题这么好弄是不是哪里有问题，就去弄第一个题的对拍。
这题的对拍也是最好弄的，在生成随机数据的时候就可以先生成一个正确的，然后随机一个位置作为答案，然后改一下即可。

结果我比赛时忘了生成随机种子是 srand(time(0))，傻乎乎的一位是 random()，然后就只能只能通过数据数组这个值过掉一些数，然后弄成随机的样子。

然后在拍第一题的时候就去弄第二题的对拍。
因为一开始打了暴力，就也很快弄好，就把第一题的对拍停了排第二题。
注意，我这里的对拍没有看时间，只是看答案。

然后拍第二题的时候就去弄第四题的对拍。
（因为第三题贪心完之后实现很简单，而且暴力也不知道怎么打，就直接不对拍了）
之前也是打过暴力，也很快弄好。

然后我就三个对拍轮流跑，一直到比赛结束。

赛后聊天

LYF 第二题用的是堆，然后一堆人全部用的算法各种各样。
还说我的线段树常数很大，不知道能不能过。

然后第三题的贪心跟一堆人对了应该是对的。

下午讲题

T1 分类套路，我的没问题。
T2 结果是用单调队列来搞，就不知道我的线段树加二分能不能过。
T3 贪心证实了是对的。
T4 离线没问题。

然后内心疯狂祈祷第二题能过。

下午讲课

讲数论，很多内容。
我拿个草稿本不停记笔记，草稿本上没位置写了就跑回去拿个笔记本继续记。

然后现在正在整理，到时会有一篇博客出来。

晚上

出成绩了，\(340\)。
（\(100+40+100+100\)）

LYF 和 LXY 两位大爷反手就 AK 了。

第二题超时了，然后我才发现我打的对拍一直都没有看超时。
然后就去跟 LYF 这个神仙的代码对拍。

然后发现有的时候我确实会超时。

然后 LYF 大爷看了一眼我的代码，说：“你怎么不用快读快输呢？”
我：“哦！c！是哦！。”

然后我加了个快读快输之后，它跑得飞快。
。。。
我直接哭死。

Day two

比赛

听说题目难度会变高，感觉要凉。

拿到题目先看题。
第一题看到有点慌，然后想了一会觉得应该可以找每个数循环起来之后最后一个数的周期，然后最后把每个数轮到的周期数乘起来，就可以得到最后一位。
第二题想了一会，感觉思路有点混乱，不知道先约束哪个条件，然后就跳去看下一题。
第三题看了一下题，发现就是走树上的链。然后又是距离，然后直接跑又过不了，然后就想到了用倍增。但是具体怎么实现还不是很清楚，就去看下一题。
最烦的构造题目，看着题目一脸懵逼。看半天也没有想法，就先做题了。

看题大概都看了半个小时，人都傻掉了。

然后去弄第一题，打完结果发现样例都过不了，自己的想法是错的。
然后就更加慌了，感觉自己今天要爆蛋。
然后调试了一下，发现 \(2\) 和 \(5\) 乘在一起会一一消掉。
然后改了一下发现还是过不了。

然后又发现其实可以把不是质数的数拆开，然后只剩下 \(2,3,5,7\)，二和五再消掉之后再按末尾规律乘起来。

然后过了样例，自己出了几个小数据也过了，就去弄下一题了。

然后先去弄第三题，先正常的弄个了树上倍增。然后想了想，因为要弄距离最小值，我们可以弄到根距离的最大值最小值，然后分类讨论一下乱搞，然后就试着打。
但是因为比较混乱，打出来的也不知道对不对，过了样例和自己出的数据就走人了。

然后去想第二题怎么搞，想了很久，想到一个方法，就是先按正则二叉树的规定建树，然后再看是否是正则二叉树。

然后去看第四题，一脸懵，只会瞎搞，搞了个全部都是 \(1\) 和行列和为 \(2\) 的情况，还不知道会不会有锅。

赛后聊天

第一题对了一下大家都差不多。

第二题大家算法各有不同，问了一下我的算法，才突然想起来最后没有判断是否是 bfs 序，然后就贼慌。

第三题大家似乎都是用倍增，但我思路糊成一团，应该都是没有分的了。

第四题好像说可以把图转化成只有 \(0,1\) 的，然而这样我还是不会做。

下午讲题

第一题没问题。

第二题好像是一个神奇的算法，弄成很多棵树，然后一个一个看放儿子。就不知道我的能不能过（应该不行，因为没看 bfs 序）。

第三题正解也是倍增，而且想法和我的差不多。但我那垃圾的代码实现能力告诉我我应该是不行的。

第四题真的可以把图转成 \(0,1\) ，然后简单判断一下就可以了。

下午讲课

讲的是概率，海星吧。

晚上

成绩出了，\(200\)。
（\(100+100+0+0\)）

第二题过了是我妹想到的。

果然，第三题炸了。

然后第四题的部分分还打错了，我就是个菜鸡。

LYF 大爷还自己弄了个 Excel 表格看前两天分数的排名。

AJ 说明天题目会没有前两天那么简单。
LYF：我信你个鬼，第一天那么简单，怎么可能比第一天还简单。
我和 LTH：

会宿舍的时候，LYF 跟我说明天可能会有 dp、斜率优化……
因为前面没有考。

我：普及考斜率优化？
LYF：斜率优化其实很简单。
我：/jk

Day three

比赛

拿到题目先看题。

第一题看是否相似，直接三边比例相同即可。
想了一下精度可能会有问题，但觉得用 double 应该不会出锅。

第二题看了一下觉得就是看极限情况，觉得手推一下应该有结论，就没有管太多。

第三题是数论，大概看了一下就想着暴力。

第四题看起来也很数论，就也想了一下暴力。

然后先去弄第一题，一开始忘了按长度排序，就直接暴力匹配。
（但是这个不是问题）
然后还是怕精度有问题，就弄了个 1e-6。

然后第二题推了一下极限数据，就发现了大概的贪心。
最低就是你永远零分，比你低的视为跟你一样零分，比你高的就是满分。然后每次把满分分给不同的人。
最高就是你永远比满分只差无限小的分数，比你高的是满分，比你低的是零分。那就尽可能把满分分配给有过没有满分的人，那全部都是满分的人数就是当时在你前面的人数。

然后就去先把第三第四题的暴力打出来。
然后先去看第三题，一开始看能不能把最后里面的那一维去掉。
当然，你会发现你可以在枚举到第二维的时候记忆化一下答案，因为第二维可能会多次选到同一个数，而且第一维对它是没有影响的。
那我们就打一下表，看看结果：
\(998244353,1,998244353,998244353,1,998244353,998244353,998244353,998244353,1\)
等等，为什么会有 \(998244353\)，这个不是模数吗？
哦，有个地方忘了取模。（国 际 憨 憨 TJH）
把取模弄好之后：
\(0,1,0,0,1,0,0,0,0,1\)
好像一开始 \(0\) 的话是 \(0\)，\(1\) 的话是 \(1\)，然后两个 \(1\) 之间隔开的距离从 \(2\) 开始每次增加 \(2\)。

打个程序验证一下，发现是对的。

然后再一看，发现这个就是平方数的位置是 \(1\)，否则是 \(0\)。
那弄回去一看……
兄嘚，这个不就是求 \(1\sim n\) 中每个数有多少个平方数因子，然后每个个数的和吗？

然后就火速实现。

然后去搞 T4。
想了想 LYF 大爷的话，想到可能是 dp。
然后想到一个十分暴力，可以说是 \(n^5\) 复杂度的暴力，然后一看数据范围，好像能过挺多的点。然后就去打。
结果大数据跑得飞快，自己弄个了极限数据，也过了？！

然后就开始搞对拍，由于前两题似乎不太好弄，就只弄了三四题的对拍。

因为打过暴力，所以也很快。

然后就看着对拍等结束。

赛后聊天

好像也没聊啥特别的。

下午讲题

第一题证明方法是对的，但是说因为精度问题要化成最简分数的形式。
危 TJH 危

第二题大致的方向是对的，但是它的具体实现好像和我的不一样。

第三题数论推对了。

第四题就是 \(n^5\) 的 dp。

下午讲课

将的是凸包。
有个初一的在讲课的时候当场把模板切了。
我好菜，我可以退役了。/kk

晚上

成绩出来，\(355\)。
\(85+70+100+100\)

果然，前两题出锅了。

第一题应该是精度问题，听说改成 long double 然后 \(12\) 位精度就可以过。
血亏。

第二题应该是实现的问题。

明天就要提高，想想普及的恶心难度，我觉得提高要凉。

提高（Day 4~6）

Day four

比赛

先看题。

第一题就是一个构造题，一脸懵。
然后想了想，可以每次选当时度数最大的点放到另一个集合。然后大概这个方法搞搞。
结果一看只能过 \(20\) 分的。

然后看第二题。想了一下，想了个 \(n^2\) 暴力就滚了。

然后第三题，看到回文串就想到 hash，然后就想到了 \(n^2\) 算法。

然后第四题，看到题目一脸懵，然后看了看数据，好像也就 \(k=0\) 能做。

然后就先弄先把前两题暴力写出来。
然后写第三题，就写 hash+二分那个。
然后把第四题 \(k=0\) 的情况水了。

然后发现第二题可以把每个点高度被选为最大值时贡献排序后的连续部分一起过掉。然后就打了一下。

然后想了想第一题的二分图应该也可以试着做一做。
然后就去弄。

然后弄完之后只剩十多分钟，就检查了一下，就结束了。

赛后聊天

LYF 神仙竟然只写了一题，不过是正解。
LYF，永远的神！！

下午讲题

第一题似乎是 LYF 神仙的做法，sto LYF orz。
第二题跟我的想法差不多，但是它可以提前处理出来，然后用二分，然后就可以不用每次都找一遍，只用二分一下弄一下就可以了。
第三题好像是用马拉车，但是 hash 也行。（当然还要别的，这个只是说判断是否回文）然后好像要二分，然后还要用 ST 表来维护之类的玩意。
第四题，好像要生成函数，然后又要化式子，一顿操作比例巴拉的。

下午讲课

讲拟阵，非常懵逼。
一堆英文，然后念 PPT。
好像一直听下去并且听懂的只有初一的 WCR 大爷。
（又是初一的，我可能该退役了）

晚上

出成绩了，\(180\)。
（\(100+50+30+0\)）

第一题过了是我妹想到的。
我好像大于 \(20\) 的情况都是当二分图来处理啊。

然后好像很多人用二分图的算法过了这道题。

LYF 血亏，惨。

Day five

比赛

先看题目。

第一题，好像在哪里见过……
反正就是推方程嘛，让我想想方程啊。
忘了，那重新推吧。
（那时的我仍没有意识到事情的严重性）

第二题，大概想了一下，发现可以用线段树维护一下一直向前跳。
大概是 \(n^2\) 算法。

第三题，看了一下觉得可以 hash 加贪心。

至于第四题，看了一下打算直接暴力。

然后推第一题的式子，推了个样例过了的。
就不管了。

然后第二题打线段树。
也把第三题贪心了一下，结果发现我的贪心有问题。然后想了想，打了个部分分 dp。

然后第四题打暴力。

赛后聊天

我：对一下第一题的方程。
LYF：啊？第一题不是做过吗。
我：我忘了。
LYF：你自己看。（打开博客）
我：（看了眼方程）耶！推错了呢！
LYF：这个不是做过吗，那你还错？
我：我是废物啊！（神志丧失ing）

下午讲题

第一题。。。
没事了，我是**。

第二题大概的想法差不多，但是它的实现比较高级。

第三题确实是 dp，但是要想要用堆来缩短一下时间。

第四题，好像是要把操作转成上浮的，然后再做就会好做很多。

下午讲课

将的是有关随机的。

一开始还听得懂，然后就逐渐蒙圈。
然后就变成了半掉线的状态。

（当然，初一神仙 WCR 肯定是全程听完了啦）

晚上

分数出了，\(120\)。
（\(0+20+70+30\)）

我就知道第一题没好事。

LYF 神仙反手就切了第一第三题。

Day six

比赛

先看题目。

第一题看了一下，觉得自己不会暴力。
想了一下因式分解，觉得勉强能水点分。
第二题想了想，弄出了个 \(n^2\) 暴力。
第三题想到暴力模拟，然后一看数据发现一个都过不了。但是觉得只有一个细胞开始的可以试着推规律。
第四题，题目都看的一脸懵，就打算水部分分。

第一题试着弄了一下暴力，然后打出了第二题的暴力。
然后去看第三题一个细胞怎么弄，然后弄了一个多小时弄出了规律，就打了上去。（结果还是不能过一个细胞全部数据）

然后去看第四题，也不知道写哪个部分分。
就打了个分成两个集合的，也不知道对不对。

下午讲题

第一题好像确实要因式分解，然后一堆恶心分类讨论。
第二题好像要 bitset 优化， 然后又 FFT。
第三题好像是要探究出一个异或的东西来确定当前时间某个点是活是死。然后又要通过容斥来算个数，然后再弄一个数位 dp。
第四题好像还要数据分治，分成两个集合的那个数据点时二分再弄一堆东西。其它的好像有一个是最小生成树，还有一个也是二分，但好像还有证明一个东西，然后再搞。

下午讲课

讲多项式。

开局一个 FFT，中文名都不知道的我直接裂开。

然后啥都不知道，就只能看看它证明的过程。
连证明的前提条件和证出来了什么东西，是干嘛的都完全不知道。

害，我太菜了。

晚上

虽然下午就出成绩的但还是写晚上吧。
（不要破坏队形）

分数是 \(85\)。
（\(10+60+15+0\)）

海星，但第二天的第一题让我彻底炸掉了。

总结

海星，但是还是很爆炸。

各种奇妙挂分。
快读、精度、期望。

最不应该的是做过的题都能错。
不愧是我。

不过有了这次的惨痛经历，下次比赛都会加上快读，好好看精度，好好推式子，不要依靠垃圾样例了。