题解 P1688 新单词接龙问题

LinkWish · 2022-01-23 16:45:25 · 题解

审题

给出 n 个单词，求在符合要求的变换下按字典序排列接龙的最大长度。

其中符合要求的变换有三种：

1.向单词的前面、中间或后面添加一个字母；

2.删除一个字母；

3.将单词中的一个字母变成另一个字母。

思路

这道题和 P4407 [JSOI2009]电子字典很像，都是求一个字符经过一次变换后可以转移到的所有其他字符串。

我们可以使用字典树来记录一个单词是否出现过，然后分类讨论三种变换求出每一个单词可以转移到的所有的单词，最后使用dp求出结果。

变换一

向单词的前面、中间或后面添加一个字母。

我们可以枚举每一个位置上添加每一个字母的情况，然后在字典树上查询原来有没有一个单词和这个变换后的单词一样。

其实我们不用真正地在原单词里面加上这一个字母，我们可以在查询时模拟加上了这一个字母，具体实现如下：

inline int find1(int pos,int change){
    int now=0;
    for(int i=0;i<llen;i++){
        if(i==pos){
            //如果我们正在查询要添加的那一项，我们就先查询添加的值
            if(!trie[now][change])return 0;
            now=trie[now][change];
        }
        if(!trie[now][ch[i]-'a'])return 0;
        now=trie[now][ch[i]-'a'];
    }
    if(pos==llen){
        //特判添加到末尾的情况
        if(!trie[now][change])return 0;
        now=trie[now][change];
    }
    return is[now];//is数组在这里扮演了两个角色：一是标记这是不是一个结束节点，二是这个单词的编号（后同）
}
for(int i=0;i<=len[x];i++){
//枚举添加的位置（注意：我们需要枚举到字符串的长度+1，因为我们枚举的是添加到每一项的前面，遗漏了在单词末尾添加的情况）
    for(int j=0,v;j<26;j++){//枚举每一个字母
        v=find2(x,i,j);
        if(v)can[x].push_back(v);//can数组记录着这个单词可以变换到的所有单词的编号（后同）
    }
}

变换二

删除一个字母。

我们只需要枚举每一个位置，并且在查询时跳过那一个位置即可模拟删除了它的情况。具体实现如下：

inline int find2(int pos){
    int now=0;
    for(int i=0;i<llen;i++){
        if(i==pos)continue;//如果是要删除的哪一位就跳过
        if(!trie[now][ch[i]-'a'])return 0;
        now=trie[now][ch[i]-'a'];
    }
    return is[now];
}
for(int i=0,v;i<len[x];i++){
    v=find1(x,i);
    if(v)can[x].push_back(v);
}

变换三

将单词中的一个字母变成另一个字母。

和变换一二一样，我们不需要真改（当然这个变换可以真改），我们只需要在查询到这一位时用变换后的值去查询就达到了修改的效果。具体实现如下：

inline int find3(int x,int pos,int change){
    int now=0;
    for(int i=0;i<len[x];i++){
        if(i==pos){//到了修改的位置就用改后的值替换
            if(!trie[now][change])return 0;
            now=trie[now][change];
        }
        else{
            if(!trie[now][ch[x][i]-'a'])return 0;
            now=trie[now][ch[x][i]-'a'];        
        }
    }
    return is[now];
}
for(int i=0;i<len[x];i++){
    for(int j=0,v;j<26;j++){
        v=find3(x,i,j);
        if(v)can[x].push_back(v);
    }
}

去重

大家有没有发现一个问题，一个单词可能可以由一个单词通过几种不同的方式变换而来，所以我们需要去重。而去重的方式也很简单，建立 vis 数组用来标记这个变换出来的单词是否被当前这个单词变换出来过。

但是问题来了，如果每一次遍历到一个单词都将 vis 数组清零的话时间复杂度会太大，这个时候我有一种常用的做法，就是将 vis 数组设置为 int 类型，里面存放的是上一次被变换出来的时间，而每一次遍历的时间是唯一的，所以不存在误判。具体实现的话就将每一个 find 函数后面的

