全国[切换城市]
登录 | 注册
网站客服：zx81024163 |

洛谷P2336 BZOJ2754 SCOI2012喵星球上的点名题目解析与数串处理技巧

2025-04-25 18:04:02发布    浏览436次    信息编号：226757

友情提醒：凡是以各种理由向你收取费用,均有骗子嫌疑，请提高警惕，不要轻易支付。

洛谷P2336 BZOJ2754 SCOI2012喵星球上的点名题目解析与数串处理技巧

标题地址：Luo Gu：[P2336] []猫星球上的名称 - Luo Gu，Bzoj：2754。 - []猫星球上的名称

问题描述

幸运的是，我被选为从地球到Meow星球的国际学生。他发现猫在上课前的命名现象非常有趣。

假设教室里有N猫，每个猫的名字都由姓氏和名称组成。猫星球上的老师将选择M弦来命名。每次读取字符串时，如果此字符串是猫的姓氏或名称的子字符串，则猫必须回答。

但是，由于猫星的角色太奇怪了，因此不能在ASCII中表达它们。为了简单的描述，决定使用字符串代表猫的名字。

现在，您可以帮助计算每次打电话时有多少猫回答多少猫，以及M呼叫结束后每只猫回答多少次？

输入和输出格式

输入格式：

现在，在Meow星球上定义给定的弦方法：

首先，给出一个正整数L，指示字符串的长度，然后L整数表示字符串的每个字符。

第一行的输入是两个整数N和M。

接下来，有n行，每行包含第i-th猫的姓氏和名称的两个字符串。姓氏和名称都是标准行星上的字符串。

接下来是线m，每条线在猫的行星上包含一个字符串，指示老师命名的字符串。

输出格式：

有多少只猫回答每个老师名字的绳子输出？

然后在最后一行中输出每只猫的单击多少次。

输入和输出示例

输入样本＃1：

2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25

输出示例＃1：

2
1
0
1 2

阐明

对于30％的数据，保证：

1≤n，m≤1000猫星的总长度不得超过4000，并且名称字符串的总长度不得超过2000。

对于100％数据，保证：

1≤n≤20000，1≤m≤50000猫名的总长度和名称字符串的总长度不得超过

确保猫星字符串中的字符数不超过10,000

问题答案交流自动机暴力

考虑AC自动机的暴力方法。首先，由于字符集的大小不确定并且可能很大，因此我们需要考虑按地图保存儿子。然后，由于字符集的大小不确定，我们无法添加虚拟边缘，只能残酷地跳动失败。这导致了Luo ＃11 TLE的最后悲剧。

我们考虑将名称字符串与非法字符匹配并匹配名称。每个匹配项在名称字符串的计数器上为+1，然后计算该名称匹配的数量字符串。

记录是否访问该点的数组非常大。最好不要使用堆栈记录修改后的节点并最终将其重新更改。

我添加了其中的一堆，所有这些都可以避免STL的笔迹修改并增加了架子，但是我仍然无法击败Luogu的＃11 QAQ！

因此，这是交流自动机暴力。我不知道如何失败或SA。就是这样。我将来会学习SA，然后再学习问题A。

抱歉，SA真的可以做她想做的任何事情！

失败树优化

如果我们在交流自动机中使用所有失败指针（非路径压缩）反向创建有向的边缘，我们将获得一棵有向树，其为0作为朝向叶子节点的根方向。使用失败树的相关属性，我们可以将匹配问题转换为树问题并优化复杂性。该算法也可以在此问题中使用。

首先，我们可以添加一个字符，该字符不会出现在名称的中间。在这里，我使用-1，将其插入三角树，然后计算出创建失败树的失败指针。应该注意的是，失败指针不能被路径压缩，因此您只能残酷地跳动才能找到它。为了方便起见，节点编号+1是在后来的创建中处理的，以避免特殊判断0。事实证明，此操作为后续处理造成了很多麻烦，我忘了在许多地方转换+1。有失败树后，我们需要使用失败树的相关属性来解决问题。

