76pts性感代码在线求条,WA
查看原帖
76pts性感代码在线求条,WA
752094
MornHus楼主2023/10/24 20:37
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
	return x*f;
}
int n,k,tot;
int ans;
int trie[300005][27];
string a[30005];
int End[300005];
int len[300005];

int vis[30];
int ind[30];
vector<int>g[30];

queue<int>ansq;

bool topo(){
	queue<int>q;
	for(int i=0;i<26;i++)if(!ind[i]&&vis[i])q.push(i);
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int i=g[now].size()-1;i>=0;i--){
			int to=g[now][i];
			ind[to]--;
			if(!ind[to]){
				q.push(to);
			}
		}
	}
	for(int i=0;i<26;i++){
		if(ind[i])return 1;
	}
	return 0;
}


inline void reset(){
	memset(vis,0,sizeof(vis));
	memset(ind,0,sizeof(ind));
	for(int i=0;i<26;i++)g[i].clear();
}
int main(){
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	n=read();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int now=0;
		len[i]=a[i].length();
		for(int j=0;j<len[i];j++){
			if(trie[now][a[i][j]-'a']){
				now=trie[now][a[i][j]-'a'];
			}else{
				trie[now][a[i][j]-'a']=++tot;
				now=tot;
			}
		}
		End[now]++;
	}
	//done
	for(int i=1;i<=n;i++){//逐个分析字符串,作为字典序第一,建图,拓扑 
		reset();
		int now=0;	
		for(int j=0;j<len[i];j++){
//			cout<<now<<' ';
			int u=a[i][j]-'a';
			vis[u]=1;
			for(int v=0;v<26;v++){
				if(v!=u&&trie[now][v]){
					vis[v]=1;
	//				cout<<u<<" -> "<<v<<endl; 
					g[u].push_back(v);
					ind[v]++;
				}
			}
			now=trie[now][a[i][j]-'a'];
		}		
		if(!topo()){
			ans++;
	//		cout<<endl<<i<<endl;
			ansq.push(i);
		}
//		cout<<"\n---------\n";
	}
	cout<<ans<<endl;
	while(!ansq.empty()){
		cout<<a[ansq.front()]<<'\n';
		ansq.pop();
	}
	return 0;
}
/*
建立一颗字典树

然后设每个字符串是字典序最小的,也就是第i个字母在i层中最小

连边,判环

O(26m)复杂度,足以AC 
*/
2023/10/24 20:37
加载中...