CSP-S2024赛后总结

$ \color {#f39c11} A.决斗 $

赛时：

题目要求游戏结束后剩余怪兽尽可能少，所以我们要将每个怪兽的价值充分发挥。

很容易想到一种贪心：
用第二小的数先打第一小的，再用第三小的打第二小，……以此类推。
这样就能保证能被打掉的都消灭了。
双指针维护即可。
最后把每一种怪兽剩余的数量加起来就是答案。

赛后：

出考场听到某不愿透露姓名的 $ \color{purple} Mafuyu $ 同学说答案就是 $ a $ 中绝对众数的出现次数。

一开始觉得是错的。

后来在洛谷上看来证明：

具体的，我们定义 $ (i,r_i) $ 的偏序关系为 $ (i,r_i) \le (j,r_j) $，当且仅当 $ r_i < r_j $ 或 $ i = j $。显然这是一个偏序关系。我们要找到它的一个最小链覆盖。根据 $ Dilworth $ 定理，最小链覆盖等于最长反链，也就是最多的两两不偏序的怪兽个数。两两不偏序即要求所有 $ r $ 相等，因此统计 $ r $ 中众数的出现次数即可。

因为证明中很多知识为学，故并未看懂。

$ \color {#52c41a} B.超速检测 $

赛时

首先很容易求出每个车会在那两个检测点间被检测出超速，所以问题可以转化为：

有 $ n $ 个点，$ m $ 个区间，问最少取几个点能使每个区间内都有被取到的点。

但冥思苦想并未想出如何做，最后只打了60分。

赛后

延续赛时的思路：

设 $ s_i $ 表示第 $ i $ 个点前有几个被选中的点。

则一种方案可行当且仅当 :
$ \forall 1 \le i \le m $ ，$ s_{r_i} - s_{l_i} \ge 1 \(， \) \forall 1 \le i \le n $ ，$ s_i - s_{i - 1} \le 1 $。

差分约束即可。

$ \color {#3498db} C.染色 $

赛时

显然若当前数字若能与前面某数字一起对答案造成贡献，则他们之间的所有数字均为同色。

所以很容易想到一种 $ dp $:

设 $ f_{i, j} $ 表示 $ i $ 前面第一个与 $ a_i $ 颜色相同的数字与 $ a_i $ 中间有连续 $ j $ 个与 $ a_i $ 不同颜色的数。
显然第一维可以滚掉。

转移现在记不清了，等代码出来后再补吧。

时间复杂度 $ O(n^2) $，预期得分50。

赛后

出考场后 $ \color{red} Green_White $ 大佬告诉我一个贪心的结论：$ a_i $ 相同的数一定是一个颜色的。

所以上述 $ dp $ 可以从枚举连续不同颜色长度变为从上一个与 $ a_i $ 相同的位置转移过来。

故 $ dp $ 复杂度可变为线性。

$ \color {#0e1d69}擂台游戏 $

不会。