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

· · 题解

题目传送门：P1019 [NOIP 2000 提高组] 单词接龙。

2025.8.11 第一次修改：调整部分排版；更改、增加一些内容；修改两处笔误。

题意

给出 n，给出 n 个单词，给出一个字符 char，将单词连接成一个长度为 len 且以字符 char 开头的字符串，使得 len 尽可能大，输出 len。

连接时要注意：

思路

搜索。

我们依次枚举所有可能的排列情况，每一次都更新最大长度 len，最后输出。

首先，我们需要一个函数，得到已有的总字符串和新加入的单词的重合部分长度大小（有几位是重合的）。如果这个长度为 0，说明这个单词不能被添加（没有重合部分）。显然，为了使总长度尽可能长，这个连接部分要尽可能小，所以我们从小开始枚举。

ll check(string s1,string s2){
    ll num=min(s1.size(),s2.size());
    for(ll i=1;i<num;i++){//枚举可能的长度
        bool f=true;//用来判断
        for(ll j=0;j<i;j++)//对比每一位
            if(s1[s1.size()-i+j]!=s2[j]){
                f=false;//如果不相同则判断为否
                break;
            }
        if(f==true) return i;//如果判断为正，返回重合部分的长度
    }return 0;//否则说明不能被添加
}

::::info[关于高亮行] 注意这一行的判断：

if(s1[s1.size()-i+j]!=s2[j])

这里 s1.size() 是字符串的长度，s1.size()-i 是字符串倒数第 i 位，也对应新单词的第 0 位，所以字符串的第 s1.size()-i+j 位就对应单词的第 j 位。我们判断字符串的后 i 位和单词的前 i 位是否不同，就要依次判断字符串的倒数第 i 位至最后一位与单词的第一位至第 i 位是否不同。即对于 \forall j \in \{1,2,\dots ,i \}，执行上面的语句判断。 ::::

对于搜索部分，我们依次枚举单词，判断是否能在总字符串后面添加。如果不行，则直接进行下一次循环；否则添加新单词，递归，回溯，再进行下一次循环。当然，如果这个单词已经使用过两次，也直接进行下一次循环。

void dfs(string st,ll num){//num 是当前总字符串的长度
    len=max(num,len);//更新最大长度
    for(ll i=0;i<n;i++){//枚举单词
        if(a[i]>=2) continue;//判断这个单词使用次数
        ll m=check(st,str[i]);//记录重合部分长度
        if(m>0){//如果重合长度大于 0，也就是说可以被添加
            a[i]++;//增加单词使用次数
            dfs(str[i],num+str[i].size()-m);//递归
            a[i]--;//回溯
        }//否则代表没有重合，不操作
    }return;
}

::::info[关于 st] 要强调的是，st 是最近添加的单词，而不是总的字符串。我们前面使用函数计算重合部分长度时，应保证该长度小于前后两个单词的长度。而如果使用总字符串，无法确定上一个单词从哪里开始。（当然，你要是不嫌麻烦也可以再开一个变量存储上一个单词的长度。） ::::

代码实现

刚才思路部分已经给出了主要代码，此处只做必要标记。

// 24ms / 1.04MB / 678B C++98 O2
// 24ms / 816.00KB / 678B C++98
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[20],len,n;//a记录每个单词使用次数
string str[20];//记录每个单词
ll check(string s1,string s2){
    ll num=min(s1.size(),s2.size());
    for(ll i=1;i<num;i++){
        bool f=true;
        for(ll j=0;j<i;j++)
            if(s1[s1.size()-i+j]!=s2[j]){
                f=false;
                break;
            }
        if(f==true) return i;
    }return 0;
}
void dfs(string st,ll num){
    len=max(num,len);
    for(ll i=0;i<n;i++){
        if(a[i]>=2) continue;
        ll m=check(st,str[i]);
        if(m>0){
            a[i]++;
            dfs(str[i],num+str[i].size()-m);
            a[i]--;
        }
    }return;
}
int main(){
    cin>>n;
    for(ll i=0;i<=n;i++)
        cin>>str[i];//特别强调：这里把最后输入的首字母作为单词中的一个输入
    dfs(' '+str[n],1);
    cout<<len;
    return 0;
}