对于问题1，它是找出出现模式字符串的文本字符串。该问题可以转化为模式字符串在失败树子树中具有多少个模式字符串的节点。这是因为在文本字符串中出现的模式字符串位置末端的失败指针将指向模式字符串的末端。由于相反的方向，模式字符串的末端指向文本字符串节点，这是一个子树问题。可以将此问题转换为DFS序列上的数字颜色类型问题，这使我们想起了[] HH项链问题，可以通过使用相同的树状阵列 +扫描线来获得。因此，我们需要标记每个节点所属的文本字符串的颜色信息，并处理每个颜色中哪些点的链接列表，以促进扫描线维护信息。如果有很多文本字符串，我们就不能每次都列举每种颜色，因此最好打开链接的列表以记录每个点有多少颜色。链接的列表空间紧凑，适合不确定且不需要随机搜索的统计问题。此外，必须处理子树大小以促进查询间隔的确定。处理上述信息后，这将是上述省级主题选择方法。该部分的复杂性是O（n \ log n）。

对于问题2，请找出文本字符串中出现几个模式字符串。如果我们默认每个节点的初始权重为0，并且在每个模式字符串末端的节点的重量中添加1个，则指向模式字符串根的路径上的点权重的总和是模式字符串的结尾后缀作为模式字符串的数字。如果我们找到并找到从每个节点到文本字符串根的路径的权重总和，我们想要。我们可以使用树链分割的方法 +线段间隔的颜色总和来计算树链，这是O（n \ log^2 n）。如果您只需要一个日志，则可以使用DFS顺序对节点进行排序的顺序，将I-1节点的LCA的路径权重总和添加到树根时，添加I-th节点时。这可以防止对公共路径权重总和进行两次计数，这具有重复数据删除的效果。当使用乘法方法查找LCA时，复杂性可以降低为O（n \ log n）。

但是，让我们仔细考虑一下，这些很长。我们需要Trie树的插入和统计信息。我们需要两个链接列表来维护节点上的颜色类型以及颜色涉及的节点的数量。我们需要一个类似树状的数组，需要树DFS统计树信息，我们需要乘法LCA处理，我们需要一个离线算法来处理间隔的颜色数量，并且我们需要计数算法才能按DFS顺序进行排序和。以上是为此问题编写此解决方案的所有要求，下一步是逐步实施它们。

在实施过程中，我遇到了各种问题。关于我最令人困惑的事情是，当我编写代码时，DFS序列号和节点序列号被困惑，并且节点序列号+1被遗忘了。但是，如果我自己可以实施，我相信编码和调试功能将是一个很好的做法。今天我花了一天的时间在这个话题上工作，我收获了很多。

代码交流自动化暴力

// Code by KSkun, 2018/3
#include 
#include 
#include 
#include 
struct io {
    char buf[1 << 26], *s;
    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }
    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;
