这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1671
这题比 HDOJ 1251 变通了一下。题目没有单纯的考虑计算前缀数,而是考虑是否有前缀,谁是谁的前缀,在这里输入一条语句时,可能前面的语句是这条的前缀,也可能这条是前面某条语句的前缀,所以要分别考虑,这就是在createTrie时注意return标志和findTrie时注意判断标志了。
字典树资料: http://www.wutianqi.com/?p=1359 |
另外,这题如果对字典树进行动态开辟空间时,最后要释放,否则会MLE而导致悲剧的。 当然,有牛人用静态的也OK了!Orz。
// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1671
// Trie
// 动态超内存了
#include
using namespace std;
typedef struct Trie{
int v;
Trie *next[10];
}Trie;
Trie *root;
void createTrie(char *str)
{
int len = strlen(str);
Trie *p = root, *q;
for(int i=0; inext[id] == NULL)
{
q = (Trie *)malloc(sizeof(Trie));
q->v = 1;
for(int j=0; j<10; ++j)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else
{
p->next[id]->v++;
p = p->next[id];
}
}
p->v = -1;
}
int findTrie(char *str)
{
int len = strlen(str);
Trie *p = root;
for(int i=0; inext[id];
if(p == NULL)
return 0;
if(p->v == -1)
return -1;
}
return -1;
}
int deal(Trie* T)
{//这是把T清空,一开始没加这个,结果MLE.
int i;
if(T==NULL)
return 0;
for(i=0;i<10;i++)
{
if(T->next[i]!=NULL)
deal(T->next[i]);
}
free(T);
return 0;
}
int main()
{
//freopen("input.txt", "r", stdin);
char str[15];
int nCases, nNum;
bool flag;
scanf("%d", &nCases;);
while(nCases--)
{
flag = 0;
root = (Trie *) malloc (sizeof(Trie));
for(int i=0; i<10; ++i)
root->next[i] = NULL;
scanf("%d", &nNum;);
for(int i=0; i<nNum; ++i)
{
scanf("%s", str);
if(findTrie(str) == -1)
flag = 1;
if(flag) //youhua
continue;
createTrie(str);
}
if(flag)
printf("NO\n");
else
printf("YES\n");
deal(root);
}
return 0;
}