题解 P1127 【词链】

谷奕勋 · 2020-10-09 15:55:47 · 题解

蒟蒻第一篇题解，写的不好还望见谅。

本蒟蒻看到这个题的第一反应就是深搜（似乎建个图会更简单），为了减少循环次数，首先按照字典序排序，建了一个数组 start 标记每个英文首字母出现的位置。将所有字符串都作为dfs起点，再找到所有以前一个末尾开头的字符串dfs下去，然后就得到了2个大大的TLE。没错，不是所有字符串都能作为起点的。

查阅了一点资料，发现如果有1个字母在首位出现次数比末尾出现次数多一，那么这个字母必将是起始字符串的首字母。如果有两个或以上个这样的字母，那么不可解。如果没有这样的字母，说明形成了Hamilton回路，每个字母对应的所有字符串都可以做dfs起点。最后AC，代码在下面。

PS：这道题好像条件有点水，有些代码有问题也能过，不知道我的代码有没有问题，希望评论区大佬指点一下。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n; int start[30], s1[30]; 
string choose[1005]; string s[1005]; bool vis[1005];

void dfs(string s_now, int acc){
    if(acc == n){
        for(int i = 1; i <= n-1; i++){
            cout<<choose[i]<<".";
        }
        cout<<choose[n];
        exit(0);
        return; 
    }
    char c_now = s_now[s_now.length()-1];
    for(int i = start[c_now - 'a']; i; i++){
        if(s[i][0] != c_now) break;
        if(vis[i]) continue;
        choose[acc+1] = s[i];
        vis[i] = 1;
        dfs(s[i], acc+1);
        vis[i] = 0; 
    }
}
int main(){

    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>s[i];
        s1[s[i][0]-'a']++;
        s1[s[i][s[i].length()-1]-'a']--;

    }
    sort(s+1, s+n+1);

    for(int i = 1; i <= n; i++){
        if(start[s[i][0]-'a'] == 0)
            start[s[i][0]-'a'] = i;
    }
    int k = 0, h;
    for(int i = 0; i < 26; i++){
        if(s1[i] == 1) k++, h = i;
        if(s1[i] == 2 || k == 2) break;
    }
    if(k == 1){
        for(int i = 1; i <= n; i++){
            if(s[i][0] - 'a' == h){
                string s_now = s[i];
                choose[1] = s[i];
                vis[i] = 1;
                dfs(s_now, 1);
                vis[i] = 0;
            }

        }
    }

    if(k == 0){
        for(int i = 1; i <= n; i++){
            choose[1] = s[i];
            vis[i] = 1;
            dfs(s[i], 1);
            vis[i] = 0;
        }
    }
    cout<<"***";
}