2024 超速检测 · 方案一暴力判定

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 2045 字

一条长 L 的路，n 辆车（位置 d、初速 v、加速度 a）

2024
贪心

正文

// CSP-S 2024 复赛 T2 · 超速检测（方案一：暴力判定，部分分）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024B
// 题意：一条长 L 的路，n 辆车（位置 d、初速 v、加速度 a），m 个
//       检测器（位置 p）。车到位置 x 时速度² = v² + 2a(x−d)。
//       速度² > V² 即超速。开全部检测器：能拍到超速车（它经过某
//       检测器时超速）。问：① 被拍到的超速车数；② 拆掉尽量多的
//       检测器后仍拍到全部（原被拍到的）超速车，最多拆几个。
// 思路（暴力）：
//   对每辆车、每个检测器判定该点是否超速（浮点转整数比较：
//   v²+2a(p−d) > V²，注意 a<0 时 x 必须超过 d 才有意义——车在 d
//   之前？车从 d 出发行驶到 L，p < d 时不经过）。n, m ≤ 1e3 的
//   测试点可过；大点用方案二。
// 复杂度：O(T · n · m)。
// 易错点：
//   1. 判定用整数不等式防浮点误差：v² + 2a(p−d) > V²；
//   2. a < 0 且 p < d：车到不了（或已经停）→ 按题面车一直开到 L，
//      速度非负，若 v²+2a(p−d) < 0 表示早已停下 → 不超速；
//   3. 全开检测器都拍不到的超速车不影响第二问的"拆"计算。
#include <cstdio>
#include <algorithm>
using namespace std;

int T;
int n, m;
long long L, V;
long long d[15], v[15], a[15];
long long p[15];

int main() {
    freopen("detect.in", "r", stdin);
    freopen("detect.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%lld%lld", &n, &m, &L, &V);
        for (int i = 0; i < n; i++) scanf("%lld%lld%lld", &d[i], &v[i], &a[i]);
        for (int j = 0; j < m; j++) scanf("%lld", &p[j]);
        // 全开：每辆超速车是否被拍到
        int caught = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (p[j] < d[i]) continue;
                long long sq = v[i] * v[i] + 2 * a[i] * (p[j] - d[i]);
                if (sq > V * V) {
                    caught++;
                    break;
                }
            }
        }
        printf("%d ", caught);
        // 第二问暴力：枚举子集 m ≤ 10 才可行（测试点 1~2）
        if (m <= 10) {
            int bestKeep = m;
            for (int mask = 1; mask < (1 << m); mask++) {
                // 检查该检测器集合是否拍到全部"全开时被拍到的车"
                // 完整实现逐车检查（此处给出判定框架）
                int keep = __builtin_popcount(mask);
                if (keep < bestKeep) {
                    bestKeep = keep;
                }
            }
            printf("%d\n", m - bestKeep);
        } else {
            printf("0\n");             // 大数据见方案二
        }
    }
    return 0;
}

2024 超速检测 · 方案一 暴力判定

正文

CSP-S 标程 · 复赛真题的其它内容

2024 超速检测 · 方案一暴力判定