C/C++教程

[CTSC2012]熟悉的文章

本文主要是介绍[CTSC2012]熟悉的文章，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

壹、题目描述 ¶

传送门 to Luogu.

贰、题解 ¶

本文其实是思考过程，思路可能稍显混乱。

能够想到对标准串建广义 \(\rm SAM\)，显然能对 \(l\) 进行二分，那么我们现在考察的就是，对于一个 \(l\)，如何校验其正确性？或者说，存在怎样的最优分割能让我们分割出来的串尽可能进行匹配？

确实不难想到 \(\rm DP\)，考虑有用的信息：

  • 当前位；
  • 从当前开始，已经匹配的最长长度；
  • 当前位置在 \(\rm SAM\) 上的匹配点；
  • 当前已经得到的合法匹配串的长度；

状态将所有信息存下固然是可行的，但肯定是不行的（？）。

考察一个错误的贪心 —— 贪心地匹配尽可能长的长度。但是由于可能可以将前面的某些匹配串的字符让到后面，使得后面的串也能够变得合法，这样的贪心显然不正确。

不妨找到每个右端点能匹配的最多的左端点，这个在 \(\rm SAM\) 上能够做到，现在问题变成了，从这些区间中，选出一些不相交的区间，每个区间都能够被一个大区间包含，是否能让这些区间覆盖超过 \(90\%\) 的点。

还是不行，但是注意到我们并不要求具体地分割方案，有没有什么更不用在意具体分割方案的转化吗？

重拾 \(\rm DP\)，定义状态 \(f(i)\) 表示最后一个单词到 \(i\) 结尾，能够匹配的最长长度，那么我们枚举前一个分割点 \(j\in [1,i)\)，将 \((j,i]\) 的词进行匹配即可。

不过需要注意的是，可能有空挡，所以还要 \(f(i)\) 和 \(f(i-1)\) 取 \(\max\) 才行（注意 \(\rm DP\) 含义的微小变化）。

不难发现这个 \(\rm DP\) 的复杂度事实上是 \(\mathcal O(n^3)\) 的，我们可以进行一些优化。

设 \(L(i)\) 表示以 \(i\) 结尾，最长的匹配单词的左端点在 \(L(i)\)，那么，我们枚举 \(j\) 的时候，就可以这样：

  • 对于 \(j<L(i)\)，有 \(f(i)=\max f(j)+i-L(i)+1\)；
  • 对于 \(j\ge L(i)\)，有 \(f(i)=\max f(j)+i-j\)；

我们将两个转移综合一下，有

\[f(i)=\max \left\{f(j)-\max\{L(i)-1,j\} \right\} \]

线段树优化，复杂度变成 \(\mathcal O(n\log^2 n)\). 好像还是不行。还有什么性质啊？

嘿，其实刚刚的 \(f(i-1)\) 取 \(\max\) 就可以包含空挡，并且 \(j<L(i)\) 的转移部分其实也是空挡，我们只需要和 \(f(i-1)\) 取 \(\max\) 就可以代替这部分的转移了，那么，我们的转移变成了：

\[f(i)=\max\{f(j)+i-(j+1)+1,f(i-1)|j \in[L(i)-1,i-l]\} \]

之后，方程变成了

\[f(i)=\max\{f(j)-j+i,f(i-1)|j \in[L(i)-1,i-l]\} \]

维护一个 \(f(j)-j\) 的单减队列就行了。复杂度就变成了 \(\mathcal O(n\log n)\) 了。别忘了算上二分的复杂度。这算黑题？

叁、参考代码 ¶

const int maxn=2.2e6; // twice
const int sigma=2;

int trie[maxn+5][sigma], fa[maxn+5];
int len[maxn+5], ncnt=1, lst;
inline void add(int c){
    int p=lst, u, q, nq;
    if(trie[p][c]){
        q=trie[p][c];
        if(len[q]==len[p]+1) lst=q;
        else{
            nq=lst=++ncnt;
            for(int i=0; i<sigma; ++i)
                trie[nq][i]=trie[q][i];
            fa[nq]=fa[q], len[nq]=len[p]+1;
            fa[q]=nq;
            for(; p && trie[p][c]==q; p=fa[p])
                trie[p][c]=nq;
        }
        return;
    }
    u=lst=++ncnt;
    len[u]=len[p]+1;
    for(; p && !trie[p][c]; p=fa[p])
        trie[p][c]=u;
    if(!p) fa[u]=1;
    else{
        q=trie[p][c];
        if(len[q]==len[p]+1) fa[u]=q;
        else{
            nq=++ncnt;
            for(int i=0; i<sigma; ++i)
                trie[nq][i]=trie[q][i];
            fa[nq]=fa[q], len[nq]=len[p]+1;
            fa[q]=fa[u]=nq;
            for(; p && trie[p][c]==q; p=fa[p])
                trie[p][c]=nq;
        }
    }
}

int T, n, m;
char s[maxn+5];

inline void input(){
    T=readin(1), m=readin(1);
    rep(t, 1, m){
        lst=1; scanf("%s", s+1);
        n=strlen(s+1);
        rep(i, 1, n) add(s[i]-'0');
    }
}

int L[maxn+5];
inline void getL(){
    int u=1, cur_len=0;
    for(int i=1; i<=n; ++i){
        int to=s[i]-'0';
        while(u && !trie[u][to])
            u=fa[u], cur_len=min(cur_len, len[u]);
        if(!u) u=1, cur_len=0;
        else u=trie[u][to], ++cur_len;
        L[i]=i-cur_len+1;
    }
    // rep(i, 1, n) printf("L[%d] == %d\n", i, L[i]);
}

int f[maxn+5], Q[maxn+5], op, ed;
inline bool check(int l){
    op=1, ed=0;
    rep(i, 0, l-1) f[i]=0;
    rep(i, l, n){
        f[i]=f[i-1];
        while(op<=ed && f[Q[ed]]-Q[ed]<f[i-l]-(i-l)) --ed;
        Q[++ed]=i-l;
        while(op<=ed && Q[op]<L[i]-1) ++op;
        if(op<=ed) f[i]=max(f[i], f[Q[op]]-Q[op]+i);
    }
    return f[n]*10>=n*9;
}

inline int bisearch(){
    int l=0, r=n, mid, ret=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) ret=mid, l=mid+1;
        else r=mid-1;
    }
    return ret;
}

signed main(){
    input();
    while(T--){
        scanf("%s", s+1);
        n=strlen(s+1);
        getL();
        int ans=bisearch();
        writc(ans);
    }
    return 0;
}

肆、关键之处 ¶

类似 \(f(i)=\max\{f(j)-j+i,f(i-1)|j \in[L(i)-1,i-l]\}\)，后面的区间左端点满足单调不减的，可以考虑维护单调队列。

单调队列其本质上还是一个最优解覆盖问题，如果解越后面，并且值又很大，那么又排在前面，值又比它小的点就没有必要存在了。

该题在 Luogu 上为黑，但个人赶脚评分虚高，只是知识点稍显高级，但算法上并没有有机结合，更像是拼盘题......大概 蓝+ 差不多？

这篇关于[CTSC2012]熟悉的文章的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航