题目描述

 哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。

 给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”

输入

 首先列出词典中不超过100000条不同的魔咒词条，每条格式为：

[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以@”结束，这一行不属于词典中的词条。

词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。

输出

 每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”

 

以下借鉴了几位网友的思路和代码

样例输入

[expelliarmus] the disarming charm[rictusempra] send a jet of silver light to hit the enemy[tarantallegra] control the movement of one's legs[serpensortia] shoot a snake out of the end of one's wand[lumos] light the wand[obliviate] the memory charm[expecto patronum] send a Patronus to the dementors[accio] the summoning charm@END@4[lumos]the summoning charm[arha]take me to the sky

样例输出

light the wandacciowhat?what?

提示

 使用stl当中的map将对应的字符串建立一一映射。 

代码如下:

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
          
         
        
       
      
     

 

题解：如果数据量小，每个字符串的长度小的话，直接使用map<string,string>轻松解决，但是数据量大，字符串的长度可能很长，这样会造成超时和超内存的问题，因此使用和映射解决

1 #include
     
       2 #include
      
         3 #include
       
      
     

 

思路

模拟赛上拉的题目，意思很简单，给你多行“【咒语】功能”以“@END@”结尾，最后输入字符串查询，要求输入的如果是功能输出咒语，如果是咒语输出功能，都不存在则输出“what？”，首先想到的就是直接用map映射但是数据量太大有10w想着肯定会超内存，就没有用后来想到用Hash+二分快速查找，但是没学会字符串Hash无奈只能对着字符串进行二分查找结果浪费很多时间还wa掉了，后来看榜单发现大家基本都写出来了，就猜肯定是hd数据弱果断暴力遍历着查找，虽然在数组范围上坑了几次，最后还是AC，果然是弱数据。赛完就赶紧学了字符串Hash把我比赛中没实现的想法给实现了，效率果然比暴力高了很多。就是将每一个串Hash一个值（这里用BKDRHash是java用的Hash算法可以达到10W数据无冲突hash值是32位整数），用结构体将这个Hash值与字符串的位置对应起来，来达到随机读取的目的，把输入的字典全部Hash后将这些Hash值排序，方便二分查找。

PS：后来有找来了几个10W的数据结果果断wa掉，看来不解决Hash冲突还是不行的，可能真的是hd数据水的没有冲突把，或者后来找到数据专门对几个Hash算法进行的针对，看来对于大数据的题目还是要解决问题

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define N 100005 7 using namespace std; 8 char spell[N][85];//储存功能 9 char magic[N][25];//储存咒语10 int num=1;11 struct node//Hash值对应的数组下标12 {13     int Hash;14     int l;15 } key[N],tail[N];//咒语和功能16 int cmp(node a,node b)17 {18     return a.Hash
         
        
       
      
     

 

分析：

此题其实就是字符串哈希的模板题，将字符串s1映射到s2,输入s1求s2,输入s2求s1

第一反应是用STL，但此题用map会MLE或TLE，所以手写哈希表

字符串哈希的方法如下：

1.将前8位字母的ASCII码乘积作为key(用long long存），转换为数字的哈希问题

2.用数组和链表存储，key对应的字符串存在数组下标为key%c(c为常数）的地方

若key%c相同，则存在链表里,下图直观展示了该过程(图中数字为key)

3.查找时先到key对应的数组，如果元素不对，则继续遍历链表，直到查到该元素

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int c=10000; 6 struct myhash{
   //评测机上hash是关键字 7     struct node { 8         long long key;//若key%c相同辅助判重 9         string s1;//若key相同辅助判重10         string s2;//要查找的东西,字符串s1对应的字符串s211         node* next;//链表用指针12     }a[c+5];13     void push(long long x,string s1,string s2) {
   //插入函数14         if(a[x%c].key==0) {
   //如果数组x%c处没有元素，直接插入15             a[x%c].key=x;16             a[x%c].s1=s1;17             a[x%c].s2=s2;18         } else {
   //如果有，链表插入新节点（头插入）19             node *tmp=new node();20             tmp->key=x;21             tmp->s1=s1;22             tmp->s2=s2;23             tmp->next=a[x%c].next;//此处相当于head24             a[x%c].next=tmp;25         }26     }27     string found(long long x,string s1) {
   //查找函数28         if(a[x%c].key==x&&a[x%c].s1==s1) return a[x%c].s2;//如果字符串在数组里，直接返回对应的字符串s229         if(a[x%c].key==0) return "what?";//如果数组里没有元素，链表里肯定也没有，返回what?30         else {31             node* tmp=a[x%c].next;//遍历链表查找32             while(tmp!=NULL) {33                 if(tmp->key==x&&tmp->s1==s1) return tmp->s2;34                 tmp=tmp->next;35             }36             return "what?";37         }38     }39 };40 myhash H1,H2;//H1存储名字对应的内容，H2存储内容对应的名字41 long long to_num(string str){
   //前8位的乘积hash 42     long long ans=1;43     int len=str.length();44     if(len>8) len=8;45     for(int i=0;i
        
         >t;65     getchar();//输入一个换行符，否则换行符会被getline读入到str中,导致在哈希表中查找'\n'，多输出一个"what?"66     while(t--){67         getline(cin,str);68         bool have_kuo=false;//区分输入的是内容还是名字69         for(int i=0;i