今天碰到了一个水题不水。题目链接如下:http://acm.nyist.net/JudgeOnline/problem.php?pid=163
第一感觉就是用字符串存储,然后一个一个地比较,然后,结果你们懂的,显然是TLE(超时),直接给我一个TLE错误,我了个去,然后 没办法才用的字典树。
又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
提交的最后AC代码如下所示:
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct TireTree{
TireTree* child[10];
int number;
};
void DestroyTireTree(TireTree* root){//destroy a tire tree
if(!root)//root is null
return;
for(int i= 0; i< 10; ++i){//destroy child
DestroyTireTree(root->child[i]);
}
delete root;//destroy root
}
TireTree* CreateNode(int inode){
TireTree* node = new TireTree;
node->number = inode;
memset(node->child, 0, sizeof(TireTree*)*10);//child is null
return node;
}
bool InsertToTireTree(TireTree* root, int iNode, int* bit, int ilen, int iStep){
if(root->number){
return false;
}
if(iStep == ilen-1){//the last bit
if(root->child[bit[iStep]]){//has a prefix
return false;
}else{
root->child[bit[iStep]] = CreateNode(iNode);
return true;
}
}else{
if(!root->child[bit[iStep]]){//child is null
root->child[bit[iStep]] = CreateNode(0);
}
return InsertToTireTree(root->child[bit[iStep]], iNode, bit, ilen, iStep+1);
}
}
void HandleEachCase();
int main(){
int iCaseCount;
cin>>iCaseCount;
while(iCaseCount--){
HandleEachCase();
}
}
void HandleEachCase(){
int n;
int number[100000];
scanf("%d", &n);
for(int i= 0; i< n; ++i){
scanf("%d", number+i);
}
int bit[10];
int ilen;
TireTree* root = CreateNode(0);
int tmp;
bool ok= true;
for(int i= 0; i< n; ++i){
tmp = number[i];
ilen = 0;
while(tmp){
bit[ilen++]= tmp%10;
tmp/= 10;
}
reverse(bit, bit+ ilen);
if(!InsertToTireTree(root, number[i], bit, ilen, 0)){
ok = false;
break;
}
}
if(ok){
cout<<"YES\n"<<endl;
}else{
cout<<"NO\n";
}
DestroyTireTree(root);
}
分享到:
相关推荐
Tire 字典树 方面的论文
脏字屏蔽 中文 Tire Tree c++实现 可以检测是否有脏字 并且把脏字屏蔽成**
关于tire树一些简单的使用和应用
Samsung Tire题目
后缀tire树(tire图),用于多字符串匹配。
paper about tire model construction
全面的轮胎模型。Using the Fiala Handling Force ...The Fiala tire model is the standard tire model that comes with all Adams/Tire modules. This chapter contains information for using the Fiala tire model:
NULL 博文链接:https://tanghongjun1985.iteye.com/blog/548759
tire forces, obtained from a multi-sensing hub (MSHub) unit, are used to estimate lateral vehicle velocity and a roll angle. In order to estimate lateral vehicle velocity, the recursive least square ...
NULL 博文链接:https://ansjsun.iteye.com/blog/441658
另外,有实现了字典Trie树,字典Trie树构建简单、模糊查找功能实现容易,无需状态记录;其与双数组Tire可以说在功能上互补; 在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘...
(2) 树有s个外部结点 (3) 树的高度等于X中最长串的长度 (4) 树中的结点数为O(n) (1) 在root结点中查找第('b'-'a'=1)号孩子指针,
嵌入式系统中基于trie树的拼音输入法的实现,李巧红,,介绍一种中文拼音输入法的实现方式,着重讨论了字库的设计及基于Trie树检索方法的实现。Trie树是基于关键码空间分解的树结构,其内�
胎压检测 Remote Sensing of Car Tire Pressure
魔术轮胎的simulink模型,可供车辆动力学轮胎力的分析
3-tire sample code 3-tire sample code
魔术公式拟合,轮胎数据处理。采用最简单的枚举法。
魔术公司轮胎参数解析,用于查看轮胎在各工况下测试曲线。
利用Tire树实现一个音域单词辅助记忆系统,完成相应的建表和查表程序。 程序主要实现对单词的插入、删除和查找。其中查找部分又分精确查找和模糊查找。 利用文件对单词进行保存和读取操作以增强程序的可用行性。
Samsung Tire 源码