题解：P13630 [NWRRC 2021] Clean Up!

· · 题解

P13630 [NWRRC 2021] Clean Up! 题解

题意简化

给定 n 个字符串，每次可以选一个公共前缀，把所有包含该前缀的字符串删除，直到不超过 k 个为止，问最少操作几次才能满足条件。

思路

首先，看到公共前缀，就会想到用字典树做。如果你不会字典树，请出门左转。

注意到，选择一个点代表的前缀删除，就相当于删除了它的子树。

我们递归访问字典树，同时就可以记录当前前缀作为多少字符串的前缀，为方便描述，称为该子树的贡献。将这些数加起来就是选择这个前缀需要删的字符串数量了。

如果这个数大于 k，我们贪心地每次删掉当前点贡献最大的子树，直到小于 k。

那这个贪心策略为什么是对的呢？或者说我们要怎么证明这个贪心策略。

其实很显然，因为各子树已经处理好了，在需要减少的数量固定时，删除更大的数能使删除次数最小。那这个部分用优先队列维护就行。

注意最后剩下的小于 k 的那部分贡献也需要花一次操作。

这样，这一题就做完了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 5;
ll t[N][50], cnt[N], siz[N];
ll tt = 0, ans = 0;
ll n, m;
void insert(string s) {
    ll tmp = 0;
    for(ll i = 0; i < s.size(); i++) {
        ll temp = s[i] - 'a';
        if(!t[tmp][temp]) t[tmp][temp] = ++tt;
        tmp = t[tmp][temp];
    }
    cnt[tmp]++;
}
ll find(ll x) {
    siz[x] = cnt[x];
    priority_queue <ll> pq;
    for(ll i = 0; i < 26; i++) {
        ll y = t[x][i];
        if(!y) continue;
        find(y);
        siz[x] += siz[y];
        pq.push(siz[y]);
    }
    while(siz[x] > m) {
        siz[x] -= pq.top();
        pq.pop();
        ans++;
    }
    return siz[x];
}
int main() {
    cin >> n >> m;
    for(ll i = 1; i <= n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    find(0);
    if(siz[0] > 0) cout << ans + 1 << endl;
    else cout << ans << endl; 
    return 0;
}

后记

求管理员通过，管理员辛苦了。

如果这篇题解对你有帮助，不妨点个赞再走吧。