30pts求调
查看原帖
30pts求调
562569
kingho11楼主2024/12/28 20:17

rt,对了#3,#4,#7三个点,代码如下:

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5,TR=510005;
int n,ans,tr[TR][26],tot,siz[TR],dfn[N],t;
vector <int> v[TR];
bool flag[TR];
string s[N];
void insert(string a)
{
	int u=0;
	for(int i=0;i<a.length();i++)
	{
		if(!tr[u][a[i]-'a'])
		{
			tr[u][a[i]-'a']=++tot;
			v[u].push_back(tot);
		}
		u=tr[u][a[i]-'a'];
	}
	flag[u]=1;
}
bool cmp(int x,int y)
{
	return siz[x]<siz[y];
}
void dfs_(int u)
{
	siz[u]=1;
	for(int i=0;i<v[u].size();i++)
	{
		int v2=v[u][i];
		dfs_(v2);
		siz[u]+=siz[v2];
	}
}
void dfs(int u,int fa)
{
	if(!flag[u])
	{
		for(int i=0;i<v[u].size();i++)
		{
			int v2=v[u][i];
			dfs(v2,fa);
		}
		return ;
	}
//	cout<<u<<" "<<fa<<"\n";
	dfn[u]=++t;
	ans+=dfn[u]-dfn[fa];
	for(int i=0;i<v[u].size();i++)
	{
		int v2=v[u][i];
		dfs(v2,u);
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		reverse(s[i].begin(),s[i].end());
		insert(s[i]);
	}
	dfs_(0);
	for(int i=1;i<=tot;i++)
	{
		sort(v[i].begin(),v[i].end(),cmp);
	}
//	for(int i=1;i<=tot;i++) cout<<siz[i]<<" ";
	dfs(0,0);
	cout<<ans;
}
2024/12/28 20:17
加载中...