首页 > 代码库 > 魔咒词典
魔咒词典
hdu1880:http://acm.hdu.edu.cn/showproblem.php?pid=1880
题意:中文题,直接看题。
题解:第一法用hash做的的题目。虽然用了很长时间,但是还是AC了。而且用了string 所以有点慢。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 char str[100002][30]; 7 int n,top; 8 string line[100002]; 9 struct Node{10 long long val;11 int id;12 bool operator<(const Node a)const {13 return val<a.val;14 }15 }num[2][100002];16 long long hash1[2][100002];17 long long t1,t2;18 string line2;19 int solve(int flag,long long val){20 int l=1,r=top;21 while(l<r){22 int mid=(l+r)/2;23 if(num[flag][mid].val>=val)24 r=mid;25 else26 l=mid+1;27 }28 return num[flag][l].id;29 }30 int main(){31 top=0;32 memset(num,0,sizeof(num));33 while(~scanf("%s",str[++top])){34 if(str[top][0]==‘@‘){35 top--;36 break;37 }38 getchar();39 getline(cin,line[top]);40 int len=strlen(str[top]);41 t1=t2=0;42 for(int i=0;i<len;i++){43 t2=t1*13+(int)str[top][i];44 t1=t2;45 }46 hash1[0][top]=t2;47 num[0][top].val=t2;48 num[0][top].id=top;49 len=line[top].length();50 t1=t2=0;51 for(int i=0;i<len;i++){52 t2=t1*13+(int)line[top][i];53 t1=t2;54 }55 num[1][top].val=t2;56 num[1][top].id=top;57 hash1[1][top]=t2;58 }59 sort(num[0]+1,num[0]+top+1);60 sort(num[1]+1,num[1]+top+1);61 scanf("%d",&n);62 getchar();63 for(int i=1;i<=n;i++){64 getline(cin,line2);65 int ll=line2.length();66 t1=t2=0;67 for(int i=0;i<ll;i++){68 t2=t1*13+(int)line2[i];69 t1=t2;70 }71 int as=0,ans=0;72 if(line2[0]==‘[‘){73 as=solve(0,t2);74 if(hash1[0][as]==t2){75 cout<<line[as]<<endl;76 }77 else78 printf("what?\n");79 }80 81 else{82 as=solve(1,t2);83 if(hash1[1][as]==t2){84 ans=as;int tp=strlen(str[as]);85 for(int j=1;j<tp-1;j++)86 printf("%c",str[as][j]);87 printf("\n");88 }89 else{90 printf("what?\n");91 }92 93 }94 }95 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。