题解 P5270 【无论怎样神树大人都会删库跑路】

龙之吻—水货 · 2019-03-24 15:29:32 · 题解

无论怎样神树大人都会删库跑路

题目大意

中文题面自己去读吧 QwQ

一句话题解

Hash + 双端队列模拟。

解题报告

这道题，首先比较显然的一点是 : 只有字符串 x 长度为 T 的后缀是可能产生贡献的。

所以只需要去维护 x 的后 T 位中，每种数字出现的个数。同时考虑到前 60pts 的字符集都特别小。我们完全可以使用双端队列 + 桶来模拟这个过程。

也就是每次从尾部加入字符，从头部删除字符。

for (register int i = 1; i <= q; i++) {
    int now = r[i % m + 1];
    for (register int j = 1; j <= len[now]; j++) {
        qu.push(a[now][j]);
        tot[a[now][j]]++;
    }
    while (qu.size() > (unsigned)t) {
        tot[qu.front()]--;
        qu.pop();
    }
 }

这样就有 20pts 了！

但是，显然，对于 Q 比较大的情况，上述方法并不适用。

但是我们发现每次操作是每 m 个一循环的，所以当 x 的长度大于 T 的时候，进行第 i 操作和进行第 i+m 次操作对答案的贡献是一样的。

这样我们就可以先进行几轮操作使得 x 的长度大于 T，然后在进行一轮操作求出 sum[i] 表示从第 1 个操作到第 i 个操作中有多少个操作对答案产生了贡献。

同时，我们还发现，对于前 60pts，有 R_i = i，因此插入的字符个数是 O(字符串总长) 级别的。

相比之前的 20pts 做法只多了几句话。

for (register int i = 1; i <= m; i++) {
    int now = r[i];
    for (register int j = 1; j <= len[now]; j++) {
        qu.push(a[now][j]);
        tot[a[now][j]]++;
    }
    while (qu.size() > (unsigned)t) {
        tot[qu.front()]--;
        qu.pop();
    }
    res[i] = res[i - 1] + check();
 }
ans += res[m] * (q / m);
ans += res[q % m];

现在我们考虑满分做法，从 60pts 到满分有两个问题，首先是字符集大小变成了 10^5 这样的话每次判断的复杂度过高；然后是插入的字符串没有保证，可能连续 m 次都要求插入同一个长度为 10^5 的字符串，复杂度依然爆炸。。。

先尝试解决第一个问题，显然 hash 是解决第一个问题比较好的方法之一。

这里我们使用最普通的 hash，也就是 hash_s = \sum_{i=0}s[i] \times base^i，至于是自然溢出，单模数，双模数，还是 n 模数不作介绍。

把用于储存数字的桶当成一个字符串 hash 掉，在这里我们会用到 hash 的一个性质，我们用一个字符串的 hash 值减去另一个字符串的 hash 会得到两个字符串按位相减的到的字符串的 hash 值， 相加同理。

举个栗子就是 ：

当然，需要保证第一个字符串的每一位都大于第二个字符串的相应位置，以及要保证加出来的数小于 base 。

利用这个性质，还可以得出来 :