在学习了文本处理后,小 PP 对英语书中的 nn 篇文章进行了初步整理。
具体来说,小 PP 将所有的英文单词都转化为了整数编号。
假设这 nn 篇文章中共出现了 mm 个不同的单词,则把它们从 11 到 mm 进行编号。
这样,每篇文章就简化为了一个整数序列,其中每个数都在 11 到 mm 范围内。
现给出小 PP 处理后的 nn 篇文章,对于每个单词 ii(1≤i≤m1≤i≤m),试统计:
- 单词 ii 出现在了多少篇文章中?
- 单词 ii 在全部文章中总共出现了几次?
输入格式
输入共 n+1n+1 行。
输入的第一行包含两个正整数 nn 和 mm,分别表示文章篇数和单词编号上限。
输入的第 i+1i+1 行包含由空格分隔的若干整数,其中第一个整数 lili 表示第 ii 篇文章的长度(单词个数);接下来 lili 个整数表示对应的整数序列,序列中每个整数均在 11 到 mm 范围内,各对应原文中的一个单词。
输出格式
输出共 mm 行。
第 ii 行输出由空格分隔的两个整数 xixi 和 yiyi,表示共有 xixi 篇文章包含单词 ii,总计出现次数为 yiyi。
数据范围
全部的测试数据满足 0<n,m≤1000<n,m≤100,且每篇文章至少包含一个单词、最多不超过 100100 个单词(1≤li≤1001≤li≤100)。
输入样例:
4 3
5 1 2 3 2 1
1 1
3 2 2 2
2 3 2
输出样例:
2 3
3 6
2 2
样例解释
单词 22 在:
- 文章 11 中出现两次;
- 文章 33 中出现三次;
- 文章 44 中出现一次。
因此 x2=3,y2=6x2=3,y2=6。
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{// n 表示文章的篇数,m 表示单词编号的上限int n, m;// x[i] 用于记录单词 i 出现在多少篇文章中int x[101];// y[i] 用于记录单词 i 在全部文章中总共出现的次数int y[101];// t[i] 用于记录单词 i 上一次出现所在文章的编号// 通过比较这个编号和当前文章编号,判断单词是否在新文章中出现int t[101];cin >> n >> m;// a 用于存储当前文章的长度(单词个数)// b 用于临时存储当前文章中读取的单词编号int a, b;// 遍历每一篇文章,n 在这里也作为文章编号,从 n 到 0while(n --){// 读取当前文章的长度cin >> a;// 遍历当前文章中的每个单词for(int i = 1; i <= a ; i ++) {// 读取当前文章中的一个单词编号cin >> b;// 判断单词 b 是否在新的文章中出现// t[b] 记录了单词 b 上一次出现所在文章的编号// 如果 t[b] 不等于当前文章编号 n,说明单词 b 在新文章中首次出现if(t[b] != n) {// 单词 b 出现的文章篇数加 1x[b] ++;// 更新单词 b 所在的文章编号为当前文章编号t[b] = n;}// 无论单词 b 是否在新文章中出现,只要出现,其总出现次数就加 1y[b]++; }}// 遍历从 1 到 m 的每个单词编号for(int i = 1; i <= m ; i ++){// 输出单词 i 出现的文章篇数和在所有文章中的总出现次数cout << x[i] << " " << y[i] << endl;}return 0;
}