题目http://acm.hdu.edu.cn/showproblem.php?pid=1671
题目本身不难，一棵前缀树OK，但是前两次提交都没有成功。
第一次Memory Limit Exceeded：
前缀树是很费空间的数据结构，每个节点存放了字母（数字）个数个指针，正所谓用空间来换取时间。
我发现我忘记写析构函数了，所以测例多起来还不释放很容易超空间。
树形结构的析构也很有趣：
~Node()
{
for (int i = ; i < ; ++i)
{
if (children[i])
{
delete children[i];
children[i] = nullptr;
}
}
}
好了，第二次没成功，Time Limit Exceeded：
看起来这是一棵规规矩矩的前缀树，仔细找可以优化的地方，试探性地把
vector<Node *> children;
Node()
{
for (int i = ; i < ; ++i) children.push_back(nullptr);
}
改成了
vector<Node *> children = vector<Node *>(, nullptr);
Node()
{
//for (int i = 0; i < 10; ++i) children.push_back(nullptr);
}
Accepted！显然构造的时候赋值比构造之后再赋值要快。。果然还是要尽可能的优化啊！
附代码：
#include <string>
#include <vector>
#include <iostream> using namespace std; class Node
{
public:
bool is_phone = false;
vector<Node *> children = vector<Node *>(, nullptr);
Node()
{}
~Node()
{
for (int i = ; i < ; ++i)
{
if (children[i])
{
delete children[i];
children[i] = nullptr;
}
}
}
void insert(const string &_Phone)
{
Node *p = this;
for (int i = ; i < _Phone.size(); ++i)
{
int curr = _Phone[i] - '';
if (p->children[curr] == nullptr)
{
p->children[curr] = new Node();
}
p = p->children[curr];
}
p->is_phone = true;
}
bool has_phone(const string &_Phone)
{
Node *p = this;
for (int i = ; i < _Phone.size(); ++i)
{
int curr = _Phone[i] - '';
if (!p->children[curr]) return false;
if (p->children[curr]->is_phone) return true;
p = p->children[curr];
}
return true;
}
}; typedef Node *Trie; int main()
{
int t;
cin >> t;
while (t--)
{
Trie trie = new Node();
int n;
cin >> n;
string phone;
bool flag = true;
while (n--)
{
cin >> phone;
if (trie->has_phone(phone)) { flag = false; }
trie->insert(phone);
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
delete trie;
}
//system("pause");
return ;
}