题解：P12124 [蓝桥杯 2024 省 B 第二场] 前缀总分

题意简述

给定

n

个字符串

s_{1 \sim n}

，修改某字符串的某个字符，使

\sum_{i<j} \operatorname{LCP}(s_i,s_j)

最大。

\operatorname{LCP}(p, q)

为字符串

p, q

的最长公共前缀长度。

思路

考虑 dp。定义

f_{i, j, k}

表示

s_i

和

s_j

从第

k

位开始到结尾的子串的最长公共前缀长度。

状态转移：

f_{i, j, k} = \begin{cases} 0, & s_{i, k} \neq s_{j, k}\\ f_{i, j, k+1} + 1, & s_{i, k} = s_{j, k} \end{cases}

统计答案时，我们枚举要修改的字符串编号

i

，修改字符的下标

k

和修改后的字符

c

。记这次修改可以使答案增加

d

。对于所有

j \neq i

，有以下两种情况使答案变动：

如果 $f_{i, j, 1} = k-1$ 且 $c = s_{j,k}$ ，这说明原本 $s_i$ 和 $s_j$ 相等的部分在第 $k$ 位这里断开了，修改之后可以给它接上。 $d \gets d + f_{i,j,k+1}+1$ 。
如果 $f_{i,j,1} \ge k$ 且 $c \neq s_{j,k}$ ，这说明原本 $s_i$ 和 $s_j$ 有一个较长的最长公共前缀，我们这次修改给它破坏了。 $d \gets d - (f_{i,j,1}-k+1)$ 。

记原本不加修改的答案为

ans

。则

ans + \max\{d\}

即为最终答案。时间复杂度

\mathcal O(n^2|s_i||\sum|)

，其中

|\sum| = 26

。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205;
string s[N];
int f[N][N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = min(s[i].size(), s[j].size())-1; k >= 1; k--)
                if (s[i][k] == s[j][k])
                    f[i][j][k] = f[i][j][k+1] + 1;
    int ans0 = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            ans0 += f[i][j][1];
    int ans = ans0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k < s[i].size(); k++) {
            for (char c = 'a'; c <= 'z'; c++) {
                int add = 0;
                for (int j = 1; j <= n; j++) {
                    if (j == i || k >= s[j].size()) continue;
                    if (f[i][j][1] == k-1 && c == s[j][k])
                        add += f[i][j][k+1]+1;
                    if (f[i][j][1] >= k && c != s[j][k])
                        add -= f[i][j][1]-k+1;
                }
                ans = max(ans, ans0+add);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

题解：P12124 [蓝桥杯 2024 省 B 第二场] 前缀总分

文章操作

题意简述

思路

代码

相关推荐

评论

题解：P12124 [蓝桥杯 2024 省 B 第二场] 前缀总分