P1019 单词接龙

题目

https://www.luogu.org/problemnew/show/P1019

思路

单词接龙,如果一个单词的末尾与另一个单词的开头有重叠的部分,那么这两个单词就可以连接起来。
这道题要求,在给定单词“龙头”的情况下求最长的“龙”的长度。
对于这样的题目,很容易地可以想到全局搜一遍,记录最长地即可。
但在做这道题过程中,有3个我没有注意到地地方:

  • 题目中说每个单词可以被使用两次,我的处理方法是,将给的所有的单词复制一份,这样对每个单词去搜就行了,但交上去却RE了,可能是递归层次太深,而每次递归都要申请空间造成内存超限。解决方法是用个计数数组统计访问次数。
  • 题中说“相邻的两部分不能存在包含关系,例如atat 和 atideatide 间不能相连。”,在这个地方,我一直在想该怎么判断它们是否有包含关系,但实际上是不要的,因为如果前一个单词能被后一个单词包含,那么直接与后一个单词相连就好了;再者,如果后一个单词被前一个单词包含,那么在连接后可以发现前一个单词的长度是不会发生改变的,这样就可以把这条递归线剪掉。
  • 在两个单词相连时,其重合部分合为一部分。这句话我理解的意思是将最长的重合部分求出来,但实际上是不对的,求的应该是最小的重叠部分。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    /*
    https://www.luogu.org/problemnew/show/P1019
    AC
    */

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

    const int MAXN=1e5+10;

    int visit[100];
    char str[100][MAXN];

    int n;
    int ans;

    void DFS(char t[]) {
    for(int i=1;i<=n;i++) {

    if(visit[i]==2)
    continue;
    int j=0;
    int len1=strlen(t);
    int len2=strlen(str[i]);

    ans=max(ans,len1);
    bool flag=false;
    for(int key=1;key<len2;key++) {
    // cout<<"KKK"<<endl;
    char tmpx[1000],tmpy[1000];
    int x,y;
    for(x=0;x<key;x++)
    tmpx[x]=str[i][x];
    tmpx[x]='\0';
    int cnt=0;
    for(y=len1-key;y<len1;y++)
    tmpy[cnt++]=t[y];
    tmpy[cnt]='\0';
    if(strcmp(tmpx,tmpy)==0) {
    char p[MAXN];
    strcpy(p,t);
    int tmpLen=len1;
    for(int q=key;q<len2;q++)
    p[len1++]=str[i][q];
    p[len1]='\0';
    // printf("%s %d\n",t,len1);
    // if(tmpLen==len1)
    // continue;
    ans=max(ans,len1);
    visit[i]++;
    flag=true;
    DFS(p);
    visit[i]--;
    }
    // if(flag) break;
    }
    }
    }
    int main() {
    // freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%s",str[i]);

    char head[3];
    scanf("%s",head);
    ans=0;
    memset(visit,0,sizeof(visit));
    DFS(head);
    printf("%d\n",ans);
    return 0;
    }
-------------本文结束感谢您的阅读-------------
0%