美文网首页
JZOJ5795 2018.08.10【2018提高组】模拟A组

JZOJ5795 2018.08.10【2018提高组】模拟A组

作者: ZJL_OIJR | 来源:发表于2018-08-12 20:47 被阅读0次

    题面

    思路

    水法

    不应该说是水法吧,只是考试的时候可能想不到别的了。
    利用了数据随机性。对所有的S_i建立字典树,并记录字典树上每个点被哪些S_i经过了,这个可以用vector实现。
    对于每次询问,在字典树上跑到对应的节点(没有节点可跑说明T_i不是任何S_i的前缀,此时答案就是n),然后暴力遍历这个节点的vector求出答案。
    复杂度最差是O(nm),由于数据的随机性,就可以过掉。
    (去你***的水法,凭什么满分)

    基于水法优化的正解

    上面做法的瓶颈在于必须用vector存下所经过的S_i集合。但是有必要全部存下来吗?
    题目要求的是数组a里的最长连续0,其实我们可以将问题转化一下:求相邻的1的差值-1的最大值,和n-最后一个1所在位置之差取一个max
    由于字符串是按照编号顺序插入的,我们每次在集合里添加的编号都和上一个添加的编号是相邻的,因此对于字典树上的节点记录两个信息,就可以避免存下整个集合,这两个信息分别是:
    last[i]表示节点i上一次被编号last[i]的字符串经过。
    ans[i]表示节点i的答案。
    复杂度就是字符串总长,与输入同阶。

    Code:

    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    
    inline int max(int a, int b) { return a > b ? a : b; }
    const int LEN = 5e6 + 7;
    
    int n, m, len;
    int root, tot, son[LEN][3], mx[LEN], ans[LEN];
    char str[LEN];
    
    void insert(int ind)
    {
        int now = root;
        for (int i = 1; i <= len; i++)
        {
            if (!son[now][str[i] - 'a']) son[now][str[i] - 'a'] = ++tot;
            now = son[now][str[i] - 'a'];
            ans[now] = max(ans[now], ind - mx[now] - 1);
            mx[now] = max(mx[now], ind);
        }
    }
    int getans()
    {
        int now = root;
        for (int i = 1; i <= len; i++)
        {
            if (!son[now][str[i] - 'a']) return n;
            now = son[now][str[i] - 'a'];
        }
        if (mx[now] == n) return ans[now];
        else return max(ans[now], n - mx[now]);
    }
    
    int main()
    {
        freopen("word.in", "r", stdin);
        freopen("word.out", "w", stdout);
    
        root = ++tot;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%s", str + 1), len = strlen(str + 1), insert(i);
        for (int i = 1; i <= m; i++) scanf("%s", str + 1), len = strlen(str + 1), printf("%d\n", getans());
    
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:JZOJ5795 2018.08.10【2018提高组】模拟A组

          本文链接:https://www.haomeiwen.com/subject/mzljbftx.html