GDOI2021简要题解

\(GDOI2021\)游记

\(Day\ -n\)

停了四周的课，感觉自己也没有拿出很好的状态，在还没有复习好什么知识的情况下，猝不及防地到了出发的时候了。

\(Day\ 0\)

上午简单复习了一下\(OI\ WIKI\)上的一些知识点，想打打题练练手但最后懒导致什么都没打，于是就到下午了。

出发，一路看番，旁边的卡爷中途还休息了\(40min\)！果然是视力\(5.1\)的男人%%%。

去签了个到，然后和同学一起吃了顿饭，回到酒店继续\(FB\)，\(9:45\)左右被叫去集合，讲了一堆铺垫后收手机。

晚上闲来无事，借了卡爷的语文书还有更重要的阅读器，然后看了一会《三体》就睡了。

\(Day\ 1\)

上午被发手机的人敲醒了。吃了个油条鸡蛋饼就匆匆上路了。

切换到比赛开始。刚开始看题，感觉\(T1\)很可做，然后没怎么想去看\(T2\)，类似差分约束但是似乎每个不等式有四个未知数，感觉有点阴间，\(T3\)的图函数\(graph\)也没有想到什么优秀的解法，于是回去敲\(T1\)了。

发现其实也不是很好敲的样子，想了想感觉可以\(O(n)\)做。首先有性质一定是改一个前缀和后缀。

搞一搞前缀\(max,min\)和后缀\(max,min\)然后枚举一遍前缀取多少，后缀用一个指针向右扫即可。

然后开始硬想\(T2\)，想了挺久的都没有什么结果，于是码\(T3\)了。一开始想了个\(O(n^3m)\)的方法，只有\(20\)，太\(naive\)了。

然后想了想改了改，优化了一下少了一个\(n\)，而后发现求答案的时候不需要每次重新跑\(spfa\)，可以从原来的基础上再跑\(spfa\)，于是还有一个\(n\)变成了一个较小的东西，可以称之为“大常数”。于是时间复杂度就是\(O((<<n)*n*m)\)。\(44\)显然有了，但是\(80\)不确定。

还剩下挺少的时间了，匆忙地打了\(T2\)的暴力，超级暴力的暴力\(dfs\)，然后\(20\)滚粗。差不多然后比赛就结束了。

下午搞什么交流会（联谊），就是听别的人宣传大学，还有\(DZD\)发言。（于是我就看了一个下午的《三体》）。交流会之后和同学一起去了平安金融中心，本来想上去的，但是好像闲人免进的样子，于是乎旁边转了转，发现已经\(6:20\)了，本来想找个好一点的店吃，但是实在是太饿了于是就\(50m\)处的\(M\)解决。吃得很爽（但是只有两个汉堡所以没有我的份了）。回到酒店以后继续\(FB\)，收了手机以后就困了睡了。

\(Day\ 2\)

考虑到昨天似乎有点晚起，于是今天就稍微早点醒来了。早餐换成了面，挺好吃的。

快进到开始比赛。\(T1\)感觉应该很可做的样子，一开始想的是整体二分然后可以\(O(n)\)扫一遍整棵树来判断，于是乎先跳过了（？？？）。看\(T2\)，想用状压来实现，设\(DP\)设了四维，时间复杂度搞得似乎只能拿\(25\)分？？？，然后想了想发现\(SB\)地直接暴力\(dfs\)就有\(60\)了。再想了想，也没有什么思路，然后跑去看\(T3\)。“支配”，啥也没有想到。题目感觉不太可做的样子，于是跑回去刚\(T1\)了。

想了想发现自己的整体二分然后\(O(n)\)扫，似乎不太可行，如果长链剖分的话重儿子传上来的时候我不太会处理。然后就考虑怎么对于每一个询问单独处理。当时想到右边\(lca\)走到\(y\)的部分可以二分右边的终点答案是什么，想到倍增但是当时觉得不能倍增，我是没有想到竟然可以倍增从当前点颜色的收集顺序的位置开始往后一个个跳的。这样\(O(n\log^2n)\)就可以简单\(AC\)了。但是考场\(SB\)的我没有想到于是\(50\)滚粗。(\(m<=300\)的部分我打的似乎要跑\(5s\)。)

\(T2\)就真的\(60\)滚粗了。\(T3\)的话想来想去也没什么会打的，于是就暴力中的暴力\(30\)爬了。比赛也就这样惨痛结束。

\(Day\ 2\)的发挥确实没有到位，\(T1\)的倍增没有认真思考过，\(T2\)的话\(dfs\)可以折半处理，或者优化一下状压\(DP\)也能\(AC\)。其实\(Day\ 2\)可能有能力\(A\)一题甚至两题的，但是由于我考场上的失误而导致了菜鸡结局。

考完后，吃了顿真功夫，买了个甜筒尝尝甜头，看了一路的《三体》，然后就回到纪中了。

旅途结束，明天就是高一下一段考，哈哈，真\(TM\)逗比。

\(Day\ 6\)

成绩出来了。\(100+20+80+50+60+30=340\)，高一有\(455\)把我爆锤。今年滚粗了，明年再战。

还有一段考成绩也出了一些了。物理\(81\)，数学\(121\)，两个我原来比较自信的理科已经变成了人见人锤的弱势科目，感觉自己数学计算能力已经变弱了，而且立体几何方面的想象能力也有待加强。还是要继续努力才行。