DDOSvoid's Blog

“菜鸟杯”华中师范大学程序设计新生赛（同步赛） A 小哈的魔法咒语

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/26134/A

简要题意：现在有一个长度为 $n$ 的字符串，我们现在要将它的所有前缀按照某种顺序排成一排，如果前缀 $i$ 排在第 $j$ 个位置，那么它的代价为 $j\times a_i$，求最小贡献和，如果 前缀 $i$ 是前缀 $j$ 的 $border$，那么前缀 $i$ 一定要排在前缀 $j$ 的前面

$n\le 10^5$

Solution

我们考虑 $kmp$，建出 $fail$ 树，那么如果想要排点 $u$，则必须先排它的所有父亲

我们考虑对于两个不相交的集合 $S,T$，不妨令 $S$ 的大小为 $sz_S$，$S$ 的 $a$ 之和为 $sum_S$，那么我们将 $S$ 排在 $T$ 之前的条件是 $sz_S\times sum_T<sz_T\times sum_S$，等价于 $\frac{sz_S}{sum_S}< \frac{sz_T}{sum_T}$

然后我们考虑，我们在排序过程中的集合会是什么样的，注意到显然是一棵树，那么做法就呼之欲出了，我们用小根堆维护现在的所有的集合，小根堆的权重就是 $\frac{sz}{sum}$，每次取出最小的集合，将其向上合并一次，每个集合的维护我们可以使用并查集，时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#define maxn 100010
#define ll long long
using namespace std;

int n, a[maxn];
char s[maxn];

int nxt[maxn]; 
void init_nxt(char *s) {
    int k = 0, l = strlen(s + 1); nxt[1] = 0;
    for (int i = 2; i <= l; ++i) {
        while (k && s[k + 1] != s[i]) k = nxt[k];
        if (s[k + 1] == s[i]) ++k;
        nxt[i] = k; 
    }
}

struct node {
    int k, sz; ll v;

    friend bool operator < (const node &u, const node &v) {
        return u.sz * v.v > v.sz * u.v;
    }
};

int fa[maxn], sz[maxn]; ll sum[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, sum[i] = a[i], sz[i] = 1; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 

ll ans; 
inline void merge(int x, int y) {
    ans += sum[x] * sz[y];
    sz[y] += sz[x]; sum[y] += sum[x];
    fa[x] = y; 
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> s + 1; init_nxt(s); priority_queue<node> Q; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; init_fa(n);
    for (int i = 1; i <= n; ++i) ans += a[i], Q.push({ i, 1, a[i] });
    while (!Q.empty()) {
        int x = Q.top().k; Q.pop(); if (x != find(x)) continue;
        int u = find(x), v = find(nxt[u]); 
        if (v != u) merge(u, v), Q.push({ v, sz[v], sum[v] });
    } cout << ans << "\n";
    return 0;
}