#define readint ip.read
const int MAXN = 100005, MAXL = 100005;
int n, m;
std::vector names[MAXN], val[MAXL];
int fail[MAXL], cnt;
std::map ch[MAXL];
int que[MAXL], l, r;
inline void insert(int id) {
    register int len = readint(), p = 0;
    for(register int i = 0; i < len; i++) {
        int t = readint();
        if(!ch[p][t]) ch[p][t] = ++cnt;
        p = ch[p][t];
    }
    val[p].push_back(id);
}
inline void calfail() {
    l = r = 0;
    fail[0] = 0;
    for(std::map::iterator it = ch[0].begin(); it != ch[0].end(); it++) {
        register int u = it->second;
        que[r++] = u;
        fail[u] = 0;
    }
    while(l != r) {
        register int u = que[l++];
        for(std::map::iterator it = ch[u].begin(); it != ch[u].end(); it++) {
            int t = it->first, v = it->second, p = fail[u];
            while(p && !ch[p][t]) p = fail[p];
            fail[v] = ch[p][t];
            que[r++] = v;
        }
    }
}
int ctn[MAXN], qur[MAXN];
bool vis[MAXL];
int sta[MAXL], stot;
inline int calcnt(int p) {
    register int res = 0;
    for(; p; p = fail[p]) {
        if(vis[p]) break;
        vis[p] = true;
        sta[++stot] = p;
        for(register int i = 0; i < val[p].size(); i++) {
            res++;
            qur[val[p][i]]++;
        }
    }
    return res;
}
inline void query(int id) {
    register int p = 0;
    stot = 0;
    for(register int i = 0; i < names[id].size(); i++) {
        int t = names[id][i];
        while(p && !ch[p][t]) p = fail[p];
        p = ch[p][t];
        ctn[id] += calcnt(p);
    }
    for(register int i = 1; i <= stot; i++) {
        vis[sta[i]] = false;
    }
}
int main() {
    n = readint(); m = readint();
    for(register int i = 1; i <= n; i++) {
        register int len = readint();
        while(len--) names[i].push_back(readint());
        names[i].push_back(-1);
        len = readint();
        while(len--) names[i].push_back(readint());
    }
    for(register int i = 1; i <= m; i++) {
        insert(i);
    }
    calfail();
    for(register int i = 1; i <= n; i++) {
        query(i);
    }
    for(register int i = 1; i <= m; i++) {
        printf("%d\n", qur[i]);
    }
    for(register int i = 1; i <= n; i++) {
        printf("%d ", ctn[i]);
    }
    return 0;
}

失败树优化（带有笔记）

