乐东黎族自治县网站建设_网站建设公司_外包开发_seo优化

CCF CSP-S 2024 第二轮比赛

没想到 CSP-S 最后一题的难度就这么难了，周末做了一天，写到凌晨，写到崩溃

零、背景

今天来看看 2024 年 CSP-S 的四道题的题解吧。

A: 快慢指针

B: 区间问题

C: 贪心+动态规划+前缀和

D: 树形DP

一、决斗

题意：各一个数组，对于每个位置，可以随意选择另外一个位置，如果对方的值小于当前的值，则对方可以被杀死。

问如何选择，才能使得剩余未被杀死的位置最少。

思路：二分查找 或快慢指针

显然，需要排序，然后需要从最小或者最大的开始处理。

一开始有一个集合，代表所有数字都未被杀死。

假设从最小的开始枚举，则每次只需要判断集合里最小的元素是否可以被杀死即可。

这时候，集合是顺序访问的，所以可以使用数组来储存，枚举的是快指针，尚未杀死的最小值就是慢指针。

int l = 0, r = 1; while (r < n) { if (nums[r] > nums[l]) { l++; } r++; } printf("%lld\n", r - l);

假设从最大值开始枚举，则每次需要找到小于最大值的最大元素。
这个需要使用二分查找。

multiset<ll> H; ll ans = n; for (int i = n - 1; i >= 0; i--) { ll v = nums[i]; auto it = H.lower_bound(v); if (it == H.begin()) { continue; // 没有更小值，无法删除 } it--; H.erase(it); ans--; } printf("%lld\n", ans);

二、超速检测

题意：给一段长度为 L 的路，一开始有 n 个车以指定起点以及指定起始速度在从南往北行驶。

另外这些车还有自己的加速度，负数代表减速。

车的速度为0时停止，否则直到开出这段路。

现在路上有 m 个监控，车以超过 V 的速度超过某个监控，则算拍到超速，问哪些车会被抓拍到超速。

另外，最多关闭多少个监控，抓拍到的超速的车辆不会漏。

思路：区间问题。

第一步是计算出每个车的超速路段。

超速路段计算需要解方程。

起始速度 v， 加速度 a，目标速度 V，则需要时间t=(V-v)/a。

行驶距离是：(v+V)*t/2。

假设计算出来的是浮点数，例如7.4，再位置7不会超速，位置8才超速。

假设计算出来的的是整数，例如7，则同上，位置7不会超速，位置8才超速。

所以上面的公式直接按整数向下取整加一即可。

for (ll i = 0; i < n; i++) { ll d, v, a; scanf("%lld%lld%lld", &d, &v, &a); if (a > 0) { if (v > V) { // 起始超速，结束超速 nums0.push_back({d, L}); } else { ll S = (V + v) * (V - v) / (2 * a) + 1; if (d + S > L) { //行驶 S 距离超过 V continue; } nums0.push_back({d + S, L}); } } else if (a < 0) { // 减速 if (v <= V) { continue; // 起始未超速 } a = -a; ll S = (V + v) * (v - V) / (2 * a); if (S * 2 * a == (V + v) * (v - V)) { S--; } nums0.push_back({d, min(L, d + S)}); } else { // 匀速 if (v <= V) { continue; } nums0.push_back({d, L}); } }

之后二分查找来判断这个路段是否有摄像头即可判断这个车是否可以被抓拍到。

nums1.reserve(n); // 被拍到的车辆 for (auto [l, r] : nums0) { auto it = lower_bound(caremas.begin(), caremas.end(), l); if (it == caremas.end()) { continue; } if (*it > r) { continue;