WA 60 pts 求助
查看原帖
WA 60 pts 求助
602803
_qingshu_楼主2024/5/22 09:14

也许是我没有看懂题?错误测试点现实排序后第一个串没有在第一位。下面是数据:

5
ffbcd
abaa
fabbf
fa
abfa
1 4 3 5 2

然后我的程序跑出来是:

DA
bcdefghijklmnopqrstuvwxyza

我认为这个数据只要满足 ff 在 aa 前面即可,有大佬能解释一下错误原因吗?

#include<bits/stdc++.h>
using namespace std;
int n,trie[10010][26],num[10010],tot=1,a[5200010],b[5200010],Rd[5200010],flag[5200010];
vector<int>e[5200010];
string s[520];
inline void add(string t,int id,int now=1){
	for(char i : t){
		int to=i-'a';
		if(!trie[now][to])trie[now][to]=++tot;
		now=trie[now][to];num[now]++;
	}flag[now]=max(flag[now],b[id]);
}
inline void check(string t,int id,int now=1){
	for(int i=0;i<t.size()-1;i++){
		int to=t[i]-'a';now=trie[now][to];
		if(flag[now]>b[id]){
			cout<<"NE";exit(0);
		}
	}
}
inline void build(string t,int now=1){
	for(char i : t){
		int to=i-'a';
		for(int j=0;j<26;j++){
			if(j==to||!num[trie[now][j]])continue;
			cout<<to<<" "<<j<<"\n";
			e[to].emplace_back(j);Rd[j]++;
		}
		now=trie[now][to];num[now]--;
	}
}
string ans;
inline void query(){
	queue<int>q;
	for(int i=0;i<26;i++)if(!Rd[i])q.push(i);
	while(!q.empty()){
		int x=q.front();ans+=x+'a';q.pop();
		for(int v : e[x]){
			Rd[v]--;if(!Rd[v])q.push(v);
		}
	}
	if(ans.size()==26)cout<<"DA\n"<<ans;
	else cout<<"NE";
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	for(int i=1;i<=n;i++){cin>>a[i];b[a[i]]=i;}
	for(int i=1;i<=n;i++)add(s[i],i);
	for(int i=1;i<=n;i++)check(s[i],i);
	for(int i=1;i<=n;i++)build(s[a[i]]);
	query();
} 
/*
aa***
b*bb
ab**a
ab
bb*ab

5
ffbcd
abaa
fabbf
fa
abfa
1 4 3 5 2

*/
2024/5/22 09:14
加载中...