[数据结构与算法]GDOI2022游记

Day -1

考前好像写题状态不太好（可能是纯粹的懒）。
开始写板子，很多算法都很久没碰了，有的调了很久才过。树剖都调了一个多小时，身败名裂。不过想想省选应该不怎么考算法就没有重写了。
顺便记了一些可能会用到的数学式子，毕竟数论这个玩意感觉考场再推容易浪费时间。

Day 0

上下午把剩下的板子写了翻了翻学习手记就差不多出发了，这次居然能住酒店，想起来上次住耀华的时候还一帮人挤在在厕所充电。
好像比赛也在酒店比，不过酒店看上去很豪华，登记完之后就回房间了。没有写题的打算，所以爽快战斗了一会就到吃饭时间了，还等着教练来叫我们统一出去吃饭结果有个人送了盒饭过来，看上去防疫管理还挺严的。
然后晚上打了会奥日，拖拖拉拉到很晚才睡。
转念一想疫情之后打比赛不能出去玩，游记都不知道写啥了。

Day 1

早上起的不算晚，不过也没有很困，溜下去吃早餐。酒店早餐好像还行，可惜没有咖啡，我自己也没带又懒得买。

然后去考场门口等开考，刚好无聊就来了一波传统艺能，单手风屿环节（依旧不是我）

发现只有一间考场，人不是很多，应该只有二三十个？

然后进考场等着，可以带水和吃的，这是好的。

之后就是念考场纪律啥的，然后发密码了，一次输对解压。

先看一遍题目，T1看起来不太好写，T2是一个计数，T3这个字符串操作应该只是来恶心人的，逝构造题，看上去比较网络流。

然后开始写T1，犹豫了一下要不要用哈希就写了个自带模数的哈希+暴力展开。

然后检查了一下就去写T2了，一眼值域很大，应该是一个类似离散的东西。枚举一个最大值，那么对于每个可以选的值应该是一个常数要么是一个和最大值有关的一次函数交替的形式，而且这种交替最多发生四次。所以考虑分出若干段来，每一段的乘出来就是一个最多$n$次的多项式，然后用拉插插出${\sum }_{i=l}^r{i}^k$就可以求了。

然后我思维就一直局限在枚举最大值的那个点是哪个了，发现有一种能提前枚举区间然后子树转移的方法，不过这样如果一种方案里有多个最大值就会被统计多次，然后想了很久也不知道怎么优化这个部分。

这个时候已经浪费了差不多两个多小时了，只好写一个枚举最大值点的$O(n^5)$暴力了，结果最后优化写法结果是错的调了一个小时，还来不及写求和的那个部分了，预估只有$28$分的样子。

然后只剩下半个多小时光速润去看T3，发现没有方案也有分，也就是有一些白送的分，性质B可以直接输出楼上和楼下的个数，性质A每个个数和需求取min就好了。

然后潦草的检查了一边就结束了，考场上就感觉是考炸了，出来发现大家都觉得很难就不太所谓了，虽然我因为刚T2还很菜导致我的分数肯定是在下游的，希望Day2能翻盘吧。

而且出来之后听说T1可以define成空，我这样做事指数级的，估分-40

下午摆烂了一会和同学联机饥荒到挺晚，然后看了下番睡觉了。

Day 2

正常起然后吃早餐等开考。

开考看题目，T1是一个质因数分解的计数，然后T2又是nmd括号，T3是一个和CSP2019D1T3很像的题。

然后去写T1，看到$s_i\le 2000$，感觉和状压有点不沾边，但是根号一下应该可以，然后写了个程序算了一下大概有$14$个数要状压，然后剩下的质数比较大可以直接分开计算，然后算了一下复杂度应该差不多就很快写完了。

去看T2，想起来WC那道就先考虑括号树，那么操作就是把一个节点自己的所有子节点丢到另一个兄弟节点下面。那么肯定是优先把同层了的给合并最优。

结果我把$x=0,y=1$和$x=1,y=0$想成一样的了，然后就很快的写完了这一（两）种情况

然后$x=1,y=1$的情况想了一会，发现从小到大往后丢到底就行了。

然后T3，从CSP那题的思路开始，这个度数不超过$3$的限制应该给我们暴力枚举交换顺序的，有一个$O(n^4)$的$dp$很好做，就是设$f_{i,j,k}$表示点$i$，传上去了数字$j$，传下去了数字$k$时子树的传递答案。

然后这个$j$枚举的时候只需要枚举子树里有的，所以这样搞是$O(n^3)$的，有$44$分。

然后检查了几次考完了。

因为不知道自己挂了分，来自虚空的感觉良好。

然后坐车回校，防止隔离所以不能回家就直接回校了。

Day 3(+)

呃原本不打算提前测的，但是来电脑室了忍不住用小图灵查了一下分。

然后就寄了，发现自己D1T2和D2T2，D2T3全挂完了，只有200出头，小图灵上没有两天T3的数据，在GD排到了二十多。

加上两天的T3我也是大众分，感觉应该是没啥机会翻盘了。

Day ?~?

官方数据和分数好像出了，出乎意料的是好像D2T2T3虽然写挂了都给了一些分，其实D2T2我的$x=1,y=1$是对的，但是小图灵那边没啥这种点。

但是D1T2还是挂了，三个多小时->0分 。
在小图灵上排$18$，不知道有没有初中的在前面，如果算上noip的话说不定有机会。

之后几天小图灵跑了个排名出来，我是第$16$，前面有个初中的，应该是进了。

Day ?

出了，以最后一名进了省队。运气有点好，挂了这么多分都能进。

心路历程回家再写…

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