P13630 Clean Up!

解题思路

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

如果一个子树含有的文件树超过

k

，则无法被删除。因此，每次应删除大小接近

k

却不大于

k

的子树。很显然每次操作应在接近叶子节点的子树上进行，使得其大小不超过

k

，并与同父节点的子树比较，先删去较大的，并统计操作数，使用 dfs 可以轻松解决。至于同父节点子树的比较，可以选择优先队列或快排，取决于个人偏好，效果上相同。

实现细节

在 dfs 完成后，记得检查 Trie 树的根节点的剩余文件数是否为

0

，如果否则答案应加上一。

完整代码

CPP

#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;
	
}

题解：P13630 [NWRRC 2021] Clean Up!

文章操作