Day9
题目描述
在学习了文本处理后，小 \(P\) 对英语书中的 \(n\) 篇文章进行了初步整理。
具体来说，小 \(P\) 将所有的英文单词都转化为了整数编号。
假设这 \(n\) 篇文章中共出现了\(m\) 个不同的单词，则把它们从 \(1\) 到 \(m\) 进行编号。
这样，每篇文章就简化为了一个整数序列，其中每个数都在 \(1\) 到 \(m\) 范围内。
现给出小 \(P\) 处理后的 \(n\) 篇文章，对于每个单词 \(i\)\(（1≤i≤m）\)，试统计：
单词 \(i\) 出现在了多少篇文章中？
单词 \(i\) 在全部文章中总共出现了几次？
输入格式
输入共 \(n+1\) 行。
输入的第一行包含两个正整数 \(n\) 和 \(m\)，分别表示文章篇数和单词编号上限。
输入的第 \(i+1\) 行包含由空格分隔的若干整数，其中第一个整数 \(l_i\) 表示第 \(i\) 篇文章的长度（单词个数）；接下来 \(l_i\)
个整数表示对应的整数序列，序列中每个整数均在 \(1\) 到 \(m\) 范围内，各对应原文中的一个单词。
输出格式
输出共 \(m\) 行。
第 \(i\) 行输出由空格分隔的两个整数 \(x_i\) 和 \(y_i\)，表示共有 \(x_i\) 篇文章包含单词 \(i\)，总计出现次数为 \(y_i\)。
数据范围
全部的测试数据满足 \(0<n,m≤100\)，且每篇文章至少包含一个单词、最多不超过 \(100\) 个单词\(（1≤l_i≤100）\)。
输入样例：
4 3
5 1 2 3 2 1
1 1
3 2 2 2
2 3 2
输出样例：
2 3
3 6
2 2
样例解释
单词 \(2\)在：文章 \(1\) 中出现两次；文章 $3 $中出现三次；文章 $4 $中出现一次。因此 \(x_2=3,y_2=6\)。\
题目分析
语法题
统计序列含数字次数和数字在序列中出现出现总次数
C++代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 110;
int n , m;
bool st[N][N];
map<int , int> p;
map<int , int> cnt;
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++ )
{
int l;
cin >> l;
while(l --)
{
int x;
cin >> x;
if(!st[i][x])
{
st[i][x] = true;
p[x] ++;
}
cnt[x] ++;
}
}
for(int i = 1 ; i <= m ; i ++)
cout << p[i] << ' ' << cnt[i] << '\n';
}
题目描述
两个集合的 Jaccard 相似度定义为：
\(Sim(A,B)=\frac{|A∩B|}{|A∪B|}\)
即交集的大小除以并集的大小。
当集合 \(A\) 和 \(B\) 完全相同时，\(Sim(A,B)=1\) 取得最大值；当二者交集为空时，\(Sim(A,B)=0\) 取得最小值。
除了进行简单的词频统计，小 \(P\) 还希望使用 Jaccard 相似度来评估两篇文章的相似性。
具体来说，每篇文章均由若干个英文单词组成，且英文单词仅包含“大小写英文字母”。
对于给定的两篇文章，小 \(P\) 首先需要提取出两者的单词集合 \(A\) 和 \(B\)，即去掉各自重复的单词。
然后计算出：\(|A∩B|\)，即有多少个不同的单词同时出现在两篇文章中；\(|A∪B|\)，即两篇文章一共包含了多少个不同的单词。最后再将两者相除即可算出相似度。
需要注意，在整个计算过程中应当忽略英文字母大小写的区别，比如 the、The 和 THE 三者都应被视作同一个单词。
试编写程序帮助小 \(P\) 完成前两步，计算出 \(|A∩B|\) 和 \(|A∪B|\)；小 \(P\) 将亲自完成最后一步的除法运算。
输入格式
输入共三行。
输入的第一行包含两个正整数 \(n\) 和 \(m\)，分别表示两篇文章的单词个数。
第二行包含空格分隔的 \(n\) 个单词，表示第一篇文章；
第三行包含空格分隔的 \(m\) 个单词，表示第二篇文章。
输出格式
输出共两行。
第一行输出一个整数 \(|A∩B|\)，即有多少个不同的单词同时出现在两篇文章中；
第二行输出一个整数 \(|A∪B|\)，即两篇文章一共包含了多少个不同的单词。
数据范围
全部的测试数据满足：\(1≤n,m≤10^4\) 且每个单词最多包含 \(10\) 个字母。
输入样例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\} \quad |A|=8\)
\(B=\{bles, fouler, les, lherbe, menue, par, picote\} \quad |B|=7\)
\(A∩B=\{les, par\} \quad |A∩B|=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
题目解析
集合论基本运算
其实就是将字符串处理后，放入集合处理，字符串哈希和set都能做，方式很多，api也很多，对了就行
C++代码
#include <bits/stdc++.h>
using namespace std;
int n , m;
set<string> p , s;
map<string , int> mp;
string to_low(string x)
{
string res = "";
for(auto it : x)
res += tolower(it);
return res;
}
int main()
{
cin >> n >> m;
for(int i = 0 ; i < n ; i ++)
{
string x;
cin >> x;
x = to_low(x);
p.insert(x);
mp[x] ++;
}
for(int i = 0 ; i < m ; i ++)
{
string x;
cin >> x;
x = to_low(x);
p.insert(x);
if(mp[x]) s.insert(x);
}
cout << s.size() << '\n' << p.size();
return 0;
}