A - ZJM 与霍格沃兹 （Week15 作业）

A - ZJM 与霍格沃兹

Sample Input

[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

Sample Output

light the wand
accio
what?
what?	

实现思路

这个题对mermory要求比较高，map<string,string>会导致Memory Limit Exceeded。因此我们需要用哈希算法求出每一个字符串对应的哈希值，利用哈希值来存储、查找；另外，要注意数据的范围，我直接用了unsigned long long,也可以加上一个Mod

PS：本题用G++会Memory Limit Exceeded,改用C++则AC

代码实现

#include<iostream>
#include<map>
#include<string.h>
#include<string>
using namespace std;
map<unsigned long long,string> mpr;
map<unsigned long long,string> mpl;
int n;
const int seed=7;
unsigned long long func(string &p)
{
	unsigned long long ans = 0;
	int len = p.length()-1; 
	unsigned long long tmp = seed;
	for(int i=0;i<len;i++)
	{
		if(p[i]!=' ')
		{
			ans+=p[i]*tmp;
			tmp*=seed;
		}
	}
	return ans;
}
int main()
{
	string s;
	string tl;
	string tr;
	while(getline(cin,s))
	{
		if(s=="@END@") break;
		for(int i=1;i<s.length();i++)
		{
			if(s[i]==']')
			{
				tl=s.substr(0,i+1);
				tr=s.substr(i+2,s.length());
				mpl.insert(pair<unsigned long long,string>(func(tl),tr));
				mpr.insert(pair<unsigned long long,string>(func(tr),tl));
				break;
			}
		}
	}
	cin>>n;
	string f;
	getchar();
	for(int i=0;i<n;i++)
	{
		getline(cin,f);
		if(mpr.find(func(f))!=mpr.end()) 
		{
			string tmp;
			tmp = mpr[func(f)];
			int len = tmp.length()-1;
			for(int j=1;j<len;j++) cout<<tmp[j];
			cout<<endl;
		}
		else if(mpl.find(func(f))!=mpl.end()) cout<<mpl[func(f)]<<endl;
		else cout<<"what?"<<endl;
	}
	return 0;
 }