题解 P7861 [COCI2015-2016#2] SAVEZ

ADay · 2021-10-20 22:10:32 · 题解

更逊的阅读体验

模拟赛原题，赛时一直在肝另一题就没做

Solution

求最长子序列的题，显然可以 \mathsf{dp}，方程为 f_i=\max\limits_{j<i}\{f_j\}+1(x_j\,\text{为}\,x_i\,\text{的前缀和后缀})。

考虑怎么判断一个字符串为另一个字符串的的前缀和后缀。我们有一个很妙的做法：把字符串 s_{1\cdots n} 正反合在一起组成 n 个字符二元组，即 (s_1,s_n)(s_2,s_{n-1})\dots(s_n,s_1)，那么这样就只用判断 x_j 组成的二元组是否是 x_i 的二元组的前缀就好了。

对于这些二元组，我们可以直接建 \mathsf{Trie}，把每个字符串的二元组当成一个字符集为 26\times26 的字符串插入，在插入的过程中如果当前节点是某个字符串的结尾就直接进行 \mathsf{dp}，并在插入完时的结点记录此字符串编号即可。

关于实现，由于这棵 \mathsf{Trie} 的每条边有两个字符 ab，我们可以把它转化为一个数 (a-'A')*26+(b-'A')，并用 \mathsf{unordered\_map} 实现动态开点的子节点列表。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,ans,tot,f[N],id[N];char s[N];
unordered_map<int,unordered_map<int,int>>g;//Trie
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);m=strlen(s+1);
        int u=0;
        for(int j=1;j<=m;j++){
            f[i]=max(f[i],f[id[u]]+1);
            int w=(s[j]-'A')*26+s[m-j+1]-'A';//正反合并
            if(g[u].find(w)==g[u].end())g[u][w]=++tot;//动态开点
            u=g[u][w];
        }if(id[u])f[i]=max(f[i],f[id[u]]+1);
        ans=max(ans,f[i]);id[u]=i;
    }printf("%d\n",ans);
    return 0;
}

最后祝各位 \texttt{CSP2021 rp++!}