P7758 [COCI2012-2013#3] HERKABE题解

· · 题解

题目链接

题目大意，给定一系列字符串，求使对于每两个有相同前缀的字符串，在它们之间的所有字符串也应当有这一个前缀满足的所有方案数。

依题意，前缀相同的一系列字符串必须要排到一起，我就直接 sort 先排序，再进行操作。

观察样例： 样例 1 中可分为。

[IVO ,[JASNA,JOSIPA]]

我们可以分别计算方案：第一组只有一个贡献为 1， 第二组有两个，排列方式有两个，贡献为 2；两组合一起排列方式有 2 个 根据乘法原理，方案数为 1 * 2 * 2 = 4。

样例 2 中分为：

[[MARA,MARICA , [MARTA,MARTINA] ],MATO]
这样我们从内向外分析，最内部有两个，贡献为 2，然后把这两个看为一组变为
[[MARA,MARICA,MAR..],MATO]
让后最内部有三个，贡献为 6 (此时我们可以发现n个前缀相同的字符排列方式就为n!)。
变为[MA..,MATO]最后只有 2 个贡献为2。
答案为 2 * 6 * 2 = 24

根据样例我们可以想到一个方法，首先暴力找出第 i 个字符串与第 i-1 个字符串的公共前缀的长度，只要 x 个字符串连续的公共前缀长度是一样的，我们就可以把 x! 算到答案里，我们设 s[i] 为第 i 个字符串与第 i-1 个字符串的公共前缀长度。

现在的问题就为如何求公共前缀长度 s[i] 一样的字符串，首先有个条件是字符串需是连续的，所以我们可以想到一些线性结构来求解。

我们继续观察可以发现当s[i] 递增时不会有贡献，只有当 s[i] 降的时候才有贡献，这时我们需要将前面大于 s[i] 的全部字符串分为相同的几组(即样例2中由内向外)对答案累计贡献。

所以我们就可以用单调栈(不会自学)来维护这个由内向外的过程，具体来说就是建立一个 pair 二元组(懒得写结构体)，第一个元素存前缀长度 x，第二个元素存连续前缀长度为 x 的字符串个数(即需要累计贡献的)，在每次入栈之前都把大于当前前缀长度的栈顶 pop 并累计贡献，扫一遍就可以了。

时间复杂度:预处理为 O(n^2),所以大概为 O(n^2)。

具体细节看代码吧(第一次写题解，有错见谅qwq)。

#include <bits/stdc++.h> 
using namespace std;
const int N = 3e3+10,mod = 1e9+7;
#define ll long long
#define P pair<int,int>
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
ll n,ans = 1,sum;
ll s[N],fac[N] = {1,1};
string a[N];
stack<P>st;
int find(string x,string y){
    int ans = 0;
    for(int i = 0;i < min(x.length(),y.length());i++){
        if(x[i] == y[i])ans++;
        else break;
    }
    return ans;
}//暴力枚举
int main(){
    scanf("%lld",&n);
    for(int i = 2;i <= n;i++)fac[i] = fac[i-1] * i % mod;//预处理阶乘
    for(int i = 1;i <= n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i = 2;i <= n;i++)s[i] = find(a[i-1],a[i]);//暴力预处理相同前缀长度
    for(int i = 2;i <= n;i++){
        while(!st.empty() && st.top().fi > s[i])ans = (ans * fac[st.top().se+1]) % mod,st.pop();
        //比当前前缀长度大的都要出栈累计贡献
        if(!st.empty() && st.top().fi == s[i]){
            int x = st.top().se;st.pop();
            st.push(mp(s[i],x+1));//前缀长度相等累加
        }
        else st.push(mp(s[i],1));//
    }
    while(!st.empty())ans = (ans * fac[st.top().se+1]) % mod,st.pop();
    //最后需要全部出栈累计贡献
    printf("%d\n",ans);

    return 0;

}

┭┮﹏┭┮