首页 > 代码库 > hdu4886 TIANKENG’s restaurant(Ⅱ) （trie树或者模拟进制）
hdu4886 TIANKENG’s restaurant(Ⅱ) （trie树或者模拟进制）
TIANKENG’s restaurant(Ⅱ)
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 130107/65536 K (Java/Others)
Total Submission(s): 456 Accepted Submission(s): 149
Problem Description
After improving the marketing strategy, TIANKENG has made a fortune and he is going to step into the status of TuHao. Nevertheless, TIANKENG wants his restaurant to go international, so he decides to name his restaurant in English. For the lack of English skills, TIANKENG turns to CC, an English expert, to help him think of a property name. CC is a algorithm lover other than English, so he gives a long string S to TIANKENG. The string S only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’. TIANKENG wants his restaurant’s name to be out of ordinary, so the restaurant’s name is a string T which should satisfy the following conditions: The string T should be as short as possible, if there are more than one strings which have the same shortest length, you should choose the string which has the minimum lexicographic order. Could you help TIANKENG get the name as soon as possible?
Meanwhile, T is different from all the substrings of S. Could you help TIANKENG get the name as soon as possible?
Meanwhile, T is different from all the substrings of S. Could you help TIANKENG get the name as soon as possible?
Input
The first line input file contains an integer T(T<=50) indicating the number of case.
In each test case:
Input a string S. the length of S is not large than 1000000.
In each test case:
Input a string S. the length of S is not large than 1000000.
Output
For each test case:
Output the string t satisfying the condition.(T also only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’.)
Output the string t satisfying the condition.(T also only contains eight kinds of letters-------‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’.)
Sample Input
3ABCDEFGHAAABAACADAEAFAGAHACAC
Sample Output
AABBB
题意：给一个主串s，然后要找出一个串ans，ans是s中没出现过的子串里字典序最小的
思路：很容易得知这个串的长度不会超过8，所以建一个trie树，把s中每个长度小于8的串都插入树中，最后bfs一遍看哪个结点没给标记到的就是答案。这个方法是我比赛一开始想到的好麻烦的方法。AC之后想到一个简便的方法，把他看成8进制数，abcdefg对应0到8，开一个vis数组把每个子串都标记一下，然后循环找一下就行了
trie代码： 模拟进制的懒得写了
#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std;const int maxnode = 2396744;typedef pair<int,int> pii;//const int maxnode = 1000000;const int sigma_size = 8;struct Trie{ int ch[maxnode][sigma_size]; int fa[maxnode]; char let[maxnode]; int sz; void init() { sz=1; memset(ch[0],0,sizeof(ch[0])); } int idx(char c) {return c-‘A‘;} void insert(char *s,int n) { int u=0; for(int i=0;i<n;++i) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); fa[sz]=u; let[sz]=c+‘A‘; ch[u][c]=sz++; if(sz>=maxnode) cout<<"fuck this memory"<<endl; } u=ch[u][c]; } } char ans[10]; int ansz; void bfs() { int u; queue<int> q; q.push(0); while(!q.empty()) { u=q.front(); q.pop(); for(int i=0;i<sigma_size;++i) { if(ch[u][i]) { q.push(ch[u][i]); } else {//find// cout<<"find "<<u<<endl; ans[0]=i+‘A‘; ansz=1; print(u); return; } } } } void print(int u) { while(u) {// cout<<"."; ans[ansz++]=let[u]; u=fa[u]; }// cout<<"sz="<<ansz<<endl; for(int i=ansz-1;i>=0;--i) printf("%c",ans[i]); printf("\n"); } void text() { int i; for(i=0;i<sz;++i) { printf("%d: fa=%d let=%c\n",i,fa[i],let[i]); } }};char ms[1000005];Trie tree;void run(){ int i,len; scanf("%s",ms); len = strlen(ms); tree.init(); for(i=0;i<len;++i) { tree.insert(ms+i,min(8,len-i)); }// tree.text(); tree.bfs();}int main(){ //freopen("in","r",stdin); int _; scanf("%d",&_); while(_--) run(); return 0;}
hdu4886 TIANKENG’s restaurant(Ⅱ) （trie树或者模拟进制）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。