本文主要是介绍统计难题 HDU - 1251 + Phone List HDU - 1671，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
两道字典树模板 没啥说的 借鉴博客点击打开链接
1251可能是哪里有bug hdu上用G++提交就会MLE 只能过C++ 待解。。
但用同样方法写1671就没问题 难道是数据水
hdu1251
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;struct node
{node *next[26];int cnt;
};node *root;void getnode(node *& ptr)
{int i;ptr=new node;for(i=0;i<26;i++) ptr->next[i]=NULL;ptr->cnt=0;
}void update(node *ptr,char *ch,int cur,int len)
{if(cur==len) return;if(ptr->next[ch[cur]-'a']==NULL) getnode(ptr->next[ch[cur]-'a']);ptr->next[ch[cur]-'a']->cnt++;update(ptr->next[ch[cur]-'a'],ch,cur+1,len);
}int query(node* ptr,char *ch,int cur,int len)
{if(ptr->next[ch[cur]-'a']==NULL) return 0;if(cur==len-1) return ptr->next[ch[cur]-'a']->cnt;return query(ptr->next[ch[cur]-'a'],ch,cur+1,len);
}void destruct(node *ptr)
{int i;for(i=0;i<26;i++){if(ptr->next[i]!=NULL) destruct(ptr->next[i]);}delete ptr;
}int main()
{int len;char ch[20];getnode(root);while(gets(ch)&&ch[0]!=0){len=strlen(ch);update(root,ch,0,len);}while(gets(ch)&&ch[0]!=0){len=strlen(ch);printf("%d\n",query(root,ch,0,len));}destruct(root);return 0;
}
hdu1671
指针版
#include <bits/stdc++.h>
using namespace std;struct node
{node *next[10];int cnt;
};node *root;
int n;void getnode(node *& ptr)
{int i;ptr=new node;for(i=0;i<10;i++) ptr->next[i]=NULL;ptr->cnt=0;
}void destruct(node *ptr)
{int i;for(i=0;i<10;i++){if(ptr->next[i]!=NULL){destruct(ptr->next[i]);}}delete ptr;
}int update(node *ptr,char *ch,int flag1,int flag2,int cur,int len)
{if(ptr->next[ch[cur]-'0']==NULL){flag1=1;getnode(ptr->next[ch[cur]-'0']);}if(ptr->next[ch[cur]-'0']->cnt!=0) flag2=0;if(cur==len-1){ptr->next[ch[cur]-'0']->cnt=1;return flag1&flag2;//flag1判断当前串是不是之前某个串的前缀 flag2判断当前串是否已经出现子串}return update(ptr->next[ch[cur]-'0'],ch,flag1,flag2,cur+1,len);
}int main()
{int t,res;char ch[20];scanf("%d",&t);while(t--){getnode(root);scanf("%d",&n);res=1;while(n--){scanf("%s",ch);if(res) res=update(root,ch,0,1,0,strlen(ch));}if(res) printf("YES\n");else printf("NO\n");destruct(root);}return 0;
}
数组版
#include <bits/stdc++.h>
using namespace std;struct node
{int next[10];int cnt;
};node tree[100010];
int num;void init()
{memset(tree,0,sizeof(tree));num=1;
}int update(char *ch,int f1,int f2)
{int len,cur,i,id;len=strlen(ch),cur=0;for(i=0;i<len;i++){id=ch[i]-'0';if(tree[cur].next[id]==0){tree[cur].next[id]=num++;f1=1;}if(tree[tree[cur].next[id]].cnt) f2=0;if(i==len-1) tree[tree[cur].next[id]].cnt=1;cur=tree[cur].next[id];}return f1&f2;
}int main()
{int t,n,res;char ch[20];scanf("%d",&t);while(t--){init();scanf("%d",&n);res=1;while(n--){scanf("%s",ch);if(res) res=update(ch,0,1);}if(res) printf("YES\n");else printf("NO\n");}return 0;
}
这篇关于统计难题 HDU - 1251 + Phone List HDU - 1671的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
