【链接】

【题意】

给你n个字符串。

让你构造一个字符串s。

使得这n个字符串。

每个字符串都是s的子串。

且都是出现次数最多的子串。

要求s的长度最短,且s的字典序最小。

【题解】

如果s是出现最多的子串。

那么s的任意一个子串也都是出现次数最多的子串。

那么考虑"ab"这样一个子串。

则肯定要有字符'a'后面接的一定是'b'

且字符'b'前接的一定是'a'

不然'a'或'b'的出现次数一定会大于"ab"了。

则对于任意一个字符串s,在s[i]和s[i+1]之间建立一条有向边,s[i]->s[i+1];

这就是一个类似拓扑排序的题了。

(如果没办法做拓扑排序,则无解

但是有一定要求。

即每个点的出度和入度一定要是1.

否则,如果有a->b,c->b这种情况。

拓扑排序救过是acb,但是没办法满足a后面紧跟着b.

还有a->c,a->b这种也显然不行,也没办法两者都满足。

然后要优先拓扑有边的点。

比如

"c"

"bd"

则b进入答案之后,下一个应该拓扑的是d而不是"c",因为d是要紧跟在b后面的1

【代码】

#include 
    
     using namespace std;int n;string s;bool bo[300];int a[300][300],rd[300],cd[300],tot = 26;int inq[300],special;queue 
     
       dl;string ans = "";int main(){    #ifdef LOCAL_DEFINE        freopen("F:\\c++source\\rush_in.txt", "r", stdin);    #endif    ios::sync_with_stdio(0),cin.tie(0);    cin >> n;    for (int i = 1;i <= n;i++){        cin >> s;        int len = s.size();        for (int j = 0;j < len;j++) bo[(int)s[j]] = true;        for (int j = 0;j < len-1;j++){            if (a[(int)s[j]][(int)s[j+1]]==0) {                rd[(int)s[j+1]]++;                cd[(int) s[j]]++;            }            a[(int)s[j]][(int)s[j+1]] = 1;                              }    }    for (int key = 'a';key <= 'z';key++)        if (!bo[key]){            rd[key] = cd[key] = -1;            tot--;        }    for (int key = 'a';key <= 'z';key++)        if (rd[key]==0){            inq[key] = 1;            rd[key] = -1;            if (cd[key] > 1) return cout <<"NO"<
      
       1 || cd[key] >1) return cout <<"NO"<