题解：P13108 [GCJ 2019 #1A] Alien Rhyme

DevilsFlame · 2025-07-23 13:58:47 · 题解

据题目要求，我们的字典树当然是反着建。

之后，我们会得到一棵树，我们拿样例 3 举例：

标红的就是一个结尾。

我们要使得每个单词只与它的配对单词押韵，并且不与其他配对中的单词押韵。就是在原有的字符串选择一段后缀，使得有且只有唯一一个字符串所选出的后缀与之相同。
不难想到贪心策略：让后缀越长越好。因为后缀越短，越有相同的可能。

int dfs(int x) {
    int res = g[x];
    for(int i = 0;i < 26;i ++) if(t[x][i]) res += dfs(t[x][i]);
    if(res > 1) ans += 2,res -= 2;//满足已有两个字符串此时后缀相同，加入答案
    return res;//多余的留到之后计算答案
}

有一细节，后缀不能为空串，不需要我多说。注意多组数据要清空。

        for(int i = 1;i <= n;i ++) {
            string a;
            cin >> a;
            add(a);
        }
        for(int i = 0;i < 26;i ++) if(t[0][i]) n = dfs(t[0][i]);//这里n的赋值没有意义，只是满足int类型函数返回值
        cout << "Case #" << tt << ": " << ans << '\n';