GDKOI2023::xhx.split();

· · 个人记录

Day0

比较好的一点就是我们学校就是考场。@lzqy_从南京回来爆锤我力。和他交流了一下各自的模拟赛，发现我做的题包括模拟赛还是过于简单了。然后我还接触到了一些 dp 套 dp 的题。

晚上整栋楼可热闹了：楼上有人在吹奏乐器，楼下@亦闻楚歌起在做演讲，由于六楼的机房要做考场被封了，所以下面的同学也上到了七楼，加上演讲完后不能回教室打扰他们考试尽管退役却只能来我们机房的那位，机房里的人数竟然达到了平常的 4 倍！

按照我的习惯晚上一场 vp，这次就能叫上他们来打了，打得十分地降智。

Day1

开考前他们都在背板子，我在背配置，然后就开考了。

学校有钱了啊，电脑都换成新的了，体验挺不错。

T1 看一眼感觉不会，决定先把后面的题做了，觉得 T2 最好做，于是用容斥推出了一个 \mathcal O(n) 式子。正当我感到高兴的时候，才发现他是多测，并且不像平常打 CF 那样保证加起来不超过某个东西。

所以只能继续推式子了/ll。试了很多种方法，包括但不限于二项式定理、斯特林数、卷积，但有个东西就是搞不掉。旁边的人已经用了两张草稿纸了，而且还是位女选手/jk。所以回去想 T1 了。

T1 的话显然不能直接做，但似乎没有别的方法。我前几天打了一场 vp，也是判断是否可行的问题，当时我没做出来。看完题解后，我悟出了一个道理：遇事不决，要么 bitset 要么哈希（至于并查集，曾经的遇事不决，我发现我总是第一个考虑它）。没错，这题的做法就是哈希！所以打 vp 还是有点用处的，它关键时刻能救你一命。

回去推 T2 ，结果最后发现连 dp 都想不出来了，打了个 \mathcal O(n^2\log n) 的卷积预处理，卡了亿下常数，不知道能不能过。

然后到了 T3 。一眼看去不可做，第二眼（就爆炸）只会暴力，第三眼感觉能把 m=0 的分敲出来，第四眼感觉是 dp 套 dp。但毕竟我昨天才接触这玩意，做的题太少了，根本就不会。我干脆放弃了这些分去打暴力，结果发现我 m=0 的做法假掉了/lb。没事也就 10 分。

两道数数差评。

出了考场后@lzqy_说他 T3 就是打了 dp 套 dp 但是常数巨大，说是状态数太多了（那看来我之前的方向是对的），然后 T1 打了一种很神仙的做法不知道能不能卡过。@mod998244353的 T1 也是哈希，但是他的方法好像比较容易被卡掉，而且他甚至还用卷积优化了一下（肯定是觉得题目太简单然后炫技）。

中午吃的饭是我平常在学校吃不到的/wul。机房不知道还能不能去然后就回班。看到宣委在给板报夹带私货，遇到了@三笠·阿克曼就去和他打球了。

下午讲题发现是 wxw 出的题（同样是高二差距怎么就那么大呢），T1 应该是没问题的，T2 是推出生成函数的式子之后然后分块搞一下，T3 是我听不懂的容斥。

然后剩下的时间讲了一堆废话，然后也没有大电脑，小电脑又没电了，就是在坐牢。第三环节是滚榜，没想到评测那边好像出了点小问题，好像是每次测都有人分数不一样，随机 RE/WA/TLE/AC 十分玄学。结果就一直在放学校宣传片，把我看吐了。

但愿明天没有数数没有构造没有概率没有博弈。

Day2

早上赶来差点迟到。

到头来还是考了我不擅长的题。T1 是道构造，看起来……好像比较可做。T2 是概率，一眼不会。T3 是一道关于树的题，感觉有时间可以想一下。

先来想 T1 哈，结果很快啊就想到了一种做法，打到一半发现发现是我没有看清楚题面。于是在往树的性质那边想。不难发现如果可以的话一定存在一种方案使得一个点在中间点到直径某一个端点的路径上面。最后我图画太丑了，推出一个错误的结论，连我都不信。还好我自己吧这种做法 hack 掉了，不然可能会损失更多的时间。考虑把直径两个端点分别作为根，剩下两个点显然在子树里面。最后跑个三维偏序就行了。

结果就是我发现它的分类讨论特别恶心，最后打了 200 多行。

然后看到 T2，发现我只会 20 分，于是看 T3 。以为是点分树，发现我好像只能想到 10 分，然后还有一种 \mathcal O(nk^2\log n) 的做法不知道能不能拿多 10 分。由于要打点分树性价比比较低所以没打。

感觉还是检查一下 T1 比较划算，发现我线段树下标应该从 0 开始，而且我数组又其母开小了。随便搞了几组大样例，发现都过了。

这时候时间不多了，就去试一试能不能把 T2 的部分分拿到吧。敲完了样例 RE 不管了。

据说 T3 有 \mathcal O(n^2) ，正好在题面那一页的最下面，没看到麻了。

下午进行现场滚榜，十分地刺激啊。我真没想到我这个垃圾分数能有前 30 ，最后进行到前几名的时候，看着几个 300+ 的分数在冲刺着榜一，最后定格在了 400 ，全场都是欢呼声。榜一整整吊打了我 120 分，是熟悉的名字。我之前跟他打过模拟赛，就没一场比他高。

这场比赛做的比较好的一点就是没挂分，但仍有我会的部分分没有拿齐。可能之后得攻克一下数学和构造这两大难关了。现在离省选就只剩下不到 20 天了，祝好。