题解：P13630 [NWRRC 2021] Clean Up!

海洋守卫者 · 2025-10-27 19:38:47 · 题解

P13630 Clean Up!

解题思路

观察到命令操作与前缀相关，因此可以想到用 Trie 树。于是删除单词次数问题转换为删除子树次数问题。关键如何在树上操作。

如果一个子树含有的文件树超过 k，则无法被删除。因此，每次应删除大小接近 k 却不大于 k 的子树。很显然每次操作应在接近叶子节点的子树上进行，使得其大小不超过 k，并与同父节点的子树比较，先删去较大的，并统计操作数，使用 dfs 可以轻松解决。至于同父节点子树的比较，可以选择优先队列或快排，取决于个人偏好，效果上相同。

实现细节

在 dfs 完成后，记得检查 Trie 树的根节点的剩余文件数是否为 0，如果否则答案应加上一。

完整代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<map>
using namespace std;
const int MAXN=3e5+7;
struct Trie{
    int cnt,fa,son[27],sz,sum;
}trie[MAXN];
int n,k,cnt;
char s[MAXN];
void insert()
{
    int p=0;
    for(int i=1;s[i];i++){
        if(!trie[p].son[s[i]-'a'])trie[p].son[s[i]-'a']=++cnt;
        p=trie[p].son[s[i]-'a'];
    }
    trie[p].cnt++;
}
void dfs(int x)
{
    priority_queue<int>que;
    trie[x].sz=trie[x].cnt;
    for(int i=0;i<26;i++){
        if(!trie[x].son[i])continue;
        int v=trie[x].son[i];
        dfs(v);
        trie[x].sz+=trie[v].sz;
        trie[x].sum+=trie[v].sum;
        que.push(trie[v].sz);
    }
    while(trie[x].sz>k)trie[x].sz-=que.top(),que.pop(),trie[x].sum++;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("\n%s",s+1);
        insert();
    }
    dfs(0);
    printf("%d",trie[0].sum+(trie[0].sz>0));
    return 0;

}