题解：P1019 [NOIP 2000 提高组] 单词接龙（疑似错题）

whl666666 · 2025-08-18 13:09:22 · 题解

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

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

蒟蒻的第一篇题解(管理求大大过QAQ)

1.DFS核心

• 每层递归更新最大长度。

• 使用次数限制（≤2次）。

• 标准回溯模板：标记→递归→撤销。

  void f(string c, int x){     // c:当前字符串 x:当前长度
  m=max(m,x);              // 更新最大长度记录
  
  for(int i=0;i<n;i++)     // 尝试所有单词
      if(v[i]<2)           // 使用限制≤2次
          if(int k=o(c,s[i]))  // 计算重叠长度k
              v[i]++,      // 标记使用
              f(s[i],x+s[i].size()-k), // 递归
              v[i]--;     // 回溯
  }

  2.初始化

int main(){
    cin>>n;                  // 读取单词数量n
    for(int i=0;i<n;i++)     // 读取n个单词
        cin>>s[i];           // 存储到字符串数组s中
    char c;cin>>c;           // 读取起始字母c

    for(int i=0;i<n;i++)     // 遍历所有单词
        if(s[i][0]==c)       // 如果单词首字母匹配
            v[i]++,          // 标记该单词已使用1次
            f(s[i],s[i].size()),  // 开始DFS
            v[i]--;          // 回溯
    cout<<m;                 // 输出最大长度
}

3.触发条件

仅处理首字母匹配的单词作为搜索起点

时间复杂度：O(n! × n × L)
空间复杂度：O(n×L + n)

其中L为平均单词长度

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,l,v[20];
string s[20];
int o(string a,string b){
    for(int i=1;i<min(a.size(),b.size());i++)
        if(a.substr(a.size()-i)==b.substr(0,i))
            return i;
    return 0;
}
void dfs(string c,int x){
    m=max(m,x);
    for(int i=0;i<n;i++)
    if(v[i]<2)
        if(int k=o(c,s[i])){
            v[i]++;
        dfs(s[i],x+s[i].size()-k);
        v[i]--;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>s[i];
    char c;
    cin>>c;
    for(int i=0;i<n;i++)
        if(s[i][0]==c){
            v[i]++;
            dfs(s[i],s[i].size());
            v[i]--; 
        }
    cout<<m;
}