本文共 5318 字，大约阅读时间需要 17 分钟。
GDKOI2021 爆炸记
害，我果然还是好菜。不会的照样不会，会打的还因为一堆奇奇怪怪的问题错了一大堆。
拿到题目先看题。第一题看了一下，第一样过去人都蒙了。啊？这不是普及吗，怎么一个表的函数的呢？然后仔细看了几眼，发现只要简单模拟一下然后分类讨论就可以了。
第二题，看到题目暴力很容易就出来了。然后想了想发现要快速求一个点左边比它高的一个和右边比它高的第一个。然后想了想没想到有什么算法。
第三题，想了一会，发现它的数据 n 到了 1e6，而且觉得有点贪心，但是还没有完整的想法。然后想了一下，就去看下一题。
第四题，一开始看了一会发现了一定是拿全部钱去买通行旅票的性质，然后就陷入和每次都要跑一个图会超时的思考。然后就滚去先敲第一题了。
然后看题大概看了 15 分钟左右。然后先去搞第一题，因为思路完整，很快就写出来了。包上检查细节，大概用了 20 分钟。
然后先去写第二题的暴力，就直接枚举两边第一个比它高的位置，然后前缀和算空间大小。大概用了 20 分钟。
然后第三题还没有思路，就先去打第四题的暴力。然后打完暴力想了一下，发现可以离线处理，想弄最小生成树的样子，边按权值排序，然后依次处理出答案。（这个时候大概是过了 70 分钟）
然后就去写，大概又写了 20 分钟，就写出来了。
接着去想第三题，想了想，想到用最大加最小，然后具体的贪心方案也想了出来，就打。
然后去看第二题，做的时候一时间忘记了可以用单调队列找序列中第一个比它大的数，然后想来想去，最后用了二分+线段树来弄。然后这里大概又搞了二十分钟左右。
然后全部打完了，就开始对拍。首先觉得第一题这么好弄是不是哪里有问题，就去弄第一个题的对拍。这题的对拍也是最好弄的，在生成随机数据的时候就可以先生成一个正确的，然后随机一个位置作为答案，然后改一下即可。
结果我比赛时忘了生成随机种子是 srand(time(0))，傻乎乎的一位是 random()，然后就只能只能只能通过数据数组这个值过掉一些数，然后弄成随机的样子。
然后在拍第一题的时候就去弄第二题的对拍。因为一开始打了暴力，就也很快弄好，就把第一题的对拍停了排第二题。
然后拍第二题的时候就去弄第四题的对拍。（因为第三题贪心完之后实现很简单，而且暴力也不知道怎么打，就直接不对拍了）
然后我就三个对拍轮流跑，一直到比赛结束。
LYF 第二题用的是堆，然后一堆人全部用的算法各种各样。还说我的线段树常数很大，不知道能不能过。
然后第三题的贪心跟一堆人对了应该是对的。
T1 分类套路，我的没问题。T2 结果是用单调队列来搞，就不知道我的线段树加二分能不能过。T3 贪心证实了是对的。T4 离线没问题。
然后内心疯狂祈祷第二题能过。
讲数论，很多内容。我拿个草稿本不停记笔记，草稿本上没位置写了就跑回去拿个笔记本继续记。
然后现在正在整理，到时会有一篇博客出来。
出成绩了，340。LYF 和 LXY 两位大爷反手就 AK 了。
第二题超时了，然后我才发现我打的对拍一直都没有看超时。然后就去跟 LYF 这个神仙的代码对拍。
然后发现有的时候我确实会超时。
然后 LYF 大爷看了一眼我的代码，说：“你怎么不用快读快输呢？”我：“哦！c！是哦！。”然后我加了个快读快输之后，它跑得飞快。然后我直接哭死。
听说题目难度会变高，感觉要凉。拿到题目先看题。
第一题看到有点慌，然后想了一会觉得应该可以找每个数循环起来之后最后一个数的周期，然后最后把每个数轮到的周期数乘起来，就可以得到最后一位。
第二题想了一会，感觉思路有点混乱，不知道先约束哪个条件，然后就跳去看下一题。
第三题看了一下题，发现就是走树上的链。然后又是距离，然后直接跑又过不了，然后就想到了用倍增。但是具体怎么实现还不是很清楚，就去看下一题。
最烦的构造题目，看着题目一脸懵逼。看半天也没有想法，就先做题了。
看题大概都看了半个小时，人都傻掉了。
然后去弄第一题，打完结果发现样例都过不了，自己的想法是错的。然后就更加慌了，感觉自己今天要爆蛋。
然后调试了一下，发现 2 和 5 乘在一起会一一消掉。然后改了一下发现还是过不了。
然后又发现其实可以把不是质数的数拆开，然后只剩 2,3,5,7，二和五再消掉之后再按末尾规律乘起来。
然后过了样例，自己出了几个小数据也过了，就去弄下一题了。
然后先去弄第三题，先正常的弄个了树上倍增。然后想了想，因为要弄距离最小值，我们可以弄到根距离的最大值最小值，然后分类讨论一下乱搞，然后就试着打。
但是因为比较混乱，打出来的也不知道对不对，过了样例和自己出的数据就走人了。
然后去想第二题怎么搞，想了很久，想到一个方法，就是先按正则二叉树的规定建树，然后再看是否是正则二叉树。
然后去看第四题，一脸懵，只会瞎搞，搞了个全部都是 1 和行列和为 2 的情况，还不知道会不会有锅。
第一题对了一下大家都差不多。
第二题大家算法各有不同，问了一下我的算法，才突然想起来最后没有判断是否是 bfs 序，然后就贼慌。
第三题大家似乎都是用倍增，但我思路糊成一团，应该都是没有分的了。
第四题好像说可以把图转化成只有 0,1 的，然而这样我还是不会做。
第一题没问题。
第二题好像是一个神奇的算法，弄成很多棵树，然后一个一个看放儿子。就不知道我的能不能过（应该不行，因为没看 bfs 序）。
第三题正解也是倍增，而且想法和我的差不多。但我那垃圾的代码实现能力告诉我我应该是不行的。
第四题真的可以把图转成 0,1，然后简单判断一下就可以了。
讲拟阵，非常懵逼。一堆英文，然后念 PPT。好像一直听下去并且听懂的只有初一的 WCR 大爷。
（又是初一的，我可能该退役了）
出成绩了，180。LYF 神仙反手就 AK 了。
第二题超时了，然后我才发现我打的对拍一直都没有看超时。然后就去跟 LYF 这个神仙的代码对拍。
然后发现有的时候我确实会超时。
然后 LYF 大爷看了一眼我的代码，说：“你怎么不用快读快输呢？”我：“哦！c！是哦！。”然后我加了个快读快输之后，它跑得飞快。然后我直接哭死。
拿到题目先看题。
第一题看是否相似，直接三边比例相同即可。想了一下精度可能会有问题，但觉得用 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~n 中每个数有多少个平方数因子，然后每个个数的和吗？
然后就火速实现。
然后去搞 T4。想了想 LYF 大爷的话，想到可能是 dp。然后想到一个十分暴力，可以说是 n^5 的复杂度的暴力，然后一看数据，好像能过挺多的点。然后就去打。
结果大数据跑得飞快，自己弄个了极限数据，也过了？！
然后就开始搞对拍，由于前两题似乎不太好弄，就只弄了三四题的对拍。
然后就看着对拍等结束。
好像也没聊啥特别的。
第一题证明方法是对的，但是说因为精度问题要化成最简分数的形式。危 TJH 危
第二题大致的方向是对的，但是它的具体实现好像和我的不一样。
第三题数论推对了。
第四题就是 n^5 的 dp。
讲拟阵，非常懵逼。一堆英文，然后念 PPT。好像一直听下去并且听懂的只有初一的 WCR 大爷。
（再次，初一的，我可能该退役了）
出成绩了，120。第一题过了是我妹想到的。LYF 血亏，惨。
然后好像很多人用二分图的算法过了这道题。
先看题。
第一题，好像在哪里见过……反正就是推方程嘛，让我想想方程啊。忘了，那重新推吧。（那时的我仍没有意识到事情的严重性）
第二题，大概想了一下，发现可以用线段树维护一下一直向前跳。大概是 n^2 简单暴力就滚了。
第三题，看了一下想到暴力模拟，然后一看数据发现一个都过不了。但是觉得只有一个细胞开始的可以试着推规律。
第四题，题目都看的一脸懵，就打算水部分分。
然后先弄先把前两题暴力写出来。然后写第三题，就写 hash+二分那个。然后把第四题 k=0 的情况水了。
然后发现第二题可以把每个点高度被选为最大值时贡献排序后的连续部分一起过掉。然后就打了一下。
然后想了想第一题的二分图应该也可以试着做一做。然后就去弄。
然后弄完之后只剩十多分钟，就检查了一下，就结束了。
LYF 神仙竟然只写了一题，不过是正解。
第一题啥都没说。
第二题大概的想法差不多，但是它的实现比较高级。
第三题确实是 dp，但是要想要用堆来缩短一下时间。
第四题，好像是要把操作转成上浮的，然后再做就会好做很多。
讲多项式。开局一个 FFT，中文名都不知道的我直接裂开。
然后啥都不知道，就只能看看它证明的过程。连证明的前提条件和证出来了什么东西，是干嘛的都完全不知道。
害，我太菜了。
虽然下午就出成绩的但还是写晚上吧。（不要破坏队形）
分数是 85。第一题过了是我妹想到的。然后好像很多人用二分图的算法过了这道题。
先看题目。
第一题，好像在哪里见过……反正就是推方程嘛，让我想想方程啊。忘了，那重新推吧。（那时的我仍没有意识到事情的严重性）
第二题，大概想了一下，发现可以用线段树维护一下一直向前跳。大概是 n^2 简单暴力就滚了。
第三题想到暴力模拟，然后一看数据发现一个都过不了。但是觉得只有一个细胞开始的可以试着推规律。
第四题，题目都看的一脸懵，就打算水部分分。
然后推第一题的式子，推了个样例过了的。就不管了。
然后第二题打线段树。也把第三题贪心了一下，结果我的贪心有问题。然后想了想，打了个部分分 dp。
然后第四题打暴力。
我：对一下第一题的方程。LYF：啊？第一题不是做过吗。LYF：你自己看。（打开博客）我：（看了眼方程）耶！推错了呢！LYF：这个不是做过吗，那你还错？我：我是废物啊！（神志丧失ing）
第一题。。。没事了，我是**。
第二题大概的想法差不多，但是它的实现比较高级。
第三题确实是 dp，但是要想要用堆来缩短一下时间。
第四题，好像是要把操作转成上浮的，然后再做就会好做很多。
讲有关随机的。
一开始还听得懂，然后就逐渐蒙圈。然后就变成了半掉线的状态。（当然，初一神仙 WCR 肯定是全程听完了啦）
分数出了，85。第一题过了是我妹想到的。LYF 神仙反手就切了第一第三题。
先看题目。
第一题看了一下，觉得自己不会暴力。想了一下因式分解，觉得勉强能水点分。
第二题想了想，弄出了个 n^2 暴力。
第三题，看了一下想到暴力模拟，然后一看数据发现一个都过不了。但是觉得只有一个细胞开始的可以试着推规律。然后打了一个多小时弄出了规律，就打了上去。（结果还是不能过一个细胞全部数据）
第四题，题目都看的一脸懵，就打了个部分分。
然后第一题试着弄了一下暴力，然后打出了第二题的暴力。然后去看第三题一个细胞怎么弄，然后弄了一个多小时弄出了规律，就打了上去。（结果还是不能过一个细胞全部数据）
然后去看第四题，也不知道写哪个部分分。就打了个分成两个集合的，也不知道对不对。
海星，但是还是很爆炸。各种奇妙挂分。快读、精度、期望。最不应该的是做过的题都能错。不愧是我。
不过有了这次的惨痛经历，下次比赛都会加上快读，好好看精度，好好推式子，不要依靠垃圾样例了。
转载地址：http://kxvh.baihongyu.com/