CSP-S 2024 爆炸记

监考老师显然业务不熟，将 NOI Linux 的「主目录」称作「桌面」，密码还发错了，难绷。

开 pdf 需要 Linux 账户密码，难绷。还好我知道。

赛时

惨不忍睹。下面均为赛时思路。

T1。显然的贪心，太紧张以至于连写两个假做法。梳理完思路后过了样例。

T2，用物理包装的神秘最优化，还好题目给了公式。潜意识里 T2 就到达了我的能力极限（也许是去年 S 组的缘故）。这也给后面的失败埋下伏笔。

二话不说，直接将公式写成函数。

然后求出了每辆车的终点。（所以我为什么要求这个？？？喜提 600B 屎山。）

接着求出每辆车超速时的位置，二分求探头区间。

就过去一个多小时了。而且前面由于绕了弯路，后来证实求探头区间的部分是错的，错哪了也不知道。

题目就转化成每辆车对应一个探头区间，保留最少的探头使得每辆车区间内都有至少一个探头。

往图论方向想（之前做过区间连边 mst），发现不行。

直接贪心？按直觉想出：对于每个探头，以探头能照到的超速车的数量为关键字，每次取最大的。（为什么要用这个又不确定正确性，复杂度又高的策略啊！）

用 bit 优化贪心，写写调调两个半小时了。

测大样例，错错错！！！发现连前面的求区间部分都是错的，悬着的心是终于死了。

剩下一个小时，打 T3 暴力 dp。

设 f(i,j) 表示 [1,i] 中，[\cdot,j] 涂一个颜色，(j,i] 涂另一个颜色。复杂度很高，O(n^3)。乱搞了一波。

T3 初始值若质时刻：

for(int i=1;i<=n;i++)
{
    f[i][0]=w[1][i];
}
...
std::fill(*f,*f+(N*N),0);

这初始值，如设。

成功地帮助我挂了 25pts。

回到 T2。发现没救了，只剩最后几分钟。检查。

T2 3.3k 屎山魅力时刻：

#include <bits/stdc++.h>

#define fr(x)\
    freopen(#x".in","r",stdin);\
    freopen(#x".out","w",stdout);

using std::cin;
typedef long long ll;
constexpr int N=3e3+114,ML=1e6+N,MV=1145;
constexpr double eps=1e-9;
double sq(double x){return x*x;}
double get_s(double t,double v0,double a){return v0*t+.5*a*sq(t);}
double get_v(double s,double v0,double a){return sqrt(sq(v0)+2.*a*s);}
double s_when_v(double v1,double v0,double a){return (sq(v1)-sq(v0))/(2.*a);}
int n,m;
double L,V;
struct car{double d,v,a;};
car a[N];
double p[N];
// struct car{ll d,v,a;};
int bp[N],ep[N];
double bg[N],ed[N];
bool calc(int cid) // true: exceed
{
    bg[cid]=a[cid].d;
    ed[cid]=a[cid].d+s_when_v(0,a[cid].v,a[cid].a);
    ed[cid]=std::min(ed[cid],L);
    if(ed[cid]<a[cid].d)ed[cid]=L;
    // ed[cid]=std::max(ed[cid],a[cid].d);
    bp[cid]=std::lower_bound(p+1,p+m+1,bg[cid])-p;
    ep[cid]=std::upper_bound(p+1,p+m+1,ed[cid])-p-1;
    // assert(bp<=ep);
    if(bp<=ep)
    {
        if(a[cid].a<0) // quick (bg)
        {
            return (get_v(p[bp[cid]]-a[cid].d,a[cid].v,a[cid].a)>V);
        }
        else
        {
            return (get_v(p[ep[cid]]-a[cid].d,a[cid].v,a[cid].a)>V);
        }
    }
    else
    {
        return false;
    }
}
int pl[N],pr[N];
void get_inr(int cid)
{
    double tmp=a[cid].d+s_when_v(V+eps,a[cid].v,a[cid].a); // position when exceed
    // if(tmp<a[cid].d)tmp=a[cid].d;
    tmp=std::max(tmp,bg[cid]);
    // printf("(%.3lf)",tmp);
    // double ano;
    if(a[cid].a>=0)
    {
        pl[cid]=std::lower_bound(p+1,p+m+1,tmp)-p;
        pr[cid]=ep[cid];
    }
    else // a<0
    {
        pl[cid]=bp[cid];
        pr[cid]=std::upper_bound(p+1,p+m+1,tmp)-p-1;
    }
}
struct bit // for CON
{
    int t[N]; // c (delta)
    #define lb (x&(-x))
    void mdf(int x,int y){for(;x<=m;x+=lb)t[x]+=y;}
    void mdf(int l,int r,int y){mdf(l,y),mdf(r+1,-y);}
    int qry(int x){int r=0;for(;x;x-=lb)r+=t[x];return r;}
};
// bit t;
bit con;
// int con[N];
std::bitset<N> fin,ex;

void Main()
{
    fin.reset();
    ex.reset();
    cin>>n>>m>>L>>V;
    if(n>3000||m>3000)
    {
        while(n--)cin>>L;
        while(m--)cin>>L;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].d>>a[i].v>>a[i].a;
    }
    for(int i=1;i<=m;i++)
    {
        // t.t[i]=0;
        cin>>p[i];
        con.t[i]=0;
        // con[i]=0;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        // cnt+=calc(i);
        // printf("i=%d ",i);
        if(calc(i))
        {
            cnt++;
            get_inr(i);
            // printf("pl=%d pr=%d ",pl[i],pr[i]);
            // for(int j=pl[i];j<=pr[i];j++)con.mdf(j,1);
            con.mdf(pl[i],pr[i],1);
            ex[i]=true;
        }
        // puts("");
        // printf("bg=%.3lf ed=%.3lf bp=%d ep=%d\n",bg[i],ed[i],bp[i],ep[i]);
    }
    // puts("");
    int ans=m;
    for(int k=0;fin.count()<cnt&&ans>=0;ans--,k=0)
    {
        // fprintf(stderr,"%d\n",ans);
        for(int j=1;j<=m;j++)
        {
            // printf("%d ",con.qry(j));
            // if(con[k]<con[j])k=j;
            if(con.qry(k)<con.qry(j))k=j;
        }
        // puts("");
        for(int i=1;i<=n;i++)if(pl[i]<=k&&k<=pr[i]&&!fin[i]&&ex[i])
        {
            con.mdf(pl[i],pr[i],-1);
            // for(int l=pl[i];l<=pr[i];l++)con[l]--;
            fin[i]=true;
        }
    }
    if(~ans)
    {
        printf("%d %d\n",cnt,ans);
    }
    else
    {
        printf("%d %d\n",cnt-1,m-1);
    }
}

int main()
{
    // fr(detect)
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--)
    Main();
    return 0;
}

出考场，讨论完发现我被狠狠地单调队列了。

学了两年 oi，初三，S 组考成这个 * 样。

不过还有救。就算去了 NOIP，也拿不了 1=。

AFO？想 p 吃。肯定还是要继续努力的。

总结经验，下次再来吧。

怎么游寄都写得这么乱。