UPC6360 词韵 2018北京冬令营
本文最后更新于 1180 天前,其中的信息可能已经有所发展或是发生改变。

内容纲要

题目描述

Adrian 很喜欢诗歌中的韵。他认为,两个单词押韵当且仅当它们的最长公共 后缀的长度至少是其中较长单词的长度减一。也就是说,单词 A 与单词 B 押韵 当且仅当 LCS(A, B) ≥ max(|A|, |B|) – 1。(其中 LCS 是最长公共后缀 longest common suffix 的缩写)
现在,Adrian 得到了 N 个单词。他想从中选出尽可能多的单词,要求它们能 组成一个单词序列,使得单词序列中任何两个相邻单词是押韵的。

输入

第一行是一个整数N。
接下来N行,每行一个由小写英文字母组成的字符串,表示每个单词。所有单词互不相同。

输出

输出一行,为一个整数,表示最长单词序列的长度。

题解

首先看到LCS可以考虑对字符串逆序建立Trie树,关键在于怎么对于这棵树怎么处理出最长链。
首先我们知道设树上某个节点x作为根节点,对于这个节点构造出的最大单词序列的解ans,应该为
设以x为根的最长链为f[x],次长链为g[x],以x为根的孩子节点为son[x]
则ans = f[x] + g[x] + son[x] + word_end[x] – 2
从字符串结束位置进行树形dp即可

代码

C/C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 3e6 + 1e2;

int sum, f[maxn], g[maxn];
int head[maxn], pcnt = 1, ecnt;
struct Node {
    int num, next;
} edges[maxn];

void addEdge(int s, int e) {
    edges[++ecnt].num = e;
    edges[ecnt].next = head[s];
    head[s] = ecnt;
}

int fa[maxn], sons[maxn], val[maxn];
bool word_end[maxn];
string s;

void trie(const string::reverse_iterator &b, string::reverse_iterator e) {
    int root = 1;
    auto iter = b;
    for (; iter != e; ++iter) {
        bool flag = true;
        auto w = *iter - 'a' + 1;
        for (int i = head[root]; i && flag; i = edges[i].next) {
            if (val[edges[i].num] == w) {
                root = edges[i].num;
                flag = false;
            }
        }
        if (flag) break;
    }
    for (; iter != e; ++iter) {
        f[pcnt] = g[pcnt] = 1;
        val[++pcnt] = *iter - 'a' + 1;
        addEdge(root, pcnt);
        fa[pcnt] = root;
        root = pcnt;
    }
    word_end[root] = true;
    sons[fa[root]]++;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        trie(s.rbegin(), s.rend());
    }
    for (int i = pcnt; i; --i)
        if (word_end[i]) {
            if (f[fa[i]] < f[i] + sons[i]) {
                g[fa[i]] = f[fa[i]];
                f[fa[i]] = f[i] + sons[i];
            } else g[fa[i]] = max(g[fa[i]], f[i] + sons[i]);
        }
    for (int i = pcnt; i; --i) {
        sum = max(sum, f[i] + g[i] + sons[i] + word_end[i] - 2);
    }
    cout << sum << "\n";
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