一个字典树的题。如果一个节点是Ending而他还有子节点的话那就NO掉,否则就YES。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <memory.h>
using namespace std;
#define NR_CHILDS 10
#define NR_NODES 100000
struct trie_node_t {
trie_node_t * childs[10];
bool is_ending;
};
trie_node_t nodes[NR_NODES];
trie_node_t *trie_root, *node_ending;
void
init_trie(void)
{
memset(nodes, 0, sizeof(nodes));
trie_root = nodes;
node_ending = trie_root + 1;
return;
}
bool
confict_exists(trie_node_t *root_node)
{
bool parent_ending(root_node->is_ending);
for (trie_node_t **iter = root_node->childs, **iter_end = root_node->childs + NR_CHILDS; iter != iter_end; ++iter) {
if (*iter) {
if (parent_ending) {
return true;
}
if (confict_exists(*iter)) {
return true;
}
}
}
return false;
}
void
add_string(char* str)
{
trie_node_t *cur(trie_root);
int c;
--str;
while (*++str) {
if (!cur->childs[c = *str - '0']) {
cur->childs[c] = node_ending++;
}
cur = cur->childs[c];
}
cur->is_ending = true;
return;
}
void
solve_prob(void)
{
int nr_number;
char number[11];
init_trie();
cin >> nr_number;
while (nr_number--) {
cin >> number;
add_string(number);
}
cout << (confict_exists(trie_root) ? "NO" : "YES") << endl;
return;
}
int
main(void)
{
int nr_cases;
ios::sync_with_stdio(false);
//freopen("test.txt", "r", stdin);
cin >> nr_cases;
while (nr_cases--) {
solve_prob();
}
return 0;
}