算法时间复杂度应该是对的,但是T了
查看原帖
算法时间复杂度应该是对的,但是T了
305891
Eraine楼主2022/4/23 17:27

是程序内部有问题吗?会不会是出现了死循环?

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int tot=1;
struct Tree{
	pair<int,int>ch[27];
	int sum;
	int seq;
	void add(int id){
		ch[++ch[0].second].second=id;
	}
}tree[100005];
bool cmp(pair<int,int>x,pair<int,int>y){
	return x.first<y.first;
}
void sorting(int id){
	for(int i=1;i<=tree[id].ch[0].second;i++){
		sorting(tree[id].ch[i].second);
		tree[id].ch[i].first=tree[tree[id].ch[i].second].sum;
		tree[id].sum+=tree[id].ch[i].first;
	}
	sort(tree[id].ch+1,tree[id].ch+tree[id].ch[0].second+1,cmp);
	tree[id].sum++;
}
int now;
ll ans;
void dfs(int id){
	int dep=now;
	for(int i=1;i<=tree[id].ch[0].second;i++){
		now++;
		ans+=(ll)(now-dep);
		dfs(tree[id].ch[i].second);
	}
}
struct Trie{
	int root=1,cnt=1;
	int trie[510005][26];
	bool val[510005];
	void insert(char s[]){
		int p=1,len=strlen(s+1);
		for(int i=len;i;i--){
			if(!trie[p][s[i]-'a'])
				trie[p][s[i]-'a']=++cnt;
			p=trie[p][s[i]-'a'];
		}
		val[p]=true;
	}
	int ans;
	void solve(int id,int p){
		if(val[id]){
			tree[p].add(++tot);
			p=tot;
		}
		for(int i=0;i<26;i++)
			if(trie[id][i])
				solve(trie[id][i],p);
	}
}trie;
char s[510005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		trie.insert(s);
	}
	trie.solve(trie.root,1);
	sorting(1);
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}
2022/4/23 17:27
加载中...