洛谷测评机发生了一些有趣的事
查看原帖
洛谷测评机发生了一些有趣的事
307826
Lamorak楼主2021/7/11 21:37

不明所以的爆零,下了个数据一看看,发现输出的数据和数据1一样,本应AC至少数据1但WA

求助,谢谢
#include<bits/stdc++.h>
using namespace std;
const int N=3300000;
int c[N][30],sum[N],head[N],tot,n;
int flag,cnt,ans[N],ans1,vis[30][30],in[30];
struct node{
	int next,v;
}ed[N];
string s[30030];
deque<int>q;

inline void add(int x,int y){
	ed[++tot].next=head[x];
	ed[tot].v=y;
	head[x]=tot;
}

inline void insert(string w){
	int p=0;
	for(int i=0;i<w.size();i++){
		int ch=w[i]-'a';
		if(!c[p][ch]) c[p][ch]=++cnt;
		p=c[p][ch];
	}
	sum[p]=1;
}

inline void query(string w){
	int p=0,ch=0;
	for(int i=0;i<w.size();i++){
		ch=w[i]-'a';
		if(sum[p]){
			flag=1;
			return;
		}
		for(int j=0;j<26;j++){
			if(c[p][j]&&j!=ch&&!vis[ch][j]){
				vis[ch][j]=1;
				add(ch,j);
				in[j]++;
			}
		}
		p=c[p][ch];
	}
}

inline int topu(){
	for(int i=0;i<26;i++){
		if(in[i]==0) q.push_back(i);
	}
	while(!q.empty()){
		int p=q.front();
		q.pop_front();
		for(int i=head[p];i!=-1;i=ed[i].next){
			int t=ed[i].v;
			in[t]--;
			if(!in[t]) q.push_back(t);
		}
	}
	for(int i=0;i<26;i++){
		if(in[i]) return 0;
	}
	return 1;
}

int main(){
	ios::sync_with_stdio(false);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>s[i];
		insert(s[i]);
	}
	for(int i=1;i<=n;i++){
		q.clear();
		flag=0;
		memset(head,-1,sizeof(head));
		memset(in,0,sizeof(in));
		memset(vis,0,sizeof(vis));
		tot=0;
		query(s[i]);
		if(flag) continue;
		if(topu()) ans[++ans1]=i;
	}
	printf("%d\n",ans1);
	for(int i=1;i<=ans1;i++){
		for(int j=0;j<s[ans[i]].size();j++){
			printf("%c",s[ans[i]][j]);
		}printf("\n");
	}
	return 0;
}
//数据一 
//4
//omm
//moo
//mom
//ommnom

//2
//omm
//mom
2021/7/11 21:37
加载中...