【csp202403 | 您所在的位置:网站首页 › 大小写相似的字母 › 【csp202403 |
题目背景
两个集合的 Jaccard 相似度定义为: 即交集的大小除以并集的大小。当集合𝐴和𝐵完全相同时,𝑆𝑖𝑚(𝐴,𝐵)=1取得最大值;当二者交集为空时,𝑆𝑖𝑚(𝐴,𝐵)=0取得最小值。 问题描述除了进行简单的词频统计,小P还希望使用Jaccard相似度来评估两篇文章的相似性。具体来说,每篇文章均由若干个英文单词组成,且英文单词仅包含“大小写英文字母”。 对于给定的两篇文章,小P首先需要提取出两者的单词集合𝐴和𝐵,即去掉各自重复的单词。 然后计算出: ∣𝐴∩𝐵∣,即有多少个不同的单词同时出现在两篇文章中;∣𝐴∪𝐵∣,即两篇文章一共包含了多少个不同的单词。最后再将两者相除即可算出相似度。需要注意,在整个计算过程中应当忽略英文字母大小写的区别,比如the、The和THE三者都应被视作同一个单词。 试编写程序帮助小 P 完成前两步,计算出∣𝐴∩𝐵∣和∣𝐴∪𝐵∣;小P将亲自完成最后一步的除法运算。 输入格式从标准输入读入数据。 输入共三行。 输入的第一行包含两个正整数𝑛和𝑚,分别表示两篇文章的单词个数。 第二行包含空格分隔的𝑛个单词,表示第一篇文章; 第三行包含空格分隔的𝑚个单词,表示第二篇文章。 输出格式输出到标准输出。 输出共两行。 第一行输出一个整数∣𝐴∩𝐵∣,即有多少个不同的单词同时出现在两篇文章中; 第二行输出一个整数∣𝐴∪𝐵∣,即两篇文章一共包含了多少个不同的单词。 样例1输入3 2 The tHe thE the THE 样例1输出1 1 样例1解释A=B=A∩B=A∪B={the} 样例2输入9 7 Par les soirs bleus dete jirai dans les sentiers PICOTE PAR LES BLES FOULER LHERBE MENUE 样例2输出2 13 样例2解释A={bleus, dans, dete, jirai, les, par, sentiers, soirs} ∣𝐴∣=8 𝐵={bles, fouler, les, lherbe, menue, par, picote} ∣𝐵∣=7 𝐴∩𝐵={les, par} ∣𝐴∩𝐵∣=2 样例3输入15 15 Thou that art now the worlds fresh ornament And only herald to the gaudy spring Shall I compare thee to a summers day Thou art more lovely and more temperate 样例3输出4 24 数据范围80%的测试数据满足:𝑛,𝑚≤100且所有字母均为小写; 全部的测试数据满足:𝑛,𝑚≤104且每个单词最多包含10个字母。 题解本题要求两篇文章单词的交集和并集,我们只需要知道两篇文章中一共出现了多少不同的单词,以及同时在两篇文章中出现过的单词数,我们不需要知道一个单词在哪篇文章中出现过。 对于每一个单词开一个计数器,统计它在几篇文章中出现过,由于一个单词可能在一篇文章中出现多次,我们需要对单词进行标记,只有在一篇文章中第一次出现的时候才令计数器加一。 最后,不同单词的总个数就是并集的大小,计数为2的单词个数就是交集的大小。 由于给的单词大小写不一致,可以先预处理把字母统一换成小写字母或者大写字母。 #include #include #include #include using namespace std; int n,m,s1,s2; string ch; map mp; map vis; int main() { int i,j,len; scanf("%d%d",&n,&m); for (i=1;i>ch; len=ch.length(); for (j=0;j='A' && ch[j]ch; len=ch.length(); for (j=0;j='A' && ch[j]0) s2++; } printf("%d\n%d\n",s1,s2); return 0; } |
CopyRight 2018-2019 实验室设备网 版权所有 |