OI集训 Day7

Content：Competition
Date：2025.7.23

T1：宝宝巴士之小猫数数

赛时思路

开始题意理解错了，以为是倒数第二位开始的连续的 $0$，后面也没有什么新的思路，就用 python 打了个 $n \le 5000$ 的表，拿了 $50$ 分的部分分。

正解

其实就是赛时的思路，根据那个方法打表，但是每次只维护前面几位 (根据样例可以知道答案很小)，然后就没有然后了。

T2：宝宝巴士之换一换

赛时思路

以为时分治，每次合并跨过 $mid$ 的区间，维护一个双指针，每次往结果大的方向移动，同时用不在所选区间内的最大值替换所选区间内的最小值，但其实这个贪心是不对的。

正解

其中有一个 Subtask 3 对问题的思考是很有帮助的。

Solution For Subtask 3

我们发现问题的答案是 最长的连续的一的个数 和 最长的连续的二的个数 $\times$ 2 中的最大值。

我们由此受到启发。观察原式 $(r-l+1)\min\{a_l, a_{l+1}, a_{l+2},\dots,a_{r}\}$，我们考虑枚举最小值，将大于最小值的数变为 $1$，将小于最小值的数变为 $0$，那么问题转化为如何求序列中连续的 $1$ 的个数。

将问题抽象出来，可以发现需要维护一个支持如下操作的数据结构：

• 单点修改
• 求连续区间

并查集可以维护。

T3：宝宝巴士之小猫过河

赛时思路

无

正解

首先我们考虑 Subtask 3 $n \le 5000$ 怎么做，很显然需要一个复杂度为 $\Theta(n^2)$ 的做法。考虑动态规划，定义状态 $dp_{i,j,0/1}$，表示左侧走了前 $i$ 队猫咪🐱，右侧走了前 $j$ 队猫咪，$0/1$ 表示上一次走的是左侧/右侧的猫咪。

发现状态太多不好优化。其实答案具有单调性 (显然)，我们可以考虑二分答案，对于二分的答案 $mid$，设当前还剩下 $limit$ 的时间，每一队猫的过桥时间为 $t_i + k_i + m - 2$，我们把这些区间 $[t_i, t_i + k_i + m - 2]$ 紧挨着 $mid$ 排，如果发现有一对队伍 $(l,r)$，无论如何都会冲突，就返回 $false$。

---

总结

这次比赛时间分配有问题，认为 T2 的复杂度正确，就一直在调试，希望拿到全部分，结果最后不仅没有分，还因为时间不够而没有把暴力的 $25pts$ 的代码提交上去，后面的 T3，T4 的部分分 ($50pts + 15pts$) 没有拿到。
接下来比赛的时候应该注意：

• 比赛前浏览题目，确定哪些部分分是可以拿到的 (在草稿纸上做好笔记，赛后复盘)，能拿部分分的题目留 $40min ~ 50min$。
• 比赛期间不要在同一到题目上花费太长的时间，给自己一个限定的时间范围，如果在范围内没有调出来，要及时放弃。