CSP-S2024题解

Targanzqq · 2024-10-27 11:52:07 · 个人记录

T1

贪心：考虑尽可能让更小的数用于配对。

我们先排序，然后双指针扫一遍，如果满足条件，就把左指针向右移动一位。答案就是左指针的位置。时间复杂度 O(n\log n)。

T2

模拟：将每辆车的超速区间处理出来，然后前缀和检测区间内是否有车即可。时间复杂度 O(n+m+l)。

贪心：我们处理出所有被检测出的车会被那些测速仪检测到，然后得到一堆区间。我们将区间按照左端点排序，每次加入一个区间时，如果这个区间被当前钦定的测速仪检测到，就不用管他。如果右端点小于测速仪的位置，就把测速仪向左移动。如果左端点大于测速仪的位置，就新开一个测速仪。答案就是 m 减去测速仪的数量。时间复杂度 O(n\log n)。

T3

贪心+dp（怎么还有贪心）：考虑对于某个点进行dp的过程。

我们可以钦定上一个和当前点颜色相同的点，那么它们中间这一段一定是同色且与当前点异色的，这段贡献可以前缀和求出。而比较困难的是求中间一段的左端点和前面的点之间的关系。由于这个点无法和当前钦定的点之间构成贡献，那么我们可以设状态为 f[i][0/1] 表示选到第 i 个点，不能选/可能选第 i-1 个点的贡献。显然后者不小于前者。

我们对于点 i，在钦定某个点 j 之后，如果 a_{j+1}=a_j，那么我们只能从 f[j+1][0] 转移，即将 f[i][0/1] 对 f[j+1][0]+val(j+1,i-1)+1 取 max，否则我们可以按照相同的方式从 f[j+1][1] 转移。如果时间复杂度 O(n^2)，期望得分 \ge50。如果数据随机生成，可以优化到 O(n)\times \Theta (1) 左右，但是如果给你弄一个所有数全部相同的数据就会被hack掉了。

然后我们考虑最优决策点是否有规律性。首先我们找最优方案，显然这个方案是大于等于区间同色的，而 f 数组又是满足单调不降的，因此我们选择最后一个数显然方案最优。这样的话时间复杂度是 O(n) 的，期望得分 100。(ps：我当时推出式子并写完之后只有十几分钟了，没再优化，导致没拿到后面这 50 分，快来嘲讽我！)