GDOI2020 游记_综合

最后一次省选了，这次在广大附中考试，不需要住酒店了。
今年因为疫情，GD选择了加入联考，终于在退役前体验到了4.5h3题的省选，不用再码到手残了。

Day -?

考前两周左右，林老师开始准备模拟赛。模拟赛的题目基本都很老旧，算比较简单，于是AK了不少套。然而dcx连续AK十几套，每场2.5h写完走人，还是比不过。
后面跟雅礼的同学联训，与强强lk也交流了一些，希望他今年能进省队吧。
对于省选倒是没什么感觉。与去年不一样，没怎么担心自己不进的问题，只希望同学们能进。

Day 0

前几天都没怎么写题，打算最后一天敲几个题。早上写了一下Codechef月赛的题解，下午先选择写了一下UR #19的C，卡了半天常数才卡过去，然后又写了一下去年联考的D1T2，过了三个样例自信一交，WA成十分，调了半天才过。顿时很慌，感觉明天不能相信大样例了。
晚上看了一会B站，原来不怎么慌的，突然开始慌起来，于是像去年一样听了会泠鸢yousa的歌。听着听着就平静下来了，告诉自己随便打打就行了。
晚上吸取了教训，选了一个不早不晚的时间上床睡了。

Day 1

意外睡得还行，不过5:45左右就醒了，然后被爸妈拉上车。到了广大附才刚过7点，无事可做在车上发了会呆。
见到同学们简单交流了一下，抓着dcx跟他说起昨天过三个样例WA了的事，互相提醒记得对拍，过了大样例也不稳。
擦了点风油精就进考场了。戴着口罩感觉呼吸困难，但还是要比赛。
照惯例在草稿纸上先写了一些注意事项，过了一会就开考了。有点慌会不会有计算几何或者非传统题，看了眼pdf第一页发现没有。
T1读完感觉就随便二分一下就行了，但看起来细节有点多，于是先跳了。
T2题面只有几句话，是要算一个式子的值。发现给了一个多项式，凭感觉转成了下降幂，然后发现直接套范德蒙德恒等式就做完了。感觉要搞FFT一类的东西，结果翻到数据范围 $m≤1000m\leq 1000$ ，那直接暴力就行了。感觉太简单了，有点怀疑是否假掉了，不过还是选择看一下T3。
T3看起来比较困难，理解了一下大概是给了两个基，然后可以调节其他数的值，使得这两个基分别是总和最大和最小的基，要求代价最小。一眼看上去没什么思路，看了下 $A = B$ 的部分分，感觉是把若干个集合中的数调成相等，不过没想太清楚。
出去上个洗手间冷静了一下，发现用拟阵的角度分析就很清晰了，大概是给定了 $O(nm)\mathcal O(nm)$ 个 $xi≤xjx_i\leq x_j$ 的条件，要求最小化 $∑i=1n(xi?vi)2\sum_{i=1}^{n} (x_i-v_i)^2$ 。这似乎是一个保序回归的问题，看到 $n≤1000n\leq 1000$ 想起论文里讲过的二分后最小割的做法，不过不太记得证明了，只记得一点结论。
权衡了一下决定先写T2。刚准备写突然发现模数可以不是质数，再看了下式子发现只有一个 $(ni)\binom{n}{i}$ 需要求逆，因为 $m≤1000m\leq 1000$ 甚至也可以暴力分解质因数来算，花了10min写完了过了大样例，感觉挺稳。
然后准备写T1，发现 $Q≤2?106Q\leq 2\cdot 10^6$ ，时限3s不开O2，感觉会非常卡常。只会一个线段树二分的做法，感觉不能线性，冷静了很久也不知道什么简单做法，只能慢慢写。细节有点多，写完调过大样例已经过10点了。测了下极限数据发现要跑5s以上，决定先写完T3再来卡常。
还剩一个T3，因为对保序回归做法不太自信，于是看了看部分分，决定先写个50分的切糕。因为同样要用到最小割，感觉代码改一改就是正解了。很快写完调过了前两个样例，尝试凭记忆写出保序回归的二分最小割做法，磨了一会磨出来了。又过了前两个样例，测了下第三个样例发现WA了。当时有点心肺停止，感觉写了个假东西，出去冷静了一下，发现有个地方理解错了，改了改过了第三个样例。
这时候刚过11点，我开始了T1的漫漫卡常路。测了下发现光读入就要2s以上，感觉必须要换成fread和fwrite，但是没怎么写过，尝试了好一会才改对。这时候还是要跑将近4s，我选择去优化前面的部分，把线段树改成非递归的版本，卡到了3.5s以内，打算信仰一下8700k的威力，不过很快发现我离散化写的比较差劲，把对int排序后二分改成了对pair排序，终于是卡了过去。
这时候还剩1h以上，把三题对拍完测完极限感觉无所事事，求稳把T3的切糕暴力套了进去，避免保序回归爆炸拿0分的惨案。
结束了跟dcx聊了一下，他感觉也AK了，并且怒喷题目比CSP还水。我在一旁瑟瑟发抖。
下午回去水群，很害怕FST。代码发下来了找民间数据测了一下，感觉海星。但是又有点慌会被卡常，慌了一个晚上也不知道咋办，只能告诉自己过了。
晚上继续不早不晚的时间上床睡觉。

