2025牛客寒假算法基础集训营3

2025牛客寒假算法基础集训营3

C

让最长的字符串最后出现，不需要在回退了。

字典序排序后，前缀相同的会在相邻，公共部分变得更多。

所以答案=(全部字符串的长度和-排序后相邻字符串的lcp)*2-最长字符串长度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
const ll N=2e5+5;
const ll mod=1e9+7;
string a[N];
ll lcp(string a,string b)
{ll i=0;while(i<a.size()&&i<b.size()&&a[i]==b[i]){i++;}return i;
}
void solve()
{ll n,m;cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);ll mx=0,sum=0;for(int i=0;i<n;i++){sum+=a[i].size()*2;if(i>0){sum-=lcp(a[i],a[i-1])*2;}ll siz=a[i].size();mx=max(mx,siz);}cout<<sum-mx<<'\n';
​
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--){solve();}
}