终于是拖到出分这一天动工游记。

省流：J = S

Day [-n,-1]

停课训练，一直在做洛谷ATCF上的题，补了好几场 div.2 和 abc，还在 dmy 上打了好多有意思的模拟赛，补了很多有价值的 \(DP\) 题目。

考前和同学猜算法。

赌了 5 块考树形 DP ，同学死活不信（伏笔 \(\times 1\)

Day -7

考前刚好一周的周六，晚上打 abc。状态起飞猛干 \(6\) 题。rk200+上大分

把这道 F - Hands on Ring (Hard) 场上只有300+人过的题给场切了。

考场上想的是显然的暴力 DP，但是也不太会证明复杂度，感觉上状态数并不多，然后直接 map 加记忆化搜索狠狠地水过去了。

后来才知道根据题目状态 \(dp_{i,j,k}\) 中 \(j,k\) 其中一个一定为 \(a[i-1]\)，然后状态数就为 \(O(n^2)\) 了。然后又学会了一个优化状态的 \(trick\)。

（伏笔 \(\times 2\)

Day 0

摆了一天，感觉也学不进去了，中午狠狠地睡了一个多小时，看了看一些模板和之前做过的好题就准备考试了。

晚上 \(10\) 点去到深圳高级中学高中园旁边的维也纳酒店，\(10:30\) 看了看q群就睡了。

Day 1

上午

早上七点起来非常精神！感觉在酒店睡得一直都挺好的。

下来和两个同学吃完早餐就去考场。

开到门口一个路口，保安把前面两辆车都赶走了。

本来还有点担心，结果开过去：

保安：你们是干什么的？

出租车司机：送学生进去。

保安：那你们进去吧。

我：哎那为啥前面的不给进？

保安：哦他们是来考试的。

这下搞笑了，如果不走这里还得兜一大圈，走一大段路才能到门口。我们就这样阴差阳错的送进来了 qwq。

后面在报告厅无聊了一会就开考了。

我对于 \(csp-j\) 的策略是尽量放松打，别给脑子整烧了影响下午 S 组。

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。

题目看起来很恶心啊。

加速度？还好有公式。

读了好几遍终于读懂了，对于每辆车，它被检测到超速的超速仪都是一段区间，且这段区间可以用二分求得。

其中有一些浮点数的问题，但是我偷懒了，直接用了浮点数（伏笔 \(\times 3\)

然后呢？不就是一个区间最小点覆盖问题吗？

还好我上过 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 到手

又想了一会，好像不太会了。

看了看部分分，神必 \(n \le 20000\) 部分分，出考场后跟小伙伴讨论也没想出来是啥做法。

考试上加了个滚动数组把大样例的 \(n\le 20000\) 过了。

还有一个 \(a_i \le 10\) ，也是一个暴力 DP，总共 \([65,75]\) pts。

17:00 开T4。

题目好恶心。

读了 15 min 后终于读懂了。

立马想到先打一个复杂度 \(O(玄学)\) 的模拟暴力。

写的很快，调的也很快。

不一会把 \(n \le 500\) 大样例轻松过了。

\(n \le 5000\) 的跑了 3s。

期望：32pts

有点悬，发现很难优化就弃了。

发现性质 A 有点好打，于是喜加 8 pts。

期望：40 pts

打完 T4 后检查时幸运地发现 T3 一处没清空的错误。

还把每道题交到 NOI LINUX 上测了一下，似乎都没有什么问题。

就这样结束了。

J组估分：100+100+100+50

S组估分：100+100+[65,75]+40

11.4

终于出分了

j：100 + 100 + 100 + 5 = 305，瓜分了！输！

S：100+100+65+40 = 305，没瓜分！赢！

伏笔收回

• 擂台游戏：

  

  于是：

• 最后 T2 还是没有卡我浮点数精度，甚至没加 eps，赢！