Day 2

同样睡得还行，然而5:15就醒了。结果到了考场头比较痛，只能多涂了点风油精。
开考前给学弟一点指导，教育他们不要慌，稳稳发挥就好。
同样开考前写了点注意事项，但是今天穿的有点厚，然后戴着口罩非常难受，只能不时把口罩摘下来，并且出去外面换气。因为出去得太频繁，甚至被监考人员警告了。
照例看了一下题，看起来没有计算几何和字符串。瞄了一眼三题竟然都不会，只能慢慢看题。
T1看起来很神仙，看得一脸懵逼。不过拉到数据范围发现 $m≤23m\leq 23$ ，显然是状压DP了，但是时空复杂度都是 $O(m2m)\mathcal O(m2^m)$ 的，看起来要卡空间，感觉能做先跳了。
T2似乎是个经典的trick，倒着按位维护01 trie即可。
T3感觉是个很套路的反演后生成树计数的题，然而我忘了怎么 $O(n3)\mathcal O(n^3)$ 算一个图的生成树边权和的和，于是只会 $O(mn3?maxd)\mathcal O(mn^3\cdot maxd)$ 的暴力，感觉不行但是只能先不管了。
于是先把T2写掉了。然后T1冷静了一下，会了一个预处理meet in middle的做法，空间是 $O(2m+m2m2)\mathcal O(2^m+m2^{\frac{m}{2}})$ 的，并且时间复杂度常数很小，于是就写掉了。
又开始做T3。想了很久还是想不起那个 $O(n3)\mathcal O(n^3)$ 的做法，推了一个单次 $O(n4)\mathcal O(n^4)$ 的，但是最坏复杂度没有优化，并且感觉常数比较大。于是打算先写那个暴力的做法，结果测了一下竟然只跑了4s多，卡了一下在本机只跑了2.6s，于是就没管了。
这时候还剩一大堆时间。对拍完测完极限开始肉眼查错，发现T2上界开小了改了一下就不知道干什么了。感觉T3虽然很稳，但还是套了一个 $w_i$ 全部相等的特判，没想到最后居然有用。
考完出来跟dcx聊了一下，他T3写了那个单次 $O(n4)\mathcal O(n^4)$ 的做法，加了一堆常数优化跑的飞快。
回去水群，一开始相当自信，结果被告知我考场的机子是64位的，由于T3大量使用了long long运算，在最终评测的32位机会变慢一倍。万幸前面套了个特判，于是T3估分变成70。

Day 4

出分了，100+100+100+100+100+90=590，D2T3数据没造满放了我一条生路（虽然好像T的点只T了几十毫秒）。dcx和两个纪中哥哥AK了，我凭CSP的优势还是苟到了GD-01，但还是比较丢人。
我，dcx，hjw和dyh进了省队，初三的zjr也进了E队，因为学校的奖励名额，全体高中oier都可以去NOI，希望大家顺利发挥吧。