CSP-S 2024

· · 生活·游记

作为FZYZer，这是我的第一篇帖子，也有可能是我的最后一篇（？）

完蛋啦 CSP-S摆烂了，我T2打完solved2()特判未调用，警示后人，不过应该也没有人和我一样傻的吧......140Pts->120Pts,本来就不是考很高，雪上加霜了，就全当是给NOIP2024攒RP吧......NOIP RP++

关于CSP-S T2有感

①你...你想正解没错！！我回来就调了35分钟AC了，而在考场上还有1个半小时的时候放弃了T2正解！！对于大模拟就应该毫不留情想正解。

②边界条件想好！比如查找不到/未超速请设置INF或特判判掉（我就是这里似了），对于四个变量recbeg，recend，jsbeg，jsend都需要同样操作！记住有答案统计再更新jsbeg和jsend值，无答案统计则不超速设INF

③数据分治很重要！第一遍提交代码边界条件没想好但是数据分治给我打到了60Pts

④编好正解要把数据分治删掉然后一个一个测特殊性质！否则你就会60Pts然后找不到哪里错…

⑤小细节

⑴做lower_bound的时候记得sort，比如我对p数组第一次就忘记sort了（）

⑵sort里面是(p+1,p+1+m,cmp)我第一次把p大小打成n了（）鉴定为打习惯了（？）

⑥NOIP专攻T1、2（）记住200Pts几乎稳一等，如果是大模拟对我更有益！（不要是结构体就好）

⑦NOIP RP++（）

⑧贪心很重要（）

CSP-S2024 T2 AC Code

#include<bits/stdc++.h>
#define reg register
using namespace std;
const int N=1e5+5;
int T,p[N];
int n,m,L,V,ans=0;
const int INF=1e7;
struct node{
    int d,v,a,recbeg,recend;
    int jsbeg,jsend;
}car[N];
bool cmp(reg int a,reg int b){
    return a<b;
}
bool cmp1(node a,node b){
    return a.jsend<b.jsend;
}
int id;
void solved(){
    ans=0;int maxi=0;
    scanf("%d%d%d%d",&n,&m,&L,&V);
    for(reg int i=1;i<=n;i++){
        scanf("%d%d%d",&car[i].d,&car[i].v,&car[i].a);
        if(car[i].a==0){
            if(car[i].v>V)car[i].recbeg=car[i].d,car[i].recend=L;
            else car[i].recbeg=INF,car[i].recend=INF,car[i].jsbeg=INF,car[i].jsend=INF;
        }
        if(car[i].a>0){
            if(car[i].v>V)car[i].recbeg=car[i].d,car[i].recend=L;
            else {
                car[i].recbeg=car[i].d+(V*V-car[i].v*car[i].v)/(2*car[i].a)+1;
                if(car[i].recbeg>L)car[i].recbeg=INF,car[i].recend=INF,car[i].jsbeg=INF,car[i].jsend=INF;
                else car[i].recend=L;
            } 
        }
        if(car[i].a<0){
            if(car[i].v<=V)car[i].recbeg=INF,car[i].recend=INF,car[i].jsbeg=INF,car[i].jsend=INF;
            else{
                car[i].recbeg=car[i].d;
                if((V*V-car[i].v*car[i].v)%(2*car[i].a)==0){
                    if((car[i].d+(V*V-car[i].v*car[i].v)/(2*car[i].a)-1)<=L)
                        car[i].recend=car[i].d+(V*V-car[i].v*car[i].v)/(2*car[i].a)-1;
                    else car[i].recend=L;
                }
                else {
                    if(car[i].d+(V*V-car[i].v*car[i].v)/(2*car[i].a)<=L)
                        car[i].recend=car[i].d+(V*V-car[i].v*car[i].v)/(2*car[i].a);
                    else car[i].recend=L;
                }
            }
        }
    }
    for(reg int i=1;i<=m;i++){
        scanf("%d",&p[i]);
        maxi=max(maxi,p[i]);
    }
    sort(p+1,p+1+m,cmp);
    for(reg int i=1;i<=n;i++){
        if(car[i].a>=0&&car[i].recbeg!=INF&&car[i].recend!=INF){
            if(car[i].recbeg<=maxi){
                ans++;
                int upp=lower_bound(p+1,p+1+m,car[i].recbeg)-p;
                car[i].jsbeg=p[upp];
                car[i].jsend=p[m];
            }
            else car[i].jsbeg=INF,car[i].jsend=INF;
        }
        else if(car[i].a<0&&car[i].recbeg!=INF&&car[i].recend!=INF){
            int upp1=lower_bound(p+1,p+1+m,car[i].recbeg)-p;
            int upp2=lower_bound(p+1,p+1+m,car[i].recend)-p;
            if(p[upp2]!=car[i].recend)upp2--;
            if(upp2>=upp1){
                ans++;
                car[i].jsbeg=p[upp1];
                car[i].jsend=p[upp2];
            }
            else car[i].jsbeg=INF,car[i].jsend=INF;
        }
    }
    int ans2=0;id=0;
    sort(car+1,car+1+n,cmp1);
    //for(int i=1;i<=n;i++)printf("%d %d\n",car[i].jsbeg,car[i].jsend);
    for(reg int i=1;i<=n;i++)
        if(car[i].jsbeg>id&&car[i].jsbeg!=INF&&car[i].jsend!=INF){
            id=car[i].jsend;
            ++ans2;
        }
    printf("%d %d\n",ans,m-ans2);
}
int main(){
    //freopen("detect.in","r",stdin);
    //freopen("detect.out","w",stdout);
    scanf("%d",&T);
    while(T--)solved();
    return 0;
}