NOIP2023游记

发布时间 2023-11-19 21:49:58作者: luo_shen

Day -7

赛前一周其实有点开摆了,模拟赛总共打了一场,还只做出了 \(1.5\) 道题,t2的在赛时写挂了,赛后2min写完,当时在想NOIP考场上不会也出现什么赛后会了的题吧,结果直接伏笔。

Day 0

早上开动员大会,同样的东西不晓得讲多少遍。开完动员大会,直接开始打球,下午开摆。

Day 1

早上因为要跟校车出发,所以6:40就被喊醒了。

8:00到sdfz,学校感觉比yl大多了,但是厕所太小了,考前上厕所排了10min的队。

进考场后发现是红轴键盘,瞬间爆炸,平时完全不用这种键盘,考场上用一敲三四个键,按个删除怎么长度还在变长,开始适应键盘。

8:30给解压密码。还是老样子,先把题目全部看一遍再说。t1一眼秒,简单题;t2没什么思路,但是理解了题意;t3花了大概5min去理解题意,还花了5min去确认自己是否读错题;t4也大致理解了题意。

8:45开始敲t1,测样例发现写挂了,花了大概15min去调试,最后还是调出来了。

9:00开始思考t2,没什么思路,先写了个 \(O(3^n)\) 的暴力验证题意是否读错,然后去上个厕所(排队还排了快10min),上厕所时突然想到初始每个数对应两个点,一个为自己,另一个为非点,还有三个常数点。将一个操作变为建两个新点,然后直接做并查集,可以维护得到所有数的最后值与初始 \(2n+3\) 个值的关系,为 \(U\) 只有两种情况:赋值为 \(U\),自己和自己初始的非点在同一个连通块内,为 \(T\)\(F\) 则只需要关心赋值的情况。此时再维护一个并查集表示当前不确定的点的权值关系则可以得到所有可以确定的点的权值。剩下的反正都不是 \(U\),对答案无影响。

写了快半个小时,发现思路细节有点问题,重新整理了一遍思路,前前后后总共花了快一个小时才写完t2,得益于前面写了暴力的缘故,只花了15min就写完了拍,开始挂拍,然后看t3。

10:30,还有两个半小时,感觉自己还是只会t3,前两个sub,于是转头看t4,会了一个dp,令 \(f_{i,j}\) 表示第 \(i\) 天已经连续运动了 \(j\) 天的最大贡献,直接转移,复杂度 \(O(nk)\)

11:00,回头看t3,因为一对数连续出现是没有意义的,在处理完当前这一对之后,要么 \(x\)\(y\) 往后移一个,要么 \(x\)\(y\) 同时往后连一个,直接爆搜。写完后发现,这个东西可以记忆化,总复杂度 \(O(qnm)\),再剪剪枝就能拿到 \(35pts\)

此时 11:30,将所有的暴力分写完后开始尝试拿更高的分,自我感觉 t3<t4,所以先想了 t3。将问题转到网格图上,令 \(a_{i,j}\) 表示 \(x_i-y_j\),如果 \(a_{1,1}>0\),只能走权值大于 \(0\) 的格子,如果 \(a_{1,1}<0\),只能走权值小于 \(0\) 的格子,那么上述暴搜思路转为在图上走 \(>0/<0\) 的格子,每次可以向右/向下/向右下走,问是否有方案,然后就不会了,中途好像会了没有往右下走的做法,但是没有想细节,就当是不会吧。

1:30与群友交流t3做法,被告知向右下方走一定可以转为先往右再往下或者先往下再往右,自己仔细思考后发现确实正确,心态直接崩了。t4有一个没有注意到的细节,题目给数据范围都是按区间给的,将所有的方案全部换为区间全是 \(1\) 会好做得多,两个东西没思考清楚,四舍五入挂了快100pts,哭死,退役了。

下午与群友聚餐,这可能是最后一次聚餐了。

晚上云斗数据出来了,看了下排名:46。真验证了他们开始的想法:队线330,一等线270,又是踩着一等线,真得退役喽。

Day2

在家中睡了一天,晚上开始写游记和回忆录,读者看到的时候回忆录可能还没写完,放心,会在一周内完成的。其它的话就到回忆录中写吧。