[SCOI2016]背单词 题解

[SCOI2016]背单词 题解

题目地址:洛谷:【P3294】[SCOI2016]背单词 – 洛谷、BZOJ:Problem 4567. — [Scoi2016]背单词

题目描述

Lweb 面对如山的英语单词,陷入了深深的沉思,”我怎么样才能快点学完,然后去玩三国杀呢?“。这时候睿智的凤老师从远处飘来,他送给了 Lweb 一本计划册和一大缸泡椒,他的计划册是长这样的:
—————序号 单词—————
1 XXX
2 XXX
……
n-2 XXX
n-1 XXX
n XXX
———————————————
然后凤老师告诉 Lweb ,我知道你要学习的单词总共有 n 个,现在我们从上往下完成计划表,对于一个序号为 x 的单词(序号 1…x-1 都已经被填入):

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

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

输入输出格式

输入格式:
输入一个整数 n ,表示 Lweb 要学习的单词数。接下来 n 行,每行有一个单词(由小写字母构成,且保证任意单词两两互不相同)1<=n<=100000, 所有字符的长度总和 1<=|len|<=510000
输出格式:
Lweb 吃的最少泡椒数

输入输出样例

输入样例#1:

2
a
ba

输出样例#1:

2

题解

如何处理字符串

把字符串翻转一下后缀问题就变成前缀问题了。前缀问题可以用Trie树处理。直接把这些字符串扔进Trie里就好。

贪心

第一种情况明显是最差的。我们可以让这个单词的所有后缀放在它前面来避免这种情况的发生,所以不需要管第一种情况。
第二种情况只会在它没有后缀的情况发生。
第三种情况考虑一种贪心想法,在Trie树上,一个结点的子树为以这个结点为前缀的字符串,统计子树中字符串的数量size,并求出一种DFS序,使得子树小的儿子优先被访问。这样,子树大的儿子中的字符串对答案的贡献将会整体减小。而DFS序保证了前缀都在这个字符串以前。

统计答案

考虑对Trie树简化建树,将不是字符串结尾的结点全部删去,并对新树DFS。每一个儿子对答案的贡献为儿子的DFS序号-父亲的DFS序号。这个可以用当前DFS序号维护一下。写树形DP大概也是可以的?

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long LL;

std::vector<int> gra[510005];
int tot1 = 1, siz[510005], dp[510005];

int ch[510005][26], tot = 1;
bool wrd[510005];

int n;
LL pts = 0, ans = 0;
char str[510005];

inline bool cmp(int a, int b) {
    return siz[a] < siz[b];
}

inline void insert(char* str) {
    int t = 1;
    int len = strlen(str);
    for(int i = len - 1; i >= 0; i--) {
        if(!ch[t][str[i] - 'a']) {
            t = ch[t][str[i] - 'a'] = ++tot;
        } else {
            t = ch[t][str[i] - 'a'];
        }
    }
    wrd[t] = true;
}

inline void rebuild(int fa, int u) {
    if(wrd[u]) {
        gra[fa].push_back(++tot1);
        siz[fa = tot1] = 1;
    }
    for(int i = 0; i < 26; i++) {
        if(ch[u][i]) {
            rebuild(fa, ch[u][i]);
        }
    }
} 

inline void calsize(int u) {
    for(int i = 0; i < gra[u].size(); i++) {
        calsize(gra[u][i]);
        siz[u] += siz[gra[u][i]];
    }
    std::sort(gra[u].begin(), gra[u].end(), cmp);
}

inline void dfs(int u, int w) {
    pts++;
    ans += pts - w;
    w = pts;
    if(wrd[u]) dp[u] = 1;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        dfs(v, w);
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        insert(str);
    }
    rebuild(1, 1);
    calsize(1);
    dfs(1, 1);
    printf("%lld", ans);
    return 0;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据