CSP-S 2024 游记/题解

CSP-S 2024

去年 S 打成*了，我要蓝√！！！！！！！！

CSP 怎么能不 CS？CS 了一个上午，顺便背了下快读。

进厂！看见了退役的同学在做志愿者，祝他未来可期吧。也希望自己能够超常发挥。

垃圾鼠标真难用。

很好，全是传统题。只有 T2 开了两秒。

T1，这不排个序然后优先队列乱搞就好了。5 min 过了，NOIP 我来了！！！！！

T2 怎么是物理题？再看一眼 T3，神秘 dp。

首先 lower_bound 能找到第一个检测车辆的测速仪，为 k。

然后 a=0 的速度一样没什么好说的；a<0 的在 k 时取到最大值；a>0 的在 m 时取到最大值。

直接在最大值处判断是否超速就解决第一问了。

然后每辆车超速的一定时一段区间，直接二分不就好了？？？？

开打！！！！

等等，转换为区间之后还有第二问。要选出最少的点使所有区间都至少有一个点。

好像这个问题很经典，但是我没做过。左端点排序好像不太能贪，右端点呢？诶！！！！还真可以。

稳了，一等有了。

一开始小样例没过，调了一会所有大样例就过了。现在是北京时间 \texttt{15:20}。

T3 看上去非常可做，是我最喜欢的 dp。

理所当然设 dp_{i,0/1}，先想想 \mathcal O(n^2) 怎么做。

对每个点枚举上一个和自己颜色相同的点，中间那一段颜色相同。

但是中间那一段跟前面颜色相同的还有贡献，第三个样例过不了。

然后发现第二维一点用都没有，丢了得了。

完了不会 \mathcal O(n^2) 的，我要输麻了。

接着发现一个结论：

如果有连续一段数字是一样的，那么将这一段染成同样的颜色一定最优。

去重把贡献算出来就好了，做完后能够保证相邻的两个数不相同。

玩着玩着样例又发现一个结论：

如果某个点有贡献，那么上一个颜色相同的点一定是最大的 j 使得 A_j=A_i。

那直接转移总时间复杂度不就是 \mathcal O(n) 的了？？

\large dp_i=\max\{dp_{i-1},dp_{l_{a_i}+1}+a_i\}

芜湖，过大样例了。我无敌了，我怎么输？？？？？

~~完了我还是不会 \mathcal O(n^2) 的。~~

现在是北京时间 \texttt{16:52}。

T4 什么勾，一点都不想打。暴力建树好像能拿一点分。

随便打了一点，能不能拿分随意吧。

现在是北京时间 \texttt{18:00}，左边的小登怎么一直在叫我有三百了，真烦，能不能来个监考把他 ban 了。

不行，我要把他拿下，我要打 T4 暴力！！！

战斗欲瞬间点满了。

本来只想混 A 性质的，发现每次询问都建一次树可以拿下更多数据。

打了个不知道时间复杂度是多少的代码，但是能过 n\le 500 的大样例。

结束了，时间不是很够，没有检查 T4 的 freopen。

期望得分 100+100+100+40=340。但是去洛谷还有熨斗全文默写了一下发现 T4 要挂若干分。。。。。