题解 - AKIOI OJ

0

XzyStudio (admin) LV 8 MOD RP++ tayz @ 6 个月前

~~（感觉这题比 B 可做）~~

先考虑第一，二档部分分，我们考虑求出所有本质不同的字符串之间的匹配度，那么我们可以贪心的去选，即先取匹配度大的，再取匹配度小的。时间复杂度 $O(n+k^3)$ ， $k$ 为本质不同字符串数量。期望得分 $40pts$ 。

再考虑回文串，对于两个回文串，最长公共前缀与最长公共后缀是等价的。所以我们只需要考虑前缀即可。那么我们可以把它插入到 Trie 树上，对于 Trie 树上任意一个前缀 $p$ 它能产生的贡献是 $|p|^2$ 再乘上它子树内字符串的数量除以二（下取整）。但是这样它会和它父亲的贡献重复计算，所以只加上 $|p|^2-|p-1|^2=2*|p|-1$ 即可。结合前面的 subtask 期望得分 $68pts$ 。

考虑怎么把后缀转化为前缀，那么我们扩充字符集，将字符集由 $a-z$ 扩充为 $(a,a)-(z,z)$ 的有序对，然后把串 $s$ 变为 $(s_1,s_n)(s_2,s_{n-1})...(s_n,s_1)$ 这样就把最长公共前缀和最长公共后缀的最小值转化为这个新串的最长公共子序列，然后应用回文串的做法即可，时间复杂度 $O(m|\sum|^2)$ 其中 $m$ 为总长度 $|\sum|$ 为原串的字符集大小，这里为 $26$ 。期望得分 $100pts$ 。

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define XY cerr<<"XY"<<endl
#define MKF cerr<<"MKF"<<endl
#define CONNECT_BASE(x,y) x##y
#define CONNECT(x,y) CONNECT_BASE(x,y)
#define DEBUG_BASE(x) cerr<<#x<<"="<<x<<' '
#define DEB_1(x) DEBUG_BASE(x)
#define DEB_2(x,y) DEB_1(x),DEB_1(y)
#define DEB_3(x,y,z) DEB_1(x),DEB_2(y,z)
#define DEB_4(a,b,c,d) DEB_1(a),DEB_3(b,c,d)
#define DEB_5(a,b,c,d,e) DEB_1(a),DEB_4(b,c,d,e)
#define DEB_6(a,b,c,d,e,f) DEB_1(a),DEB_5(b,c,d,e,f)
#define COUNT_BASE(_1,_2,_3,_4,_5,_6,x,...) x
#define COUNT(...) COUNT_BASE(__VA_ARGS__,6,5,4,3,2,1,0)
#define D(...) cerr<<"[In Line "<<__LINE__<<"]: ",CONNECT(DEB_,COUNT(__VA_ARGS__))(__VA_ARGS__),cerr<<endl
#define NAME(x) #x
#define INNAME(x) NAME(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define look_time cerr<<(double)clock()/CLOCKS_PER_SEC<<endl
#define look_memory cerr<<abs(&M1-&M2)/1024.0/1024.0<<endl
// #define int long long
#define F(i,a,b) for(int i=(a),i##end=(b);i<=(i##end);++i)
#define UF(i,a,b) for(int i=(a),i##end=(b);i>=(i##end);--i)
#define pb(x) push_back(x)
#define gc() getchar()
#define ret return
#define pc putchar
#define popcount(x) __builtin_popcount(x)
using ll=long long;
using lll=__int128;
using PII=pair<int,int>;
using uint=unsigned;
using db=double;
using DB=long double;
mt19937 rng(time(NULL));
inline void init();
inline void IO();

const int maxn=2e5+5;

ll ans=0;
int tr[maxn][700],sum[maxn];

bool M2;

void dfs(int u)
{
    F(i,0,26*26-1)
    {
        int v=tr[u][i];
        if(v) dfs(v),sum[u]+=sum[v];
    }
}

void dfs2(int u,int dep)
{
    ans+=1ll*(sum[u]/2)*(2*dep-1);
    F(i,0,26*26-1)
    {
        int v=tr[u][i];
        if(v) dfs2(v,dep+1);
    }
}

inline void mian()
{
    int n,cnt=1;
    cin>>n;
    F(i,1,n)
    {
        string s;
        cin>>s;
        int len=s.length();
        int p=1;
        F(j,0,len-1)
        {
            int x=(s[j]-'a')*26+(s[len-1-j]-'a');
            if(!tr[p][x]) tr[p][x]=++cnt;
            p=tr[p][x];
        }
        sum[p]++;
    }
    dfs(1);
    sum[1]=0;
    dfs2(1,0);
    cout<<ans<<endl;
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    int T=1;
     IO();
    // #define multitest 1
#ifdef multitest
    cin>>T;
#endif
    while(T--) init(),mian();
    look_time;
    look_memory;
    return 0;
}

inline void init()
{

}

#define FILEIO string
inline void IO()
{
#ifdef FILEIO
    freopen(INNAME(FILEIO)".in","r",stdin),freopen(INNAME(FILEIO)".out","w",stdout);
#endif
}

ID: 1092
难度: 9
分类: (无)
标签: (无)
递交数: 1
已通过: 1
通过率: 100%
上传者: XzyStudio (admin)