UVA644 Immediate Decodability
发布时间:2020-12-14 03:46:35 所属栏目:大数据 来源:网络整理
导读:UVA644 Immediate Decodability Trie Trie模板题 难度几乎相等的题 P2580 于是他错误的点名开始了 对于每组数据都清空树太浪费时间,所以我们只要在需要新点时 预先把新点原有的数据清空 即可。 剩下除了一些细节要注意,没啥要说的了 (luogu的标签系统有些
UVA644 Immediate Decodability Trie Trie模板题 难度几乎相等的题 P2580 于是他错误的点名开始了 对于每组数据都清空树太浪费时间,所以我们只要在需要新点时预先把新点原有的数据清空即可。 剩下除了一些细节要注意,没啥要说的了 (luogu的标签系统有些迷啊) #include<iostream> #include<cstdio> #include<cstring> using namespace std; struct data{ int nxt[2]; bool end; void clear() {nxt[0]=nxt[1]=0; end=0;} //清空原先的数据 }a[5000001]; //对于每个节点,存储它的下一个字母,以及是否是某个字母的结束符 char q[2000001]; int cnt; //节点编号 bool ok; inline void insert(){ int u=0,len=strlen(q); bool ins=0; //ins:是否插入新节点 for(int i=0;i<len;++i){ int p=q[i]-‘0‘; if(!a[u].nxt[p]){ //如果之前没有这个节点就插入 a[++cnt].clear(); a[u].nxt[p]=cnt; ins=1; } if(a[u].end) ok=1; //如果某个在它之前插入的单词是它的前缀 u=a[u].nxt[p]; //跳转到下一个 } if(!ins) ok=1; //如果它是某个在它之前插入的单词的前缀 a[u].end=1; } int main(){ int t=0; while(cin>>q){ if(q[0]==‘9‘) { //一组数据的结束 printf("Set %d is ",++t); if(ok) printf("not "); printf("immediately decodablen"); cnt=0; ok=0; a[0].clear(); //注意树根0也要清空 }else insert(); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |