WEEK15作业 A - ZJM 与霍格沃兹（必做）

A - ZJM 与霍格沃兹（必做）

题目

思路

这题卡空间。要实现两个字符串的相互转化，若直接建立字符串到字符串的映射，会超过限制空间。如果将字符串存入数组里，用哈希算法将字符串转化为一个独一无二的数字，建立数字和字符串数组下标的映射并存入map，则比字符串-字符串映射少用一半左右的空间。

查询时先用哈希算法函数将字符转化为数字，再通过map得到字符串数组的下标，就得到了目标字符串。

●以上算法完成时，还是mle了。。。我把哈希函数的返回值类型改成int才险过。

代码

#include <iostream>
#include <map>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int seed=7;
const int themod=1e9;
int Hash(string s) {
	int temp=0;
	for (int i=0;i<s.size(); i++) {
		temp=(temp+(long long)(s[i])*seed)%themod;
		temp=temp*seed%themod; 
	}
	return temp;	
}

int n,cnt1=0,cnt2=0;
map<int,int> map1;
string v[200010];
string s,temp,str1,str2;
int main() {
	while(true)
	{
		getline(cin,s);
		if(s=="@[e-mail]") break;
		str1=s.substr(0,s.find("] ")+1);
		str2=s.substr(s.find("] ")+2,s.size()-s.find("] ")-1);
		v[cnt1++]=str1;
		v[cnt1++]=str2;
		map1.insert({Hash(str1),cnt2++});
		map1.insert({Hash(str2),cnt2++});
	}
	cin>>n;
	getchar();
	for(int i=1;i<=n;i++) {
		getline(cin,s);
		if(map1.find(Hash(s))==map1.end()) cout<<"what?"<<endl;
		else {
			if(s[0]=='[') {
				temp=v[map1[Hash(s)]+1];
				cout<<temp<<endl;
			}
			else {
				temp=v[map1[Hash(s)]-1];
				cout<<temp.substr(1,temp.size()-2)<<endl;
			}
		}
	}
	return 0;
}