P11232 [CSP-S 2024] 超速检测 题解

· · 题解

解题思路

首先容易发现每个车辆肯定都是在一段区间内会被检测出超速，可以使用二分求出这些区间。

然后题意可以转化为给定一些区间，选择尽量少的点使得每个区间内至少有一个选择的点。

考虑 dp，设 f_i 表示选取第 i 个点，且让前 i 个点涉及到的区间满足要求的最小选点数。

考虑枚举上一个选择的点，我们不能让这两个点中间存在区间，所以可以把区间按右端点排序，然后二分找到满足右端点小于 i 的区间前缀 [1,p]。

我们可以预处理区间的前缀左端点最大值 Lmax，那么上一个选择的点 j 必须满足 j \ge Lmax_p。

发现可以转移的状态处于一个区间，于是用线段树维护区间最小值即可。

后来发现这部分也可以单调队列维护。

tips

对于计算瞬时速度，可以把根号运算转化为不等式另一侧的平方运算，从而避免浮点数运算。

#include <bits/stdc++.h>
#define lowbit(o) o & -o
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 100005;
const int mod = 998244353;
const int inf = 5e5;
const LL INF = 1e18;
int d[N], v[N], a[N], p[N];
struct Line{
    int l, r;
}c[N];
int w[N << 2], Lmax[N], f[N];
bool cmp(Line A,Line B)
{
    if (A.r != B.r)
        return A.r < B.r;
    return A.l < B.l;
}
LL calc(LL v,LL a,LL d,LL pos)
{
    LL s = pos - d;
    return v * v + 2 * a * s;
}
inline void pushup(int u)
{
    w[u] = min(w[u << 1], w[u << 1 | 1]);
}
void build(int u,int l,int r)
{
    if (l == r)
    {
        w[u] = 1000000;
        if (!l)
            w[u] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u,int l,int r,int x,int v)
{
    if (l == r)
    {
        w[u] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        update(u << 1, l, mid, x, v);
    else
        update(u << 1 | 1, mid + 1, r, x, v);
    pushup(u);
}
int query(int u,int l,int r,int L,int R)
{
    if (L <= l && r <= R)
        return w[u];
    int mid = (l + r) >> 1, res = 1000000;
    if (L <= mid)
        res = query(u << 1, l, mid, L ,R);
    if (mid < R)
        res = min(res, query(u << 1 | 1, mid + 1, r, L, R));
    return res;
}
void work()
{
    int n, m, L;
    LL V;
    cin >> n >> m >> L >> V;
    for (int i=1;i<=n;i++)
        cin >> d[i] >> v[i] >> a[i];
    for (int i=1;i<=m;i++)
        cin >> p[i];
    int tot = 0;
    for (int i=1;i<=n;i++)
    {
        if (p[m] < d[i])
            continue;
        int l = lower_bound(p + 1, p + m + 1, d[i]) - p, r = m, res = 0;
        if (a[i] > 0)
        {
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (calc(v[i], a[i], d[i], p[mid]) > V * V)
                    res = mid, r = mid - 1;
                else
                    l = mid + 1;
            }
            if (res)
            {
                c[++ tot] = {res, m};
                //cout << "1\n";
            }
        }
        else if (a[i] == 0)
        {
            if (v[i] > V)
                c[++ tot] = {l, m};
            //cout << "2\n";
        }
        else
        {
            int L = l;
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (calc(v[i], a[i], d[i], p[mid]) > V * V)
                    res = mid, l = mid + 1;
                else
                    r = mid - 1;
            }
            if (res)
            {
                c[++ tot] = {L, res};
                //cout << "3\n";
            }
        }
    }
    cout << tot << ' ';
    if (!tot)
    {
        cout << m << '\n';
        return;
    }
    sort(c + 1, c + tot + 1, cmp);
    for (int i=1;i<=tot;i++)
        Lmax[i] = max(Lmax[i - 1], c[i].l);
    build(1, 0, m);
    for (int i=1;i<=m;i++)
    {
        int l = 1, r = tot, res = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (c[mid].r < i)
                res = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        f[i] = query(1, 0, m, Lmax[res], i - 1) + 1;
        update(1, 0, m, i, f[i]);
    }
    int ans = 1000000;
    for (int i=1;i<=m;i++)
        if (i >= Lmax[tot])
            ans = min(ans, f[i]);
    cout << m - ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _T = 1;
    cin >> _T;
    while (_T--)
        work();
    return 0;
}