题解：P13108 [GCJ 2019 #1A] Alien Rhyme

居然还没有题解，赶紧来一发。
其实和正常字典树没什么区别，只是这里要求后缀，所以我们把字符串倒过来加入字典树。
如何得出答案？
其实也不难。后续遍历整棵字典树，如果能匹配就答案

+2

，然后这个节点的父节点的计数数组要全部

-2

，也就是减去以这个节点为根节点的子树的答案。
至于为什么要后续遍历，样例的第

3

个小数据就给出答案了。
因为每个重音后缀只能匹配两个字符，而先序遍历可能会找到多个有相同的重音后缀的字符。虽然稍微处理一下也可以过，但是后序遍历更简单。

code

CPP

#include<iostream>
using namespace std;
int trie[5005][60] , len , cnt[5005] , n;
void insert(string s){
	int p = 0;
	for(int i=s.size()-1;i>=0;i--){
		int x = s[i] - 'A';
		if(trie[p][x]==0)trie[p][x] = ++len;
		p = trie[p][x] , cnt[p]++;
	}
}
int solve(int i){
    int res = 0;
    int tmp = 0;
    for(int c=0;c<26;c++){
        if(trie[i][c]){
            res += solve(trie[i][c]);
            tmp += cnt[trie[i][c]] - res;
        }
    }
    if(i!=0&&cnt[i]-res>=2)res += 2;
    return res;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T;cin >> T;
	for(int x=1;x<=T;x++){
		for(int i=0;i<=len;i++)for(int j=0;j<26;j++)trie[i][j] = 0 , cnt[i] = 0;
		len = 0;
		cin >> n;
		for(int i=1;i<=n;i++){
			string s;cin >> s;
			insert(s);
		}
		cout << "Case #" << x << ": " << solve(0) << "\n";
	}
	return 0;
}

~~话说为什么时限20s~~

题解：P13108 [GCJ 2019 #1A] Alien Rhyme

文章操作

code

相关推荐

评论

题解：P13108 [GCJ 2019 #1A] Alien Rhyme