[TIOJ] 1446. H遊戲密笈

題目連結:http://tioj.infor.org/problems/1446
稍微想一下就會發現這題就等價於塞到trie後的DFS的順序,但是因為建棵trie有點麻煩,所以在想個兩下就會發現建棵trie再DFS其實跟你直接排序再扣掉相鄰的人的LCP等價,所以就這樣做吧XD
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

string ss[N];

int main(){
	int n, ans=0; cin>>n;
	for(int i=0;i<n;i++){
		cin>>ss[i];
		ans+=ss[i].size();
	}
	sort(ss, ss+n);
	for(int i=1;i<n;i++){
		int sz = min(ss[i].size(), ss[i-1].size());
		int lcp;
		for(lcp=0;lcp<sz and ss[i][lcp]==ss[i-1][lcp];lcp++);
		ans-=lcp;
	}
	cout<<ans*2+n<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology