题解：P1019 [NOIP 2000 提高组] 单词接龙

yedalong · 2025-02-22 18:00:28 · 题解

Solution

考虑预处理一个数组 g，g_{i,j}=k 表示第 i 个字符串和第 j 个字符串的最小重合长度为 k，0 则表示这两个字符串没有重合。

那么这个 g 该怎样预处理呢？这里介绍一个对于 string 类型的好东西：substr。这函数可以截取一个字符串内你所指定的子串。那么这预处理就很简单了。由于是要让接出来的龙尽可能长，因此，要从小到大枚举字符串 a_i 和 a_j 的重合部分，一有发现，立刻退出循环。

对于搜索部分也挺简单的。对于找到符合条件的字符串搜索下去即可，需要回溯。

AC code

#include <bits/stdc++.h>
using namespace std;
string a[25];int n,maxx,pd[25],g[25][25];
void dfs(string s,int k){
    maxx=max(maxx,(int)s.size());
    pd[k]++;
    for(int i = 1;i<=n;i++){
        if(g[k][i]&&pd[i]<2){
            dfs(s+a[i].substr(g[k][i]),i);
        }
    }
    pd[k]--;
}
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    char s;cin>>s;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            for(int k = 1;k<min(a[i].size(),a[j].size());k++){
                if(a[i].substr(a[i].size()-k,k)==a[j].substr(0,k)){
                    g[i][j]=k;
                    break;
                }
            }
        }
    }
    for(int i = 1;i<=n;i++){
        if(a[i][0]==s){
            dfs(a[i],i);
        }
    }
    cout<<maxx;
}