题解：UVA10295 Hay Points

UVA10295 Hay Points

题目大意

给定一个单词表，以及表内每个单词的权值。

给定若干篇文章。定义一篇文章的得分为出现的所有单词的权值和（不在单词表内的单词的权值为 $0$），求出每篇文章的得分。

思路

可以说是 std::map 的模板题。

具体来说，建立一个 std::string 到 int 的映射，记录每个单词的权值。

输入文章时，依次检查每个单词是否在 map 中有映射，有则将对应的权值加到答案中即可。

一个小的优化是，可以使用 C++11 中加入的基于 hash 的 std::unordered_map，将单次查询的平均时间复杂度降至 $\mathcal{O}(1)$。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
#include<unordered_map>
#define map unordered_map
using namespace std;
/*================*/

inline int read() {
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

#define r(a) (a)=read()

int m,n,a,tot;
string s;
map<string,int> mp;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>m>>n;
	while (m--) {
		cin>>s>>a;
		mp[s]=a;  //建立映射关系
	}
	while (cin>>s) {
		if (s==".") {
			cout<<tot<<"\n";
			tot=0;
		}
		else if (mp.find(s)!=mp.end())  //查找是否存在映射
			tot+=mp[s];
	}
	return 0;
}