// Code by KSkun, 2018/5
#include 
#include 
#include 
#include 
#include 
#include 
typedef long long LL;
inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}
inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}
const int MAXN = 200005;
// 双向链表 
struct LinkedList {
    int head[MAXN], tail[MAXN], val[MAXN], pre[MAXN], nxt[MAXN], tot;
    LinkedList() {
        tot = 0;
    }
    // 在p所属的链表头部插入v这个值 
    inline void insert(int p, int v) {
        tot++; 
        if(!tail[p]) tail[p] = tot;
        val[tot] = v; if(head[p]) pre[head[p]] = tot; nxt[tot] = head[p]; head[p] = tot;
    }
} col, col2;
// 树状数组 
struct BinaryIndexTree {
    int tr[MAXN];
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int x, int v) {
        for(int i = x; i < MAXN; i += lowbit(i)) {
            tr[i] += v;
        }
    }
    inline int query(int x) {
        int res = 0;
        for(int i = x; i; i -= lowbit(i)) {
            res += tr[i];
        }
        return res;
    }
} bit;
// 字符集太大，用map存儿子省空间 
std::map ch[MAXN];
std::queue que;
std::vector gra[MAXN]; // fail树存在这里 
int fail[MAXN], ecnt[MAXN], end[MAXN], tot;
// Trie树的插入，分别处理文本串和模式串 
inline void insert(std::vector &str, int id, bool isname) {
    int p = 0;
    for(int i = 0; i < str.size(); i++) {
        int t = str[i];
        if(!ch[p][t]) {
            ch[p][t] = ++tot;
        }
        if(isname) {
            // 统计每个节点上的颜色种类 
            col.insert(ch[p][t] + 1, id);
        }
        p = ch[p][t];
    }
    if(!isname) {
        // 统计一个节点是多少模式串的结尾，模式串可能有多个相同不可用bool 
        ecnt[p + 1]++; end[id] = p + 1;
    }
}
// 计算fail数组 
inline void calfail() {
    for(std::map::iterator it = ch[0].begin(); it != ch[0].end(); it++) {
        que.push(it->second);
        gra[1].push_back(it->second + 1);
    }
    while(!que.empty()) {
        int p = que.front(); que.pop();
        for(std::map::iterator it = ch[p].begin(); it != ch[p].end(); it++) {
            int t = fail[p], q = it->second;
            // 暴力跳fail计算 
            while(!ch[t][it->first] && t) t = fail[t];
            fail[q] = ch[t][it->first];
            gra[ch[t][it->first] + 1].push_back(q + 1);
            que.push(q);
        }
    }
}
int anc[MAXN][20], siz[MAXN], dfn[MAXN], dep[MAXN], ptn[MAXN], sum[MAXN], clk;
// DFS处理fail树信息 
inline void dfs(int u) {
    siz[u] = 1; dfn[u] = ++clk; ptn[dfn[u]] = u;
    sum[u] = sum[anc[u][0]] + ecnt[u];
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == anc[u][0]) continue;
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        dfs(v);
        siz[u] += siz[v];
    }
}
int n, m;
struct Query {
    int id, l, r;
    inline bool operator<(const Query &rhs) const {
        return l == rhs.l ? r < rhs.r : l < rhs.l;
    }
} qur[MAXN];
// 第一个问题
int ans1[MAXN];
inline void main1() {
    // 按DFS序处理出每个颜色的链表 
    for(int i = 1; i < MAXN; i++) {
        for(int j = col.head[ptn[i]]; j; j = col.nxt[j]) {
            int c = col.val[j];
            col2.insert(c, i);
        }
    }
    // 初始化询问以及对询问排序 
    for(int i = 1; i <= m; i++) {
        qur[i] = Query {i, dfn[end[i]], dfn[end[i]] + siz[end[i]] - 1};
    }
    // 初始化树状数组，在每个颜色的初位置+1 
    for(int i = 1; i <= n; i++) {
        bit.add(col2.val[col2.tail[i]], 1);
    }
    std::sort(qur + 1, qur + m + 1);
    int lst = 1;
    // 同[SDOI2009]HH的项链
    for(int i = 1; i <= m; i++) {
        if(lst != qur[i].l) {
            for(int j = lst; j < qur[i].l; j++) {
                for(int k = col.head[ptn[j]]; k; k = col.nxt[k]) {
                    int c = col.val[k];
                    bit.add(j, -1);
                    col2.tail[c] = col2.pre[col2.tail[c]];
                    if(col2.val[col2.tail[c]]) bit.add(col2.val[col2.tail[c]], 1);
                }
            }
            lst = qur[i].l;
        }
        ans1[qur[i].id] = bit.query(qur[i].r);
    }
    for(int i = 1; i <= m; i++) {
        printf("%d\n", ans1[i]);
    }
}
// 倍增LCA
inline void preparelca() {
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i < MAXN; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}
inline int querylca(int x, int y) {
    if(dep[x] > dep[y]) std::swap(x, y);
    int del = dep[y] - dep[x];
    for(int i = 19; i >= 0; i--) {
        if(del & (1 << i)) {
            y = anc[y][i];
        }
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--) {
        if(anc[x][i] != anc[y][i]) {
            x = anc[x][i]; y = anc[y][i];
        }
    }
    return anc[x][0];
}
// 第二个问题 
std::vector name[MAXN];
int ans2[MAXN];
inline bool cmp(int a, int b) {
    return dfn[a] < dfn[b];
}
inline void main2() {
    for(int i = 1; i <= n; i++) {
        int p = 0;
        // 将字符串换成该字符串的节点 
        for(int j = 0; j < name[i].size(); j++) {
            p = ch[p][name[i][j]];
            name[i][j] = p + 1;
        }
        // 按DFS序计算树链的并的权值和 
        std::sort(name[i].begin(), name[i].end(), cmp);
        for(int j = 0; j < name[i].size(); j++) {
            ans2[i] += sum[name[i][j]];
            if(j) ans2[i] -= sum[querylca(name[i][j], name[i][j - 1])];
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", ans2[i]);
    }
}
int len;
std::vector s;
int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        s.clear();
        len = readint();
        while(len--) {
            s.push_back(readint());
        }
        s.push_back(-1);
        len = readint();
        while(len--) {
            s.push_back(readint());
        }
        insert(s, i, true);
        name[i] = s;
    }
    for(int i = 1; i <= m; i++) {
        s.clear();
        len = readint();
        while(len--) {
            s.push_back(readint());
        }
        insert(s, i, false);
    }
    calfail();
    dfs(1);
    preparelca();
    main1();
    main2();
    return 0;
}

相关阅读：
本文链接：https://www.xkyczp.com/detail/226757.html

提醒：请联系我时一定说明是从星空网上看到的！

最新发布