《信息学奥赛一本通·高手专项训练》集训 Day 9

luckydrawbox · 2022-08-10 00:16:31 · 个人记录

字典树

\color{#9D3DCF}\text{A. 理解文章}

题目

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 T 是由若干小写字母构成。一个单词 W 也是由若干小写字母构成。一个字典 D 是若干个单词的集合。我们称一段文章 T 在某个字典 D 下是可以被理解的，是指如果文章 T 可以被分成若干部分，且每一个部分都是字典 D 中的单词。

例如字典 D 中包括单词 \texttt{is},\texttt{name},\texttt{what},\texttt{your}，则文章 \texttt{whatisyourname} 是在字典 D 下可以被理解的，因为它可以分成 4 个单词：\texttt{what},\texttt{is},\texttt{your},\texttt{name}，且每个单词都属于字典 D，而文章 \texttt{whatisyouname} 在字典 D 下不能被理解，但可以在字典 D'=D\cup\{\texttt{you}\} 下被理解。这段文章的一个前缀 \texttt{whatis}，也可以在字典 D 下被理解，而且是在字典 D 下能够被理解的最长的前缀。

给定一个字典 D，你的程序需要判断若干段文章在字典 D 下是否能够被理解。并给出其在字典 D 下能够被理解的最长前缀的位置。

题解

P2292 [HNOI2004] L 语言

设 dp_i 表示文章的前缀 T_{1\sim i} 能否被理解，那么我们就可以在字典中的单词组成的 \text{AC} 自动机中进行 \text{DP}，求出每个节点的到根节点经过的边数，即单词长度 dep_i，那么 dp_i\leftarrow dp_{i-dep_j+1}(j\in i\text{ 的所有 fail 前驱})。

注意到 |s| 很小，只有 20，也就是说 \text{AC} 自动机的深度不超过 20，即 \text{fail} 树的深度不超过 20，因此我们可以将其状压计算，减少复杂度。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e6 + 10;
int n, m;
bool f[N];
char s[N];
struct AC {
    int tr[N][26], tot;
    int e[N], fail[N], dep[N], d[N];
    queue<int> q;
    void insert(int len, char *s) {
        int p = 0;
        dep[0] = -1;
        for (int i = 0; i < len; i++) {
            if (!tr[p][s[i] - 'a'])
                tr[p][s[i] - 'a'] = ++tot;
            dep[tr[p][s[i] - 'a']] = dep[p] + 1;
            p = tr[p][s[i] - 'a'];
        }
        e[p] = 1;
        d[p] |= (1 << dep[p]);
    }
    void build() {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        while (q.size()) {
            int p = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (tr[p][i]) {
                    fail[tr[p][i]] = tr[fail[p]][i];
                    d[tr[p][i]] |= d[fail[tr[p][i]]];
                    q.push(tr[p][i]);
                } else
                    tr[p][i] = tr[fail[p]][i];
            }
        }
    }
    int query(int len, char *t) {
        int p = 0, ans = 0, d_ = 1;
        for (int i = 0; i < len; i++) {
            p = tr[p][t[i] - 'a'];
            f[i + 1] = ((d_ & d[p]) > 0);
            d_ <<= 1;
            if (f[i + 1]) {
                d_ |= 1;
                ans = max(ans, i + 1);
            }
        }
        return ans;
    }
} ac;
int main() {
    freopen("paragraph.in", "r", stdin);
    freopen("paragraph.out", "w", stdout);
    f[0] = 1;
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        ac.insert(strlen(s), s);
    }
    ac.build();
    for (int i = 1; i <= m; i++) {
        scanf("%s", s);
        int len = strlen(s);
        for (int j = 1; j <= len; j++) f[j] = 0;
        write(ac.query(len, s));
        putchar('\n');
    }
    return 0;
}

