2023GDKOI总结

2023GDKOI总结

说明：不是GD选手，只是因为来zsjz集训就顺便参加了GDKOI，不过也不参与GD选手排名。

考前看了看GDKOI2021的题，当时是考了3天，每天4题，而里面只有一道题是我一眼能看出来做法的，所以感觉考试的难度不小。

Day1

考试是8：30开始。先打开了VScode，发现已经装好了C++的插件，很良心。然后就开始看题。T1一直没有特别好的做法，然后想到了判行和与列和，一会就写完了，简单对拍了一下感觉没问题，就去看T2了。T2是个数学题，先通过打表推出了错排的方案数，然后就开始不停推式子，先推了一个\(n^3\)的式子，然后写出来发现有问题，然后又重新推，好不容易推了个单次\(O(n)\)的式子，担心过不了第3档部分分就写了个map防止重复计算，自己造数据发现跑得很快就没管了。T3感觉很难，只打了20分的暴力就没管了。然后再回头看T1，决定造很小的数据测正确性，结果真的拍出错来了，发现是\(A=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)，\(B=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)，\(C=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)的情况把我卡掉了，然后发现只要查一下对角线上的点是否正确就行了。考试快结束了，把文件拷到虚拟机里测了一下，发现没问题，就准备交卷了。

考完才知道T1直接随机一个向量就是正解，感觉自己的做法容易没卡，好在最后把暴力拼上去了，不至于会挂太多分。期望得分：(20 ~ 100)+60+20=(100 ~ 180)

Day2

还没开始的时候监考老师说有道题有spj，但是就害怕是不是有什么神秘构造题。考试一开始，就发现T1是构造题，T2T3又是不可做题，感觉还是T1更好得分，于是开始全力攻T1。先发现链的情况很简单，可以直接找直径，然后就开始在草稿纸上画出一般的情况，发现3个点到其中两个点的LCA的距离是一定的，找出每个点最长的3条链，然后就可以用三维偏序解决。可是看数据范围，普通的三维偏序过1s有点困难，而且一时忘记了三维偏序怎么写，就决定边写前面一步边想后面的怎么解决。前面的部分就是简单的换根DP，没花多久写完了，看了一眼感觉没问题。然后就开始想后面的怎么做，突然就灵光一现，想到按照一维离线后，对第二维建线段树，每个位置维护第3维的最大值，这样每次查找时只需求一个区间最大值就行了，于是就开始写，写完发现最后输出时还得找两点路径上第k个点，这就可以用简单的树上倍增做，然后大概在10：30写完了，代码有6k，在11：00左右就调好拍上了。然后发现T2暴力一分都没有，就跳了，看T3，很快写了10分的暴力，然后回头看T1，测了测时间，发现超过了1s，于是就开始卡卡常，最后好不容易卡进了1.02s，还想继续优化，结果时间不够了，只是拿到虚拟机下编译了一下考试就结束了。

考完出来发现T1我们学校就两个人写出来了，但还是怕自己超时了，T2也没什么人得分，T3倒是有人拿了30左右。期望得分：(60 ~ 100)+0+(10 ~ 20)=(70 ~ 120)。

最终得分：100+60+20+100+0+0=280，过了GD的金牌线。

总结：这场考试考得比春测要好不少，一是解决了两天的T1，而且D1T2也拿了很高的分，但是也有很多不足的地方。比如D2的T2T3一分没拿，T2可以用fwt或矩阵乘法拿到不少暴力分，T3如果没写挂有20分，再拼一点别的暴力分（如线段树合并）有30分，这些分都没有拿到，这说明一是暴力分要拿稳，而是要提升水平，拿到更高的暴力分。还有就是两天的T1都是因为数据不强才过的，以后遇到这种可能被卡的题要尽量优化，减少被卡的几率和被卡的分数。