48分求助,真的看不出什么问题了。。。
查看原帖
48分求助,真的看不出什么问题了。。。
430202
_DtrIsta3int楼主2022/11/9 19:12

WA #4 #8-12.

思路:对每一个字符串做判断,Diff是遍历到当前时不同的字符的个数,如果第一次出现该字母,则将该字母的优先度设为++Diff(优先度就是在自定义字母表中的顺序),然后查找该节点的兄弟节点优先度小于该节点的情况是否存在,如果存在则说明无法找到合适的顺序,否则继续,以及若该字符串是某字符串的子串也无法成为字典序最小。

样例也过了,感觉思路没什么问题,求Hack数据或思路纠正。。。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXLEN 300009
class Trie
{
public:
	int next[27] = { 0 };
	int time = 0;
	int islast = 0;
}T[MAXLEN];
int space = 0, m, ans = 0, f[27];
string str[30007];
bool isvalid[30007], isfirst[27];
int TrieInsert(string a)
{
	int len = a.size(), next = 0, index;
	for (int temp = 0; temp < len; temp++)
	{
		index = a[temp] - 'a' + 1;
		if (!T[next].next[index])T[next].next[index] = ++space;
		next = T[next].next[index];
	}
	T[next].islast++;
	return next;
}
bool TrieFirst(string a)
{
	int len = a.size(), next = 0, index, diff = 0;
	for (int temp = 0; temp < len; temp++)
	{
		index = a[temp] - 'a' + 1;
		if (!isfirst[index])
		{
			isfirst[index] = true;
			diff++;
			f[index] = diff;
		}
		for (int t = 1; t <= 26; t++)
		{
			if (T[next].next[t] && f[t] < f[index])
			{
				return false;
			}
		}
		if (T[next].islast)
		{
			return false;
		}
		next = T[next].next[index];
	}	
	ans++;
	return true;
}
int main()
{
	cin >> m;
	for (int temp = 0; temp < m; temp++)
	{
		cin >> str[temp];
		TrieInsert(str[temp]);
	}
	for (int temp = 0; temp < m; temp++)
	{
		memset(isfirst, false, sizeof(isfirst));
		memset(f, 30, sizeof(f));
		isvalid[temp] = TrieFirst(str[temp]);
	}
	cout << ans << endl;
	for (int temp = 0; temp < m; temp++)
	{
		if (isvalid[temp])cout << str[temp] << endl;
	}
	return 0;
}
2022/11/9 19:12
加载中...