学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1880

题目讲的是，给出n对字符串，给出其中一者，输出另一者。主要是练习BKDHash的使用。

刚开始用到了map，但是MLE了，后来改善了一下，打了个擦边球，差一点点就MLE了，不过还是AC了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>

using namespace std;

vector<string> F,E;//分别存储前半部分和后半部分
vector<int> f_h_p[100000],f_p_h[100000],e_h_p[100000],e_p_h[100000];
//f_h_p[i]F对应hash值i所包含的输入序号
//f_p_h[i]F对应输入序号的字符串所在的hash值
//......

int BKDHash(char *c){
    int hash=0;
    while(*c) hash=hash*31+(*c++);
    return (hash&0x7fffffff)%100000;
}

char ch[300];
int main(){
    //freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\in.txt","r",stdin);
    string s,ss;
    int cnt=0;
    while(scanf("%[^\n]",ch)!=EOF){
        getchar();//吸收回车
        if(strcmp(ch,"@END@")==0) break;
        char *cch=ch;
        s.clear();ss.clear();
        for(;*cch!=' ';cch++)
            s+=*cch;//获取前半段
        for(cch++;*cch;cch++)
            ss+=*cch;//获取后半段
        F.push_back(s);E.push_back(ss);
        int t1=BKDHash(&s[0]),t2=BKDHash(&ss[0]);
        f_h_p[t1].push_back(cnt);f_p_h[cnt].push_back(t1);
        e_h_p[t2].push_back(cnt);e_p_h[cnt].push_back(t2);
        cnt++;
        //cout<<s<<":"<<ss<<endl;
    }
    int n;cin>>n;getchar();//吸收回车
    for(int i=0;i<n;i++){
        scanf("%[^\n]",ch);getchar();
        int t=BKDHash(ch);
        int op=0;
        if(*ch!='['){
            for(int j=0;j<e_h_p[t].size();j++){
                int p=e_h_p[t][j];
                if(strcmp(&E[p][0],ch)==0){
                    for(int k=1;k<F[p].size()-1;k++)
                        cout<<F[p][k];
                    cout<<endl;
                    op=1;
                    break;
                }
            }
        }else{
            for(int j=0;j<f_h_p[t].size();j++){
                int p=f_h_p[t][j];
                if(strcmp(&F[p][0],ch)==0){
                    cout<<E[p]<<endl;
                    op=1;
                    break;
                }
            }
        }
        if(!op) cout<<"what?\n";
    }
    return 0;
}