\color{#9D3DCF}\text{B. 区间异或}

题目

给出一个正整数序列 a_1,a_2,…,a_n。求有多少个区间 [l,r](1\le l\le r\le n) 的异或和不小于给定的正整数 K，即求满足

其中 \oplus 表示异或。

的区间 [l,r] 总数。

题解

显然区间异或和可以转化为前缀异或和的异或：sum_{l-1}\oplus sum_{r}。

我们考虑枚举 r，求存在多少个 l-1，满足 sum_{l-1}\oplus sum_{r}\ge K。

和异或序列类似，我们将之前所有的 sum_{l-1} 插入到 \texttt{01 Trie} 中，并在每个节点统计其子树中被标记的节点的数量 val_p，然后拿 sum_r 和 K 在 \texttt{01 Trie} 上跑，设当前走到的节点为 p，sum_r 的当前位为 cr，K 的当前位为 kr，枚举 j\in\{0,1\}：

• 若 j\oplus cr>kr，那么这位为 j 的数必定都大于 K，因此答案加上 val_{ch_{p,j}} 即可。
• 若 j\oplus cr=kr，继续往下递归，若到了被标记的终止节点 p，加上 val_p 即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
int t, n, k, a[N], s[N];
struct Trie {
    int tot;
    struct Tree {
        int son[2];
        int sum;
    } a[N * 30], e;
    Trie() { tot = 1; }
    int search(int x) {
        int p = 1, ans = 0;
        for (int i = 29; i >= 0; i--) {
            int np = 0;
            for (int j = 0; j < 2; j++) {
                if ((j ^ ((x >> i) & 1)) > ((k >> i) & 1) && a[p].son[j])
                    ans += a[a[p].son[j]].sum;
                if ((j ^ ((x >> i) & 1)) == ((k >> i) & 1))
                    np = a[p].son[j];
            }
            p = np;
            if (!p)
                break;
        }
        return ans + (a[p].sum);
    }
    void insert(int x) {
        int p = 1;
        for (int i = 29; i >= 0; i--) {
            if (!a[p].son[((x >> i) & 1)])
                a[p].son[((x >> i) & 1)] = ++tot;
            a[a[p].son[((x >> i) & 1)]].sum++;
            p = a[p].son[((x >> i) & 1)];
        }
    }
} tree;
int main() {
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    t = read();
    while (t--) {
        n = read();
        k = read();
        for (int i = 1; i <= n * 30; i++) tree.a[i] = tree.e;
        tree.tot = 1;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            s[i] = s[i - 1] ^ a[i];
        }
        tree.insert(0);
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += tree.search(s[i]);
            tree.insert(s[i]);
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}

\color{#9D3DCF}\text{C. 背单词}

题目

你是一位喜欢背单词的人。你要学习的单词总共有 n 个，现在我们从上往下完成计划表，对于一个序号为 x 的单词（序号 1\sim x-1 都已经被填入）：

• 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 n\times n 颗泡椒才能学会；
• 当它的所有后缀都被填入表内的情况下，如果在 1\sim x-1 的位置上的单词都不是它的后缀，那么你吃 x 颗泡椒就能记住它；
• 当它的所有后缀都被填入表内的情况下，如果 1\sim x-1 的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 y ，那么你只要吃 x-y 颗泡椒就能把它记住。

小明是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助小明，寻找一种最优的填写单词方案，使得他记住这 个单词的情况下，吃最少的泡椒。

题解

P3294 [SCOI2016]背单词

显然第一种情况的泡椒数远大于第二、三中情况的泡椒数，所以我们要尽量避免这种情况。

后缀问题不好处理，我们可以把所有单词翻转，这样所有的后缀就转化为了前缀。

可以用字典树处理出每个单词的直接前缀单词：它长度最大的前缀。特别地，没有直接前缀单词的单词的直接前缀单词为 0 号单词。

显然，这些直接前缀单词的关系构成一棵树，每个节点的泡椒数只和其在单词表中与父节点的距离有关，为了使泡椒数最小，肯定是让每个节点跟在其父节点后面，且中间不含其他父节点，因此最优的单词表应该是这棵树的一个 \text{dfs} 序。

但是一个父节点会有多个子节点，每个子节点的子树在 \text{dfs} 序中必定会排在该子节点后面，所以在一个 \text{dfs} 序中，一个子节点到其父节点的距离应该是这个子节点之前的子节点构成的子树大小之和 +1，为了使泡椒总数最小，我们可以贪心地讲这些子节点按其构成的子树大小排序，小的在前，大的在后，按这样的顺序进行 \text{dfs}，可以得到最优的填词方案。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10, S = 5.1e5 + 10;
int n, d[N], sze[N];
string s[N];
vector<int> e[N];
ll ans = 0;
struct Trie {
    int tot;
    char standard;
    struct Tree {
        int son[26];
        int end;
    } a[S * 10];
    Trie() {
        tot = 1;
        standard = 'a';
    }
    int search(int id, string str) {
        int len = str.size(), p = 1, ans = 0;
        for (int k = 0; k < len; k++) {
            int ch = str[k] - standard;
            if (!a[p].son[ch])
                return ans;
            p = a[p].son[ch];
            if (a[p].end)
                ans = a[p].end;
        }
        return ans;
    }
    void insert(int id, string str) {
        int len = str.size(), p = 1;
        for (int k = 0; k < len; k++) {
            int ch = str[k] - standard;
            if (!a[p].son[ch])
                a[p].son[ch] = ++tot;
            p = a[p].son[ch];
        }
        a[p].end = id;
    }
} tree;
bool cmp(int x, int y) { return s[x].size() < s[y].size(); }
bool cmp2(int x, int y) { return sze[x] < sze[y]; }
void dfs(int x) {
    for (int i = 0; i < e[x].size(); i++) dfs(e[x][i]);
    sort(e[x].begin(), e[x].end(), cmp2);
    ll sum = 1;
    for (int i = 0; i < e[x].size(); i++) {
        // cout<<e[x][i]<<" "<<sum<<endl;
        ans += sum;
        sum += sze[e[x][i]] + 1;
        sze[x] += sze[e[x][i]];
    }
}
int main() {
    freopen("word.in", "r", stdin);
    freopen("word.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        d[i] = i;
        for (int j = 0; j < s[i].size() / 2; j++) swap(s[i][j], s[i][s[i].size() - j - 1]);
    }
    sort(d + 1, d + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        int f = tree.search(d[i], s[d[i]]);
        e[f].push_back(d[i]);
        tree.insert(d[i], s[d[i]]);
    }
    for (int i = 0; i <= n; i++) sze[i] = e[i].size();
    dfs(0);
    write(ans);
    return 0;
}

AC自动机

\color{#9D3DCF}\text{A. 单词问题}

题目

一篇文章是由许多单词组成的。一个单词会在论文中出现多次，求每个单词在文中出现次数。

题解

P3966 [TJOI2013]单词

把所有单词扔进 \text{AC} 自动机，并把一个单词的所有前缀的节点的答案都加上 1，这样，是一个单词的前缀的单词的答案都加上了，但是，还有不是前缀的子串，他们显然会是前缀的后缀，也就是 fail 数组，把这些子串对应的前缀 fail_p 的答案都加上 ans_p 即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
int n;
string s[210];
struct AC {
    int tr[N][26], tot;
    int sum[N], sum1[N], fail[N], a[N * 10];
    queue<int> q;
    void insert(string s) {
        int p = 0;
        sum[p]++;
        sum1[p] = sum[p];
        for (int i = 0; i < s.size(); i++) {
            if (!tr[p][s[i] - 'a'])
                tr[p][s[i] - 'a'] = ++tot;
            p = tr[p][s[i] - 'a'];
            sum[p]++;
            sum1[p] = sum[p];
        }
    }
    void build() {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        int t = 0;
        while (q.size()) {
            int p = q.front();
            q.pop();
            a[++t] = p;
            for (int i = 0; i < 26; i++) {
                if (tr[p][i]) {
                    fail[tr[p][i]] = tr[fail[p]][i];
                    q.push(tr[p][i]);
                } else
                    tr[p][i] = tr[fail[p]][i];
            }
        }
        for (int i = t; i; i--) {
            sum1[fail[a[i]]] += sum1[a[i]];
        }
    }
    int query(string t) {
        int p = 0, ans = 0;
        for (int i = 0; i < t.size(); i++) {
            p = tr[p][t[i] - 'a'];
        }
        return sum1[p];
    }
} ac;
int main() {
    freopen("word.in", "r", stdin);
    freopen("word.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        ac.insert(s[i]);
    }
    ac.build();
    for (int i = 1; i <= n; i++) {
        cout << ac.query(s[i]) << endl;
    }
    return 0;
}

\color{#9D3DCF}\text{B. 喵星球点名}

题目

小明幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

假设课堂上有 n 个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择 m 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。

然而，由于喵星人的字码如此古怪，以至于不能用 \text{ASCII} 码来表示。为了方便描述，小明决定用数串来表示喵星人的名字。

现在你能帮助小明统计每次点名的时候有多少喵星人答到，以及 m 次点名结束后每个喵星人答到多少次吗？

题解

P2336 [SCOI2012]喵星球上的点名

本来有一个在 \text{OJ} 上满分的做法的，不过复杂度好像假了，于是这里直接给出正解：

先可以把一只喵的名和姓合并在一起，中间插入一个不存在的字符，这样就不需要考虑两个串了。

询问是类似于字符串 x 在字符串 y 中是否出现过。

考虑 \text{AC} 自动机 \text{fail} 树的性质，\text{fail} 指针指向的是最长相同后缀。

如果字符串 A 是字符串 B 的后缀, 那么在 \text{AC} 自动机上面，从 B 开始跳 \text{fail} 树，一定可以跳到 A。

也就是说，B 在 A 的子树内，A 是 B 的祖先。（在 \text{fail} 树上）

判断 A 是否在 B 中出现过，就可以对于 B 的每一个前缀（子串一定是一个前缀的后缀），在 \text{fail} 树上暴力往上跳进行修改或者查询即可。

但是暴力跳 \text{fail} 复杂度可能不太对，但是好像也可以通过此题，这里给出一个复杂度为 O(n \log n) 的做法。

第一问

对于一个名字串的每一个前缀（总前缀个数不超过字符串总长），覆盖它到根的路径（覆盖表示加多次算一次）。

对每一个名字串都这么做，看点名串总共被多少个名字串给覆盖。

树上链修改，单点查询的问题先转化成树上单点修改，子树查询的问题j。

由于覆盖多次算只算一次，就要把覆盖多的部分减掉。

这里有一个小 trick。

对名字串的前缀按 \text{dfs} 序排序，减掉的部分就是每相邻节点的 \text{lca}。

这样就可以做覆盖多次算一次了。

第二问

对于一个名字串的所有一个前缀，看它们总共覆盖了多少点名串。

树上单点修改，链查询的问题先转化串树上子树修改, 单点查询的问题。

同样利用上面的 trick，减掉 \text{dfs} 序相邻节点 \text{lca} 的贡献即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int S = (N + M) << 1;

int n, m;
int namePos[N], queryPos[M];

int last, vcnt = 0;
struct node {
    int fa, fail; // 此处的 fa 为 trie 树上的 fa
    map<int, int> to;
} a[S];

int que[S];
int siz[S], dep[S], son[S], fa[S]; // 此处的 fa 相当于 ac 自动机上的 fail
int dfn[S], top[S], dfc; 
vector<int> g[S];

namespace BIT {
#define lowbit(x) (x & -x)
    int c[S];
    void clear() { memset(c, 0, sizeof c); }
    void update(int p, int v) {
        for(int i = p; i <= dfc; i += lowbit(i))
            c[i] += v;
    }
    int sum(int p) {
        int res = 0;
        for(int i = p; i; i -= lowbit(i))
            res += c[i];
        return res;
    }
    int query(int l, int r) { return sum(r) - sum(l - 1); }
#undef lowbit
} // namespace BIT

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

void extend(int c) {
    int &v = a[last].to[c];
    if(!v) v = ++vcnt, a[v].fa = last;
    last = v;
}

int getFail(int u, int c) {
    if(a[u].to.count(c)) return a[u].to[c];
    else if(!u) return u;
    return a[u].to[c] = getFail(a[u].fail, c);
}

void buildFailTree() {
    int hd = 1, tl = 0;
    for(auto pr : a[0].to)
        que[++tl] = pr.second;
    while(hd <= tl) {
        int u = que[hd++];
        for(auto pr : a[u].to) {
            a[pr.second].fail = getFail(a[u].fail, pr.first);
            que[++tl] = pr.second;
        }
    }
    for(int i = 1; i <= vcnt; ++i)
        g[a[i].fail].push_back(i);
}

void preDfs(int u) {
    siz[u] = 1;
    dfn[u] = ++dfc;
    dep[u] = dep[fa[u]] + 1;
    for(int v : g[u]) if(v != fa[u]) {
        fa[v] = u, preDfs(v);
        siz[u] += siz[v];
        if(!son[u] || siz[v] > siz[son[u]])
            son[u] = v;
    }
}
void getTop(int u, int tp) {
    top[u] = tp;
    if(son[u]) getTop(son[u], tp);
    for(int v : g[u]) if(v != fa[u] && v != son[u]) {
        getTop(v, v); 
    }
}

inline int lca(int u, int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int arr[N], tot;
bool cmp(const int &u, const int &v) { return dfn[u] < dfn[v]; }

void solve1() {
    BIT::clear();
    for(int i = 1, u; i <= n; ++i) {
        u = namePos[i], tot = 0;
        while(u) {
            arr[++tot] = u;
            BIT::update(dfn[u], 1);
            u = a[u].fa;
        }
        sort(arr + 1, arr + tot + 1, cmp);
        for(int j = 1; j < tot; ++j)
            BIT::update(dfn[lca(arr[j], arr[j + 1])], -1);
    }
    for(int i = 1, u; i <= m; ++i) {
        u = queryPos[i];
        printf("%d\n", BIT::query(dfn[u], dfn[u] + siz[u] - 1));
    }
}
void solve2() {
    BIT::clear();
    for(int i = 1, u; i <= m; ++i) {
        u = queryPos[i];
        BIT::update(dfn[u], 1);
        BIT::update(dfn[u] + siz[u], -1);
    }
    for(int i = 1, u, res; i <= n; ++i) {
        u = namePos[i], tot = 0, res = 0;
        while(u) {
            arr[++tot] = u;
            res += BIT::sum(dfn[u]);
            u = a[u].fa;
        }
        sort(arr + 1, arr + tot + 1, cmp);
        for(int j = 1; j < tot; ++j)
            res -= BIT::sum(dfn[lca(arr[j], arr[j + 1])]);
        printf("%d%c", res, " \n"[i == n]);
    }
}

int main() {
    n = read(), m = read();
    for(int i = 1, l, c; i <= n; ++i) {
        last = 0;
        l = read();
        for(int j = 1; j <= l; ++j) {
            c = read();
            extend(c);
        } extend(-1);
        l = read();
        for(int j = 1; j <= l; ++j) {
            c = read();
            extend(c);
        }
        namePos[i] = last;
    }
    for(int i = 1, l, c; i <= m; ++i) {
        last = 0;
        l = read();
        for(int j = 1; j <= l; ++j) {
            c = read();
            extend(c);
        }
        queryPos[i] = last;
    }

    buildFailTree();

    preDfs(0);
    getTop(0, 0);

    solve1();
    solve2();
    return 0;
}

\color{#9D3DCF}\text{C. 禁忌问题}

题目

给定 alphabet ，令字符集为小写字母中前 alphabet 个字母。

再给定一个字符集 A 上的字符串集合 T，T 的大小为 N ，T 中的每一个字符串都被称为禁忌串。

一个字符串的禁忌伤害将按照如下方式计算：将这个字符串划分为若干段，最大化其中是禁忌串的段的数量，则这个禁忌串的段的数量的最大值即为这个字符串的禁忌伤害。

求在字符集 A 上且长度为 len 的字符串的禁忌伤害的期望。

题解

P4569 [BJWC2011]禁忌

设 dp_{i,j} 表示长度为 i 的字符串在 \text{AC} 自动机上走到节点 j 的概率：

• 若 j 是禁忌串的终止节点，那么 dp_{i,1}\leftarrow \frac{dp_{i-1,j}}{alphabet}。
• 若 j 不是禁忌串的终止节点，那么 dp_{i,ch_{j,k}}\leftarrow \frac{dp_{i-1,j}}{alphabet}。