「ABC353」Yet Another Sigma Problem

题目

字典树做法(用时187ms)

#include<cstdio>
#include<ctype.h>
const int N = 3e5 + 10;
int n;
long long ans;
int trans[N][26],cnt[N]; 
int tot;
char s[N];
template<class T>
void read(T &x){
	char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
}
void insert(){
	int now = 0;
	char c = getchar();
	while(!isalpha(c))c = getchar();
	while(isalpha(c)){
		if(!trans[now][c-'a'])trans[now][c-'a'] = ++tot;
		now = trans[now][c-'a'];
		ans += cnt[now];
		++cnt[now];
		c = getchar();
	}
}
signed main(){
	read(n);
	for(int i = 1;i<=n;++i)insert();
	short st[50],top = 0;
	do{
		st[++top] = ans%10,ans /= 10;
	}while(ans);
	while(top)putchar(48 | st[top--]);
	return 0;
}

搜索(用时262ms)

#include<iostream>
#include<algorithm>
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
const int N = 3e5 + 10;
int n;
long long ans;
string s[N];
void dfs(int l,int r,int d){
	if(l >= r)return ;
	if(d)ans += (r - l + 1) * (r - l) >> 1;
	int pre = l;
	for(int i = l;i<=r;++i){
		if(s[i].size() == d){ pre = i+1; continue; }
		if(s[i][d] != s[pre][d])dfs(pre,i-1,d+1),pre = i;
	}
	dfs(pre,r,d+1);
}
signed main(){
	cin >> n; for(int i = 1;i<=n;++i)cin >> s[i];
	sort(s+1,s+n+1);
	dfs(1,n,0);
	cout << ans;
	return 0;
}

分治(注意等于与否的判断)(用时263ms)

#include <iostream>
#include<cstdio>
#include<algorithm>
#define main Main(); signed main(){ return ios::sync_with_stdio(0), cin.tie(0), Main(); } signed Main
using namespace std;
string s[300010];
int n;
long long ans;
inline int lcp(const string &a,const string &b){
	int now = min(a.size(),b.size());
	for(int i = 0;i<now;++i)if(a[i] != b[i])return i;
	return now;
}
int h[300010];

void solve(int l,int r){
	if(l == r)return ;
	int mid = (l + r)>>1;
	solve(l,mid),solve(mid+1,r);
	int i = mid, j = mid+1, mi = min(h[i],h[j]);
	while(i > l && h[i-1] >= mi)--i;
	while(j < r && h[j+1] >= mi)++j;
	ans += 1ll * (mid - i + 1) * (j - mid) * mi;
	while(i > l || j < r){
		if(j == r || (i > l && h[i-1] >= h[j+1])){
			int t = i;
			mi = h[--i];
			while(i > l && h[i-1] >= mi)--i;
			while(j < r && h[j+1] > mi)++j;
			ans += 1ll * (t-i) * (j - mid) * mi;
		}else{
			int t = j;
			mi = h[++j];
			while(i > l && h[i-1] > mi)--i;
			while(j < r && h[j+1] >= mi)++j;
			ans += 1ll * (mid - i + 1) * (j-t) * mi;
		}
	}
}
signed main(){
	cin >> n;
	for(int i = 1;i<=n;++i)cin >> s[i];
	sort(s+1,s+n+1);
	for(int i = 1;i<n;++i)h[i] = lcp(s[i],s[i+1]),ans += h[i];
	solve(1,n-1);
	cout << ans << endl;
	return 0;
}