[HackerCup Round1 2] Autocomplete (Trie)

题目链接:https://www.facebook.com/hackercup/problems.php?pid=313229895540583&round=344496159068801

题目大意:自己看去(其实我也说不清)

裸的Trie树,直接看是否存在必须插入的节点。

代码写的太挫了。。将就着看吧。。

 #include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdlib>
using namespace std;
#define CHARSET 26 const int MAX_NODE = ; struct trieNode{
int ch[CHARSET];
};
trieNode trie[MAX_NODE];
int ptr;
int ans; int T,N;
char str[MAX_NODE]; void init(){
ptr = ans = ;
for(int i=;i<CHARSET;i++){
trie[].ch[i] = -;
}
} int newNode(){
ptr++;
for(int i=;i<CHARSET;i++){
trie[ptr].ch[i] = -;
}
return ptr;
} void insert(const char* str){
bool hasAdded = false;
int len = strlen(str);
int rt = ;
for(int i=;i<len;i++){
int id = str[i] - 'a';
if( trie[rt].ch[id]==- ){
trie[rt].ch[id] = newNode();
if( !hasAdded ){
ans = ans + i + ;
hasAdded = true;
// printf("+%d\n",i+1);
}
}
rt = trie[rt].ch[id];
}
if(!hasAdded){
ans = ans + len;
// printf("+%d\n",len);
}
} int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
scanf("%d",&T);
for(int cases = ;cases <= T ; cases++){
scanf("%d",&N);
init();
for(int i=;i<N;i++){
scanf("%s",str);
insert(str);
}
printf("Case #%d: %d\n",cases,ans);
}
return ;
}
上一篇:css初始化样式代码


下一篇: