词链

wshz · 2018-05-23 13:01:48 · 题解

/*搜索+技巧+剪枝=AC 该题很像[单词接龙]；(https://www.luogu.org/problemnew/show/P1019) 只要在上面加一点技巧即可AC（同样是深搜）；

#include<bits/stdc++.h>
using namespace std;
int n,l,bj[100001],flag;
string a[10001],k;
map<char,int>bj1,bj2;
void xx(int x,string y)
{
    if(flag==1)
    return ;
    if(x==n)
    {
        flag=1;
        k=y;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(bj[i]==0)
        {
            bj[i]=1;
            if(a[i][0]==y[y.length()-1])/*如果第一
            个字符串的尾字母等于下一个字符串的首字
            母，满足条件将他们拼接；
                xx(x+1,y+"."+a[i]);
            break;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        bj1[a[i][0]]++;//找该字符串的首字母出现的次数；
        bj2[a[i][a[i].length()-1]]++;/*找该字符串
        的尾字母出现的次数；*/
    }
    int q=1;
    sort(a+1,a+n+1);//按字典序排序；
    for(int i=1;i<=n;i++)
    {
        if(bj1[a[i][0]]-bj2[a[i][0]]==1)/*如果该字
        母在字符串开头出现次数比在字符串尾部次数多一那
        么以该字符开头的字符串一定是第一个字符串*/
        {
            q=i;
            break;//找到一个就退出循环；
        }
    }
    bj[q]=1;//标记第一个字符串下标；
    xx(1,a[q]);//深度搜索；
    if(flag==0)//表示没有找到；
    cout<<"***";
    else//已找到；
    cout<<k;
    return 0;
}