大致题意:
给出n个不同长度的数串,如果某个串是另一个串的前缀,输出“NO”,否则输出“YES”。
大致思路:
其实是一个很简单的tire判断,很快就写了出来,但是TLE了。手贱翻了一下discuss才知道,动态tire树每次都new一个对象太费时间,要改用静态数组。遂改之,AC~~
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int mMax=10005;
const int nMax=50;
class nodea{
public:
int id;
bool vis; //前缀记录标志
nodea *p[10];
// nodea(){
// vis=0;
// int i;
// id=-1;
// for(i=0;i<10;i++)p[i]=NULL;
// }
};
nodea num[500000];nodea *root;
int x;
nodea * newnodea(){
nodea * p = num + x++;
for(int i = 0; i < 10; i++){
p->p[i] = NULL;
}
p->id=-1;
p->vis=0;
return p;
}
int cnt;
bool flag;
int getnum(char *s){
int i;
nodea *r=root;
int l=strlen(s);
for(i=0;i<l;i++){
r->vis=1;
if(r->id!=-1)flag=0;
if(r->p[s[i]-'0']==NULL){
r->p[s[i]-'0']=newnodea();
}
r=r->p[s[i]-'0'];
}
if(r->id==-1){
r->id=cnt;
cnt++;
if(r->vis==1){
flag=0;
}
r->vis=1;
}
return r->id;
}
int main(){
int n,i,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
cnt=1;
x=0;
char str[nMax];
root=newnodea();
flag=1;
for(i=0;i<n;i++){
scanf("%s",str);
if(flag)getnum(str);
}
if(flag){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
分享到:
相关推荐
关于tire树一些简单的使用和应用
Tire 字典树 方面的论文
NULL 博文链接:https://ansjsun.iteye.com/blog/441658
(2) 树有s个外部结点 (3) 树的高度等于X中最长串的长度 (4) 树中的结点数为O(n) (1) 在root结点中查找第('b'-'a'=1)号孩子指针,
后缀tire树(tire图),用于多字符串匹配。
NULL 博文链接:https://tanghongjun1985.iteye.com/blog/548759
全面的轮胎模型。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:
paper about tire model construction
数据结构指的是“一组数据的存储...数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
gem 'tire-am_serializers' 用法 与相同: render json : User . search ( ... ) 只有一件事,Rails默认情况下会寻找TireUserSeralizer 。 如果类不存在,它将尝试找到UserSerailizer 。 如果此模型不存在...
Samsung Tire题目
MF_Tire_GUI 有助于可视化每个魔术公式参数对轮胎纵向力与滑移率曲线的重要性。 GUI 能够可视化以下版本的 Magic Formula 轮胎模型: * Pacejka 92 (MF 5.2) *佩斯卡1996 此外,MF_Tire_GUI 现在可用于拟合轮胎模型...
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 ...
DoubleArrayTrie 双端trie树的python实现 ...其与双数组Tire可以说在功能上互补; 在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树
设置 在python虚拟环境中,运行: pip install -r requirements.txt python manage.py migrate cars python manage.py createsuperuser (创建用于登录的用户) 运行应用程序 python manage.py runserver ...
Tire . suggest ( 'cars' , field : 'name.suggest' , term : 'au' ) . suggestions #=> ["audi", "audi 100", "audi 200", "audi 80", "audi 90", "audi a2", "audi a3", "audi a4", "audi a5", "audi a6"] 按多个...
胎压检测 Remote Sensing of Car Tire Pressure
3-tire sample code 3-tire sample code
魔术轮胎的simulink模型,可供车辆动力学轮胎力的分析