题解：AT_abc353_e [ABC353E] Yet Another Sigma Problem

YFF1 · 2024-05-19 18:31:58 · 题解

前言：

本代码不使用任何哈希表或字典树，可供刚学习字符串的萌新使用。

思路（极为奇葩）：

注意到，将字符串排序后，每个字符串对答案的贡献就是它与上一个字符串最长连续前缀的长度，因此可以将每个字符串的最长公共连续前缀拆分成一个个字符，然后统计并累加。

代码：

#include<bits/stdc++.h>
using namespace std;
string s[300005];
char c[300005];
long long n,mp[300005][30],sum,ans;
int main () {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+1+n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<s[i].size();j++){
            int pos=int(s[i][j]-96);
            if((i==1||j+1<=s[i-1].size())&&s[i-1][j]==s[i][j])mp[j][pos]++;//用于判断该字符与上一个字符串上该位置的字符是否相同 
            else{ //若有不同，说明这个字符串与上一个字符串的最大公共前缀到此为止了 
                for(int k=j;k<s[i].size();k++){
                    if(c[k]>='a'&&c[k]<='z'){
                        int pos2=int(c[k])-96;
                        ans+=mp[k][pos2]*(mp[k][pos2]-1)/2;
                        mp[k][pos2]=0;//将这之后所有的累计数组归零，因为要求的是前缀连续相同的长度
                    }
                    c[k]=s[i][k];
                    mp[k][int(s[i][k])-96]=1;
                }
                break;
            }
        }
    }
    for(int i=0;i<=300000;i++){
        if(c[i]>='a'&&c[i]<='z'){
            int pos3=int(c[i])-96;
            ans+=mp[i][pos3]*(mp[i][pos3]-1)/2;//最后还要再补一次计算 
        }
    }
    cout<<ans;
    return 0;
}