P3065 [USACO12DEC]First! G

和之前那个题目很像

https://www.cnblogs.com/wzxbeliever/p/16087337.html

我想的是

先建立字典树 依次判断每个字符串 对于同一深度 只要满足该字符比其他字符前面就好

到这里都是没问题的 我开始想的是每层依次判断26个字母满不满足 于是开心的提交了 发现tle

于是发现了问题 每层会浪费很多比较 所以想办法改进 和上面那个题目一样 用拓扑排序

当出现环的时候 那一定是不能满足的 最后还要特判一下是否该字符串前缀为另一个字符串 如果是的话 那肯定是没法满足的

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=3e4+5;
int n,cnt,ans;
int inn[30],sum[maxn*26],pd[maxn],tr[maxn*26][26];
string s[maxn];
vectorQ[30];
void insert(string);
void tp();
bool ck(string);
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>s[i],insert(s[i]);
	for(int i=1;i<=n;i++)
	if(ck(s[i]))ans++,pd[i]=1;
	cout<q;
void tp(){
	while(!q.empty())q.pop();
	for(int i=0;i<26;i++)
	if(!inn[i])q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i