联合省选2021 / GDOI2021 游记

· · 个人记录

我们仍未知道那天GDOI2021 D1T1的数据是怎么造的

虽然考得特别差，但还是写一篇游记纪念一下，毕竟是自己第一次参加这种比赛。

Day -2

当天早上做了核酸，之后回学校划水，晚上在大佬的帮助下把连续调了三天的题目给搞定了，刷了刷模板就睡了。

Day 0

晚上做大巴到了耀华，和同校的两个大佬以及外校的两个大佬住在一个宿舍。之后写了会作业，意识到明天有五个半小时的时间，应该足够去调试、对拍或者证明某种性质了吧。

Day 1

先快速浏览了一遍题目，发现题面非常得简短，我下意识觉得是那种“人很话不多”的题目，开始有点慌。

T1感觉非常可做，首先写了一个 n\leq 10 的暴力用以对拍，接着想到可以用 O(N^3) 的dp来做（主要是赛前写了太多dp题），后来发现极差最大并不一定要最大值和最小值都很小或很大，可能会相互影响。

接着就转而想到 O(N^3) 的枚举最大最小值，然后遍历一遍判断是否合法。写了这个做法之后也拍过了。

想了半个多小时的 O(NM)和O(N) 做法，最后只想到一个最大值从 a_{n-m} 开始枚举的小优化。不过并没有什么卵用

上了个厕所转而去写T2。

T2是一个构造题，貌似可做一点。我试图在 b_{i,j} 中寻找规律，推了很久的式子都无果。接着想到了一个诡异的做法：既然只要合法即可随便构造一个矩阵，那么可以从右下便利至左上，然后考虑将所有的b_{i,j}按比例分配给每一个点，具体来讲，对于一个b_{i,j}，在它的求和范围内目前还没有填数的方格，可以求出这所有对应涵盖这些方格的b_{k,l}近似比值，然后按比例分配b_{i,j}给这些格子。虽然感觉会被一些奇怪的数据给卡掉，但是我暂时也想不到更好的方法，于是就开始写了。

结果一直写了将近两个小时，最后也只过了样例，手造的极端数据都没过，此时还剩下不到半个小时。我只好转而去写T3。

T3这种题目一看就是只能写 O(N^2M) 暴力做法，但是由于T2的锅，心态不是很稳，一直写炸，直到考试结束前都没有调出来qwq（考试提前了半小时结束）

出了考场被大佬当众吊打wtcl

Day1估分：\texttt{40+[0,25]+0=[40,65]}

中午一直同舍友的玩捣蛋猪

下午听了一次单方面的交流会，港大、哈工大、中大等名校来这里做了一系列宣讲。dzd也破例来到了GDOI，有生之年第一次看到dzd宣讲 orz

接着颓废了一个晚上。

Day 2

虽然晚上睡得比较晚，但是整一场考试竟然都不感觉困。平常在学校早就睡着了

先浏览了一遍题目，感觉比昨天还要毒瘤，怀揣着骗到多少分是多少分的心态开了T1

T1的 25pts 暴力上跳很好写，但是中途还写挂了几次。之后我一直在像链的部分分，最初想用前缀和与后缀和乱搞一下，发现做法假了；转而去想 m\leq 300 的部分分，依旧是没有什么头绪。

上了个厕所又去想T2

先打了个10pts 暴力以对拍，接着发现滚棒情况其实是队伍最终排名的倒序，于是就省掉一维暴搜，然后发现将m分配给队伍可以使用贪心实现，对于当前队伍 i 只需要在满足 a_i+b_i< a_j( j>i)和a_i+b_i< a_k+b_k(k<i)即可。于是就可以O(n\cdot n!)搞定。中途又写挂了不少次qwq

之后试图进行一系列优化，无果。

至于T3，还是无可避免地重演了Day 1的悲剧，时间又双叒叕不够了，只得爆零。

Day2 估分：25+[40,60]+0=[65,85]

心态直接爆炸，下午接着颓废。

晚上回程的过程中狂写作业+睡觉，后排的同学和学弟们都还挺欢乐的。

Day X

省选出分了

Day1 实际得分：40+0+0=40\ Day2 实际得分：25+60+0=85

GDOI 总分：125 rk 200+

sro lzqy 235\ sro C_B_S 130

为什么D1T1错位输入和n=m的贪心都能拿满分？？？

为什么我的D1T2没有骗到分？？？

总之这场省选虽然考得很差，D1T2和D2T2调试时间太长以至于D1T3和D2T3竟然没有时间写，但还是见证了许多，比如耀华的饭很好吃， 以及省选的真实面目数据特别水。还有就是自己的代码实现能力以及代码调试能力太过低下，以前总是追求难题，并没有去刷那些真正在我的能力范围内的题目，对各方面的能力提升都没有什么帮助。

希望之后能有所改进。 CSP/NOIP 2021 加油！

“我即不期望获得幸福，也不需要什么信誓旦旦的约定。我自有其他期许，希望有朝一日能够远航。奔向更加飘渺的远方。” ——《十字路口》