警示后人40pts
查看原帖
警示后人40pts
539345
OrinLoong楼主2025/7/31 09:08
void vtbuild(int k){
    P[++k]=1,sort(P+1,P+k+1,cmpd);
    stk[ktp=1]=P[1];
    for(int i=2;i<=k;i++){
        if(P[i]==P[i-1])continue;int ca=getlca(P[i],stk[ktp]);
        if(ca!=stk[ktp]){
            while(dfn[ca]<dfn[stk[ktp-1]])addedge(stk[ktp-1],stk[ktp]),ktp--;
            if(dfn[ca]!=dfn[stk[ktp-1]])addedge(ca,stk[ktp]),stk[ktp]=ca;
            else addedge(ca,stk[ktp--]);
        }
        stk[++ktp]=P[i];
    }
    for(int i=1;i<ktp;i++)addedge(stk[i],stk[i+1]);
}
int main(){
    for(int i=1;i<=M;i++){
        readi(K);
        for(int j=1;j<=K;j++)readi(P[j]),isk[P[j]]=1;
        vtbuild(K);DP(1),writil(dp[1]);
        for(int j=1;j<=K;j++)isk[P[j]]=0;
    }
    return 0;
}

发现哪里错了吗?

是的这个错误极为唐诗:我们人为往长为 kkPP 数组最前面添了一个 11,但是 DP 完后在清空 isk 的时候却清的是 PP 的前 kk 个元素,这说明我们清漏了一个。

纯唐。

2025/7/31 09:08
加载中...