题解：P11232 [CSP-S 2024] 超速检测（民间数据）

ykzzldz · 2024-10-26 22:52:48 · 题解

首先对 a 的三种情况进行分类讨论，带公式求出每个车能被检测出超速的区间 [l,r]，可以预处理出两个数组 L_i,R_i，分别表示 i 位置左右的第一个测速仪，那么这辆车被检测出超速的测速仪的区间即为 [R_l,L_r]，下面所说的区间均为测速仪的区间。

将所有区间按右端点从小到大排序，遍历每个区间，若此区间内没有测速仪，则加上右端点处的测速仪。例如，有 [1,4],[2,5],[6,7] 三个区间，第一次选 4，然后遍历到 [2,5] 这个区间，发现其中的 4 被选过了，就不用选，[6,7] 这个区间没选，选上 7。下面给出考场代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=1e6+10;
int T,n,m,L,V,l[M],r[M],d[N],v[N],a[N];
struct node{
    int l,r;
};
vector<node>jl;
bool cmp(node a,node b){
    return a.r<b.r;
}
signed main(){
    cin>>T;
    while(T--){
        jl.clear();
        scanf("%lld%lld%lld%lld",&n,&m,&L,&V);
        for(int i=0;i<M;i++){
            l[i]=r[i]=0;
        }
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&d[i],&v[i],&a[i]);
        }
        for(int i=1;i<=m;i++){
            int p;
            scanf("%lld",&p);
            l[p]=r[p]=p;
        }
        for(int i=1;i<=L;i++){
            if(l[i])continue;
            l[i]=l[i-1];
        }
        for(int i=L;i>=0;i--){
            if(r[i])continue;
            r[i]=r[i+1];
        }
        for(int i=1;i<=n;i++){
            if(a[i]==0){
                if(!r[d[i]]||v[i]<=V)continue;
                jl.push_back({r[d[i]],l[L]});
            }
            if(a[i]>0){
                if(!r[d[i]])continue;
                if(v[i]>V){
                    jl.push_back({r[d[i]],l[L]});
                }
                else{
                    int s=(V*V-v[i]*v[i])/(2*a[i])+1;
                    s+=d[i];
                    if(s>L||!r[s])continue;
                    jl.push_back({r[s],l[L]});
                }
            }
            if(a[i]<0){
                if(!r[d[i]]||v[i]<=V)continue;
                int s=(V*V-v[i]*v[i])/(2*a[i]);
                if((V*V-v[i]*v[i])%(2*a[i])==0)s--;
                s+=d[i];
                if(s>L)s=L;
                if(r[d[i]]>l[s])continue;
                jl.push_back({r[d[i]],l[s]});
            }
        }
        sort(jl.begin(),jl.end(),cmp);
        int p=-1,ans=0;
        cout<<jl.size()<<' ';
        for(int i=0;i<jl.size();i++){
            if(i&&jl[i].l<=jl[i-1].l)continue;
            if(p<jl[i].l)p=jl[i].r,ans++;
        }
        cout<<m-ans<<'\n';
    }
    return 0;
}