return is[now]

替换为

if(is[now]&&vis[now]!=x&&is[now]!=x){//is[now]!=x在这里是为了防止在变换三中变到了自己
    vis[now]=x;
    return is[now];
}
return 0;

dp

这道题的 dp 其实比较好想，题目中数据按字典序排列和答案只能按字典序排列让这道题的 dp 难度大大降低。

设 dp[i] 表示以编号为 i 的单词结尾的最大接龙长度，那么答案就是 \max{dp[i]} 。

动态转移方程为 dp[i]=\max{dp[j]} (1\leqslant j < i,j \in can[i])

具体实现如下：

for(int i=1;i<=n;i++)
    for(int j=0;j<can[i].size()&&can[i][j]<i;j++)
        dp[i]=max(dp[i],dp[can[i][j]]+1);
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    printf("%d",ans);

完整代码如下（转换一和转换二调了下位置）

//Linkwish's code
#include<bits/stdc++.h>
using namespace std;
int n,dp[50010];
int trie[500010][26],vis[500010],cnt,len[50010],is[1000010];
char ch[50010][20];
vector<int> can[25010];
inline void insert(int x){
    int now=0;
    for(int i=0;i<len[x];i++){
        if(!trie[now][ch[x][i]-'a'])trie[now][ch[x][i]-'a']=++cnt;
        now=trie[now][ch[x][i]-'a'];
    }
    is[now]=x;
}
inline int find1(int x,int pos){
    int now=0;
    for(int i=0;i<len[x];i++){
        if(i==pos)continue;
        if(!trie[now][ch[x][i]-'a'])return 0;
        now=trie[now][ch[x][i]-'a'];
    }
    if(is[now]&&vis[now]!=x&&is[now]!=x){
        vis[now]=x;
        return is[now];
    }
    return 0;
}
inline int find2(int x,int pos,int change){
    int now=0;
    for(int i=0;i<len[x];i++){
        if(i==pos){
            if(!trie[now][change])return 0;
            now=trie[now][change];
        }
        if(!trie[now][ch[x][i]-'a'])return 0;
        now=trie[now][ch[x][i]-'a'];
    }
    if(pos==len[x]){
        if(!trie[now][change])return 0;
        now=trie[now][change];
    }
    if(is[now]&&vis[now]!=x&&is[now]!=x){
        vis[now]=x;
        return is[now];
    }
    return 0;
}
inline int find3(int x,int pos,int change){
    int now=0;
    for(int i=0;i<len[x];i++){
        if(i==pos){
            if(!trie[now][change])return 0;
            now=trie[now][change];
        }
        else{
            if(!trie[now][ch[x][i]-'a'])return 0;
            now=trie[now][ch[x][i]-'a'];        
        }
    }
    if(is[now]&&vis[now]!=x&&is[now]!=x){
        vis[now]=x;
        return is[now];
    }
    return 0;
}
inline void init(int x){
    for(int i=0,v;i<len[x];i++){
        v=find1(x,i);
        if(v)can[x].push_back(v);
    }
    for(int i=0;i<=len[x];i++){
        for(int j=0,v;j<26;j++){
            v=find2(x,i,j);
            if(v)can[x].push_back(v);
        }
    }
    for(int i=0;i<len[x];i++){
        for(int j=0,v;j<26;j++){
            v=find3(x,i,j);
            if(v)can[x].push_back(v);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        dp[i]=1;
        scanf("%s",ch[i]);
        len[i]=strlen(ch[i]);
        insert(i);
    }
    for(int i=1;i<=n;i++)init(i);
    for(int i=1;i<=n;i++)sort(can[i].begin(),can[i].end());
    for(int i=1;i<=n;i++)
        for(int j=0;j<can[i].size()&&can[i][j]<i;j++)
            dp[i]=max(dp[i],dp[can[i][j]]+1);
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    printf("%d",ans);
    return 0;
}

update

1/26：将“...然后在字典树上查询元来有没有一个单词和这个变换后的单词一样。”中的“元来”改正为“原来”。