提供一个的唐诗的 20pts 错法供后人嘲笑

如果你是用ST表做第二问，那么注意了。某论文是这么写的

\text{LCP}(i,j)=lcp(suf(sa(i)),suf(sa(j)))

而那个式子是

\text{LCP}(i,j)=\min_{k=i+1}^j h_k

所以实际上你在做第一问时，默认枚举的下标

i

实际上是某个顺序下的

sa

。

CPP

for(int i=1;i<=n;i++){
    dx[h[i]]+=(i-L[i])*(R[i]-i);
}

所以顺序上来看是有问题的，但由于

i

和

sa

是一一对应的，所以第一问不会 WA，如果你就这样做第二问的话会 WA

CPP

for(int i=1;i<=n;i++){
    int lmx=rmax(L[i],i-1),rmx=rmax(i,R[i]-1);
    int lmi=rmin(L[i],i-1),rmi=rmin(i,R[i]-1);
    if(lmx==-inf) rmx=1;
    if(lmi==inf) rmi=-1;
    mx[h[i]]=max(mx[h[i]],max(lmx*rmx,lmi*rmi));
}// WA

一个办法是直接在初始化 ST 表时直接把下标变成

sa

即可。

CPP

for(int i=1;i<=n;i++){
    stm[0][i]=sti[0][i]=a[sa[i]];
}

提供一个的唐诗的 20pts 错法供后人嘲笑

讨论操作

回复

相关推荐

提供一个的唐诗的 20pts 错法供后人嘲笑