CSP-S 2024 游记

发表于 2024-10-27 更新于 2024-12-07

CSP-S 2024 游记

期望得分 $100 + 100 + 50 + 0 = 250pts$

~~等待 CCF 下发代码中…~~ 今年 CCF 似乎没公开码，但是好消息是没挂分

2024/12/4 Upd: 拿到了 7 级蓝钩，没想到这竟是我 OI 生涯中的高光时刻

T1

30min 写了个贪心，直接跑过样例。曾经一度以为样例是经过特殊构造的，欲写对拍，由于暴力不好写，遂放弃。

期望得分：$100pts$

先通过物理公式计算出每个车的超速区间，需分 $a > 0$，$a < 0$ 和 $a = 0$ 三种情况讨论

再对 $p_i$ 离散化，并将上述区间映射到离散化的 $p$ 上，同时可以求出第一问的答案

然后第二问就转化为最少点覆盖区间问题，经典贪心，优先队列即可

$O(m \log m)$，过样例，期望得分 $100pts$

似乎有不少人挂分，包括 k_Sword 和 NAPeach，为他们感到惋惜，希望他们能在 NOIP 中取得好成绩

30min 写了个 $50pts$ 显然 $O(n^2)$ DP

$f_{i, 0/1, pre}$ 表示第 $i$ 位，染色为蓝或红，上一个与当前异色元素的下标为 $pre$ 的最大权值

对于 $f_{i, 0/1, i - 1}$ 枚举上一位的 $pre$ 转移即可

写完只剩 30min 结束，蓝的优化，遂摆烂

是 Copy CodeForces，CCF 烂完

后来听说正解是 $O(n)$ 的 DP，似乎式子还比较好推？

还可以 $O(n \log n)$ 的 DS 优化 DP，但是 jl 写的被卡常了

没写。

是黑题。正解线性做法似乎很难想。听说有 $16pts$ 唐分，且 $72pts$ 很可做，可惜场上没开。

zzethld 说他场上想到了 $92pts$ 做法，%%%

k_Sword: CSP-S 有 $372pts$ 的人机分

SD 这次分数线 $195pts$，再创新高，题目质量可见一斑

QDEZ 似乎人均 $300pts+$，我太菜了 QwQ