【Codeforces Round #445 (Div. 2) D】Restoration of string

给你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 <bits/stdc++.h>

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 <int> 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"<<endl,0;

		}else {

			if (rd[key]>1 || cd[key] >1) return cout <<"NO"<<endl,0;

		}

	special = 0;

	while (1){

		int x = -1;

		if (special!=0) x = special;

		for (int key = 'a';x==-1 && key <= 'z';key++)

			if (inq[key]){

			 	x = key;

			 	break;

			}

		if (x==-1) break;

		tot--;

		inq[x] = 0;

		if (special==x) special = 0;

	 	ans += (char) x;

	 	for (int i = 'a';i <= 'z';i++){

	 	 	if (a[x][i]){

	 	 	 	rd[i]--;

	 	 	 	a[x][i] = 0;

	 	 	 	if (rd[i]==0){

	 	 	 		special = i;

	 	 	 		inq[i] = 1;

	 	 	 	 	rd[i] = -1;

	 	 	 	}else{

	 	 	 	 	return cout <<"NO"<<endl,0;

	 	 	 	}

	 	 	}

	 	}

	}

	if (tot!=0){

		cout <<"NO"<<endl;

	}else{

		cout << ans << endl;

	}

	return 0;

}

巴特西

【Codeforces Round #445 (Div. 2) D】Restoration of string

最新文章

热门文章