[NOIP2000 提高组] 单词接龙

题目背景

注意：本题为上古 NOIP 原题，不保证存在靠谱的做法能通过该数据范围下的所有数据。

本题为搜索题，本题不接受 hack 数据。关于此类题目的详细内容

NOIP2000 提高组 T3

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 $n$ 表示单词数，以下 $n$ 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

样例 #1

样例输入 #1

5
at
touch
cheat
choose
tact
a

样例输出 #1

23

提示

样例解释：连成的“龙”为 atoucheatactactouchoose。

$n \le 20$。

算法1

(DFS+字符串)

1.由题意可知每个单词最多只能使用两次

因此需要一个mark[]数组来记录每个单词的使用情况

2.判断每一个单词是否能做为龙头

只要单词首字母等于龙的首字母，就可以当龙头。

我们就搜索该单词作为龙头的时候龙的长度

  string s[25];
  for(int i=1;i<=n;i++) 
  cin>>s[i];

  char c;    
  cin>>c;

  for(int i=1;i<=n;i++){
    if(s[i][0] == c){   //判断每一个单词的首字母
        mark[i]++;
        dfs(s[i]);      //以该单词为龙头搜索
        mark[i]--;
    }
}

3.用一个ans,记录一下龙的最长长度。

4.如何判断是否能拼接

第一个字符串从后往前看，s1.substr(len1-i,i);

第二个字符串从前往后看，s2.substr(0,i);

当两个子串相同说明能够连接,连接时把重复的地方去掉一个

注意：不能有包含关系

因此 s1中 len1 - i > 0 ，即 i < len1, 在s2中 i <len2;

由此可见，能得出 i 的范围 i <len1 && i<len2;

//s1 表示目前龙的长度，s2要拼接的单词

string check(string s1,string s2){

    int len1 = s1.size(), len2 = s2.size();
    for(int i = 1; i < len1 && i < len2; i++){
        if(s1.substr(len1-i,i) == s2.substr(0,i))
        return s1.substr(0,len1-i)+s2;  //去掉一个重合的部分
    }

    return "-1";   //拼接不了
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 25;

int n;
string s[N];
int mark[N];   //单词的使用次数 
int ans;

string check(string s1,string s2){

    int len1 = s1.size(), len2 = s2.size();

    for(int i=1;i<len1&&i<len2;i++){
        if(s1.substr(len1-i,i)==s2.substr(0,i))
        return s1.substr(0,len1-i)+s2;
    }

    return "-1";
}

void dfs(string now){
    int k = now.size();
    if(k>ans) ans=k;

    //枚举每一个单词 
    for(int i=1;i<=n;i++){
        if(mark[i]==2) continue; 
        string cmp = check(now,s[i]); 
        if(cmp!="-1"){  //如果拼接成功 
           mark[i] ++;
           dfs(cmp);
           mark[i]--;
        } 
    }

}
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }

    char c;
    cin>>c;

    for(int i=1;i<=n;i++){
        if(s[i][0]==c){  //判断每一个字符串第一个字符 
            mark[i]++;
            dfs(s[i]);
            mark[i]--;   //回退 
        }
    }

    cout<<ans;
    return 0; 
}