首页 > 代码库 > 魔咒词典

魔咒词典

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 }
View Code