2024.10.27 CSP-S 第二轮

昨天晚上

跟其他人一起去吃了牛肉面，味道还行,就是很辣。

上午

因为不用考 J 组，所以可以睡的晚一点，不过 8:30 得到会议室自习。
就我没带笔记本，只能默默地掏出我的算阶。

中午

菜好少，而且味道不咋地，本来想去 KFC 加餐的，但怕拉肚子就不去了。

下午

提前 10 分钟进考场。

2:30 开始考试。

先大致浏览了一下题，前三题题面还算清晰，第二题比较长。最后一题题面长的要死，反正我也不打算做出最后一题就先不看了。
初步思路：T1 贪心，T2 推式子然后不会，T3 dp。

T1 太水了，不如去年 T1，很快就过大样例了，才 \(552\) 字节。
2:45 切 T1。

T2 发现其实二分找出每辆车后面第一个检查点之后，看一下那个检查点和末尾检查点就可以知道超没超速了，那第一问就随便做。
进一步会发现每辆车能测出他超速的是一段区间，于是再次二分搞出所有区间。
这样问题好像就变成：给你若干个区间求最少的能覆盖所有区间的点数。
这不典题吗，先发现包含的区间没有用，然后变成胡不包含，然后按照左端点排序，则右端点升序。
朴素dp，设 \(f_i\) 表示覆盖前 \(i\) 个区间的答案，显然放在左端点最优，还是二分就可以找到决策点了。
插一嘴，差分约束也可以做，就是太长了。
3:30 切 T2。

T3 感觉只能是 dp，但是状态设不出来，一开始觉得应该是枚举第 \(i\) 个点前面第一个和他数字一样的同色数 \(j\)，那要产生贡献当且仅当 \((j,i)\) 这个区间都与 \(i\) 不同色，但是这样 \(j+1\) 这个点的贡献算不出来，而且枚举加算贡献是 \(O(n^3)\) 的。
然后灵光一闪，觉得同色数一定在一个集合，理性证明了一下发现是对的，那就不用枚举 \(j\) 直接看最后一个相同数值的数即可。
但还是要解决 \(i+1\) 贡献的问题……
o，那我直接多记一维不就好了，把 \(i，i+1\) 的颜色都记进来就好了。
转移前缀和优化即可，\(O(n)\)。
4:30 切 T3。

还有 \(2\) 个小时给我做 T4，时间头一次这么充裕，果然前几天的倒霉都是在积攒 rp，只要 T4 不是黑那我两个小时总能做出来吧。

题面怎么这么长呀。

可算是读懂了，不过感觉模拟我都打不出来，还要优化成线性，这怎么做。

果断先回去检查。

差不多 5:00 检查完。

先把特殊性质 A 打了，然后打了一个感觉是指数级别的暴力，目前 \(24\) 分。

然后发现貌似这个暴力 dfs 是 \(O(n^3)\) 的，一测大样例跑的飞快，果然是 \(O(n^3)\)，这样就是 \(40\) 分了。

然后就卡了卡了。

最后 \(30\) 分钟发现了 \(O(n^2 \log n)\) 做法，但只有 \(8\) 分，而且我觉得我打不出来，就不想打了。

6:30 结束考试。

出去一交对发现提高组的基本都是 \(200+\),提高转省选基本都 \(300+\)，果然还是太水了，不过感觉比去年更思维（去年 T3 大模拟就是屎）。
不过我这个成绩还算不错。

期望得分：\(100 + 100 + 100 + 40 = 340\)。

总结

今年发挥还算稳定，思路很流畅，并且代码实现没出现小错误。应该是把能想到的都想出来了。

如果最后一题写的更快一点可能会变成 \(348\) 分。

今年 T2 只要写过 konata 的 DP 专题或者 cdx 的最短路专题应该就能秒，所以平时写题还是很有必要的。

晚上

晚饭比中饭好多了。

8:00 圆满返程。

来源链接：https://www.cnblogs.com/FloatingLife/p/18648027