問題描述
小易參與了一個(gè)記單詞的小游戲巢钓。游戲開始系統(tǒng)提供了m個(gè)不同的單詞，小易記憶一段時(shí)間之后需要在紙上寫出他記住的單詞霍弹。小易一共寫出了n個(gè)他能記住的單詞谒撼，如果小易寫出的單詞是在系統(tǒng)提供的，將獲得這個(gè)單詞長度的平方的分?jǐn)?shù)熄捍。注意小易寫出的單詞可能重復(fù)烛恤，但是對(duì)于每個(gè)正確的單詞只能計(jì)分一次。
輸入描述
輸入數(shù)據(jù)包括三行：
第一行為兩個(gè)整數(shù)n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)治唤。以空格分隔
第二行為n個(gè)字符串棒动，表示小易能記住的單詞，以空格分隔宾添，每個(gè)單詞的長度小于等于50船惨。
第三行為m個(gè)字符串，系統(tǒng)提供的單詞缕陕，以空格分隔粱锐，每個(gè)單詞的長度小于等于50。
輸出描述
輸出一個(gè)整數(shù)表示小易能獲得的分?jǐn)?shù)
輸入例子
3 4
apple orange strawberry
strawberry orange grapefruit watermelon
輸出例子
136
分析
用unordered_set存儲(chǔ)記住的單詞和系統(tǒng)單詞扛邑。有兩個(gè)好處：
1.保證沒有重復(fù)元素
2.find操作的時(shí)間復(fù)雜度為O(1)
note
unordered_set底層用hash實(shí)現(xiàn)怜浅，查找效率很高
代碼
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
unordered_set<string> rememberedWords, systemWords;
for (int i = 0; i < n; i++)
{
char word[51];
scanf("%s", word);
rememberedWords.insert(word);
}
for (int i = 0; i < m; i++)
{
char word[51];
scanf("%s", word);
systemWords.insert(word);
}
int grade = 0;
for (const auto str : rememberedWords)
{
if (systemWords.find(str) != systemWords.end())
{
int len = str.size();
grade += len * len;
}
}
printf("%d\n", grade);
return 0;
}
