codwarm
2024-11-04 22:49:13
终于是拖到出分这一天动工游记。
省流：J = S
停课训练，一直在做洛谷ATCF上的题，补了好几场 div.2 和 abc，还在 dmy 上打了好多有意思的模拟赛，补了很多有价值的
考前和同学猜算法。
赌了 5 块考树形 DP ，同学死活不信（伏笔
考前刚好一周的周六，晚上打 abc。状态起飞猛干
把这道 F - Hands on Ring (Hard) 场上只有300+人过的题给场切了。
考场上想的是显然的暴力 DP，但是也不太会证明复杂度，感觉上状态数并不多，然后直接 map 加记忆化搜索狠狠地水过去了。
后来才知道根据题目状态
（伏笔
摆了一天，感觉也学不进去了，中午狠狠地睡了一个多小时，看了看一些模板和之前做过的好题就准备考试了。
晚上
早上七点起来非常精神！感觉在酒店睡得一直都挺好的。
下来和两个同学吃完早餐就打车去考场。
开到门口前的一个路口，保安把前面两辆车都赶走了。
本来还有点担心，结果开过去：
保安：你们是干什么的？
出租车司机：送学生进去。
保安：那你们进去吧。
我：哎那为啥前面的不给进？
保安：哦他们是来考试的。
这下搞笑了，如果不走这里还得兜一大圈，走一大段路才能到门口。我们就这样阴差阳错的送进来了 qwq。
后面在报告厅无聊了一会就开考了。
我对于
8:30 哇这个第一题看起来好复杂
8:35 cout << n-s.size();
8:40 开T2，怎么又是这种走迷宫问题。
8:45 怎么是直接模拟啊，连bfs都不用，比走迷宫还水。
9:00 开T3。
似乎 DP 不太行，哦哦好像直接根据数位贪心就行，然后有一些奇怪的情况，又研究了好一会。
其实这个时候我已经对 j 组的难度估计产生了极大误差，以为这场水的要命。
于是就开始慢慢悠悠地做，做着做着，再去检查两下，然后就做了半个多小时。
然后发现 T4 就剩不到 2 h 了。
9:40 开T4。
我感觉 T4 还剩接近 2h 应该绰绰有余吧。
然后一看题目，这啥啊。
图论？好像边数有点多。
线段树优化建图？不太能做啊。
想啊想啊，然后好像会了暴力 DP。
打算先写一下，但似乎没有那么好写，过了 1 h 终于写完了。
然后开始思考优化，发现这玩意似乎可以用一个类似单调队列滑动窗口的东西优化。
然后写啊写，因为一堆细节写挂，就调啊调。
然后就剩 10 min 了优化后的代码还是没过大样例。
然后就有两个选择：冲刺调题 or 求稳。
然后我选择了自认为最聪明的办法：先再冲 5 min，调对了，赢！调不出来，再把备份代码复制回去。
于是我还是没调出来，最后几分钟检查了一下头文件就耻辱下播了。
upd：出分了，T4 暴力DP的分数都没有，挂成 5pts。输！
午觉醒来也是非常精神啊。
开考！
14:30 看到第一题，想了很多解法，最后终于发现了一个很对的双指针加贪心解法，证了证非常的对，然后就溜了。
14:50 开T2。
题目看起来很恶心啊。
加速度？还好有公式。
读了好几遍终于读懂了，对于每辆车，它被检测到超速的超速仪都是一段区间，且这段区间可以用二分求得。
其中有一些浮点数的问题，但是我偷懒了，直接用了浮点数（伏笔
然后呢？不就是一个区间最小点覆盖问题吗？
还好我上过 yxc的算法基础课，这下赢赢赢了。
yxcnb！我再也不敢黑 y 总了。
感觉这个做法还是非常一眼的，于是速速打完，不一会就过了。
目前 200 pts
16:00 开 T3
感觉是 DP 题。
好像还真是。
16:10 暴力 DP O(n^3) 会了。
16:15 哎这玩意不就是 F - Hands on Ring (Hard) 一个套路吗？
又优化一维，O(n^2) 50pts 到手
又想了一会，好像不太会了。
看了看部分分，神必
考试上加了个滚动数组把大样例的
还有一个
总共
17:00 开T4。
题目好恶心。
读了 15 min 后终于读懂了。
立马想到先打一个复杂度
写的很快，调的也很快。
不一会把