【比赛】CSP-S 2024 游记
1 回顾
T1
10min
一开始还是有点想歪了，仔细想一下然后过了。
T2
1h
非常需要总结的一道题。
几乎看完题就出思路了，注意到算是一道小模拟，所以开打之前先理了一遍思路，这很好。
但是，为什么这道简单题浪费了这么久呢？
打的时候太谨慎？打完第一问就就开始测大样例检查？
不！这其实挺好的。
当时测大样例的时候发现第一问多了点，然后开始输出单组数据进行调试。
这个时候问题出现了，输出浮点数用 %d 我吐了啊，\(p\) 全部输出 \(0\)，然后单独测的时候总能过，合起来总是不能过，我以为我 ub 导致了一些神秘错误。。。然后查了半个多小时。甚至自己手写了 lower_bound 和 upper_bound。
全程丝毫没有怀疑审题出问题，在正确输出 \(p\) 之后，猛然发现一切的一切都是符合预期的，这时候回去看题，超速是严格大于啊啊啊！！（题面甚至加粗了……
这个时候心态有点崩了，迅速把取等删去，然后冲完贪心，发现第二问又挂了……
查了大概 5min，发现输出 m-ans 打成 n-ans 了……
T3 (T4)
剩下的大部分时间吧。
同样非常需要总结的一道题。
深呼吸，开 T3，有点怪但是大概率是贪心/dp，先想性质，发现：
- 发现把所有的相邻的元素，连边之后，分两种颜色，那么两种颜色的线段最多只会在端点处交错一个；
- 一个元素要对答案产生贡献，和其最近的同色匹配一定是不劣的。
这很 dp 啊，我们把任意一个颜色视作主元，定义 \(f_i\) 表示钦定 \(i\) 为主要颜色且和 \(lst[a[i]]\) 匹配产生贡献的最大答案。
然后枚举 \(lst[a[i]]\) 之前那个染成主要颜色的点 \(j\)，有转移：
\[f_{i}=\max_{j=1}^{lst[a[i]]}f_j+w(j,i) \]其中 \(w(j,i)\) 是 \((j,i)\cup\{j-1,lst[a[i]]+1\}\) （后面并上的这个集合需要根据下标稍微判一下）中所有 \(a_k\times(\text{出现次数}-1)\)。
大概 30min 的时候打了一个 \(O(n^3)\) 然后发现比大样例小了一点，分析了一下大样例发现性质一有点问题，实际上包含也是可以的，但是包含的那个颜色必须是相邻的。于是我们再输入的时候处理掉这种情况，这样性质一就对了，并且不用考虑算 \(w\) 的时候的下标问题。
然后就过大样例了，\(O(n^2)\) 是好改的，应该再优化一下就能过了。心情稍微好了一点，感觉还是有望 300+ 的。
这个时候去看了一眼 T4，感觉像一个巨型 ds 模拟，而暴力可能也就 32pts，所以还是先去冲 T3 的 50pts 了。
于是冲了两个多小时的 T3 优化没优化出来……一直在想直接优化，然后开始想性质，发现好像并没有什么用。
2 总结
估分：\(100+100+50+0\)。
没脸见人了……人均三道啊…………
T3 下来看了一下，大概有两种做法：
-
依赖于值域的 \(O(nV)\) dp，用线段树显然优化掉；
-
（from Super_Cute.
跟我思路差不多，都从 \(lst[a[i]]\) 转移过来的，不同的是我直接去枚举 \(j\) 那一步转移，他直接用 \(lst[a[i]]+1\) 转移过来了。
（考场上我好像也想过用某一个 dp 值来平替整个转移的过程的，但是没有深入想，害怕又在一个思路里面陷太久了（但是实际上几乎就没想，然后后面就忘了。
（教训就是，思路一定要想 bfs 一样，想到一个思路就记录下来，有这么多时间也不缺这一两分钟啊。
还是实力不够……题见的还是不够，还有就是总结有点畸形了，对特定一道题的解法过度总结了，而缺失了对思维方式和解题技巧的总结。
标签：大样,思路,T3,然后,2024,lst,游记,CSP,dp From： https://www.cnblogs.com/CloudWings/p/18508353