P7537 [COCI 2016/2017 #4] Rima 题解

· · 题解

P7537 [COCI 2016/2017 #4] Rima 题解

解题思路

接下来只讨论 |A|\leq|B|。

这道题我们先反转字符串将问题中的“后缀” 变为“前缀” 处理。

由于问题涉及“前缀”，我们构造一个 Trie。

接下来思考一下在 Trie 上两个串满足什么条件可以相邻。

第一种情况，两个串长度不同，则两个串长度相差只能为 1，而且，A 为 B 的前缀。对应到 Trie 上，就是父子结点。

于是，我们得到第一个结论：在 Trie 上，父子结点对应的字符串可以相邻。

第二种情况，两个串长度相同，此时 A 和 B 除最后一个字符外相等即可相邻。 对应到 Trie 上，就是兄弟结点。

于是，我们得到第一个结论：在 Trie 上，兄弟结点对应的字符串可以相邻。

我们已经讨论完了所有情况，接下来需要思考的便是如何构造这个最长字符串序列。

为使思路更易讲解，接下来提到的 Trie 所有结点对应的字符串至少有一个。

在一个 Trie 中的最长字符串序列有两种情况：

  1. 包含根结点。
  2. 不包含根节点。

明显第二种情况可以通过递归求得，我们只处理第一种情况。

显然包含根结点的话，根结点的子结点也都可以选择。

注意到子结点与其子结点可以相邻，但是<该子结点的兄弟结点>不能与<该子结点的子结点>相邻，所以，我们要让<该子结点>隔开<该子结点的子结点>与<该子结点的兄弟结点>。

太绕了，画个图吧：

可是一个点难以隔开三个部分（原有两部分，不能把其他兄弟结点分开形成三个部分），故我们只能让<该子结点的子结点>处于字符串序列的两端。

所以，带孩子的结点只能有两个，并且只能和孩子一起挤在边上。

于是，我们得到的字符串序列长这样：

<子结点 x 的子结点>；<子结点 x>;<一些兄弟结点>；<根结点>；<一些兄弟结点>；<子结点 y>;<子结点 y 的子结点>。

似乎更绕了，再来个图吧：

注意到“子结点的子结点” 也可以是“子结点为根的子树”，但是这个子树是有限制的，这个<子树的子树>与<该子结点的兄弟>不可相邻，同样的也是<子树的子树>的每个结点与<该子结点的兄弟>都不满足相邻的条件。

还是给图吧，语言描述真的很困难：

所以，我们要保证该子树的根一定要在构成的序列的两端，否则一个结点同样无法隔开三个部分（这次是不能隔开子树根的兄弟结点）。

要保证这个，我们需要使该子树根只有一个子结点包含其子树。

具体实现

注意到思路中每个结点要处理两个信息：

显然，两个信息都可以初始化为所有结点都不包含其子树时，字符串序列的最长长度。

然后，找到每个子结点中，让其包含子树后可以提供的更多贡献最多的两个结点。

最大结点和次大结点在第一种情况下都要包含其子树。

第二种情况下显然只有最大结点包含其子树。

注意到上文思路只讨论了 Trie 所有结点对应的字符串至少有一个的情况，一般情况下需要处理的典型细节便是计算子结点允许包含子树时该子结点对应字符串不存在的情况，这时候就没有结点可以隔开子树与子结点的兄弟，该子结点不得包含子树。

直接开始写代码还是比较坐牢，调细节也很折磨，建议看看代码再写：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define N 500005
#define LEN 3000005

int n;
int idx=1,son[LEN][30],tot[LEN];
int dp1[LEN],dp2[LEN]; // dp1: 信息1 dp2: 信息2

void add(char s[])
{
    int len=strlen(s+1);
    int k=1;
    for(int i=1;i<=len;++i)
        if(son[k][s[i]-'a'+1])
            k=son[k][s[i]-'a'+1];
        else
            k=son[k][s[i]-'a'+1]=++idx;
    ++tot[k];
}

void query(int k) // 这里建议好好看看
{
    if(!k)
        return;
    for(int i=1;i<=26;++i) // 先算子结点
        query(son[k][i]);
    int maxs=0,last=0; // 最大值和次大值
    dp1[k]=dp2[k]=tot[k];
    for(int i=1;i<=26;++i)
    {
        // 先初始化为不包含子树
        dp1[k]+=tot[son[k][i]];
        dp2[k]+=tot[son[k][i]];
        if(tot[son[k][i]]) // 注意到要排除没有点隔开不能相邻的两部分的情况，具体两部分是什么请复习思路
        {
            if(dp2[son[k][i]]-tot[son[k][i]]>=maxs)
                last=maxs,
                maxs=dp2[son[k][i]]-tot[son[k][i]];
            else if(dp2[son[k][i]]-tot[son[k][i]]>=last)
                last=dp2[son[k][i]]-tot[son[k][i]];
        }
    }
    dp1[k]+=maxs+last;
    dp2[k]+=maxs;
    for(int i=1;i<=26;++i) // 计算不包含该结点的情况下的最长长度
        dp1[k]=max(dp1[k],dp1[son[k][i]]);
        // 注意到这里不能更新 dp2，因为 dp2 要求需要有一个点来隔开不能相邻的两部分的情况（服务父亲结点的计算），这里如果更新了一个子结点的答案，那么一定不包含该结点
        // 回头注意到上面的 if 还是要特判，因为可能不存在该结点对应的字符串，固然无法满足 dp2 要求，这种情况不得参与计算
}

signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        char<s=new char[LEN];
        scanf("%s",s+1);
        reverse(s+1,s+strlen(s+1)+1);
        add(s);
        delete[] s;
    }
    query(1);
    printf("%d",dp1[1]);
    return 0;
}

Solution record\ First accepted record