CCFCSP备考第一天

第33次认证第一题——词频统计

时间限制： 1.0 秒

空间限制： 512 MiB

下载题目目录（样例文件）

题目描述

在学习了文本处理后，小 P 对英语书中的 n 篇文章进行了初步整理。具体来说，小 P 将所有的英文单词都转化为了整数编号。假设这 n 篇文章中共出现了 m 个不同的单词，则把它们从 1 到 m 进行编号。这样，每篇文章就简化为了一个整数序列，其中每个数都在 1 到 m 范围内。

现给出小 P 处理后的 n 篇文章，对于每个单词 i（1≤i≤m），试统计：

单词 i 出现在了多少篇文章中？
单词 i 在全部文章中总共出现了几次？

输入格式

从标准输入读入数据。

输入共 n+1 行。

输入的第一行包含两个正整数 n 和 m，分别表示文章篇数和单词编号上限。

输入的第 i+1 行（1≤i≤n）包含由空格分隔的若干整数，其中第一个整数 li 表示第 i 篇文章的长度（单词个数）；接下来 li 个整数表示对应的整数序列，序列中每个整数均在 1 到 m 范围内，各对应原文中的一个单词。

输出格式

输出到标准输出。

输出共 m 行。

第 i 行（1≤i≤m）输出由空格分隔的两个整数 xi 和 yi，表示共有 xi 篇文章包含单词 i，总计出现次数为 yi。

样例输入

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 中出现一次。

因此 x2=3、y2=6。

子任务

全部的测试数据满足 0<n,m≤1000<n,m≤100，且每篇文章至少包含一个单词、最多不超过 100100 个单词（1≤li≤1001≤li≤100）。

参考题解

#include<iostream>
#include<vector>
#include<cstring> //用于memset 
using namespace std;

int main()
{
	vector<vector<int> > data; //注意不要写成>>，要有空格，否则编译器会认为这是一个位移运算符！！
	int n, m;
	cin>> n >> m;
	int result[m][2] = {0}; //输出结果，行数为单词编号，列数为2，分别是文章数，出现次数
	
	/*注意，C++中局部数组不会自动初始化为0！要手动初始化！！*/ 
	//memset(result, 0, sizeof(result)); 傻了，直接在定义时初始化效率更高
	 
	for(int i = 0; i < n; i++){
		int count; //该行有多少个字母，即后面还有多少个int数值 
		cin >> count;
		vector<int> row_data;
//		bool flag = true;单个不行，应该要给每个单词设置一个flag
		bool appeared[m];
		memset(appeared, 0, sizeof(appeared)); //初始化为false
		 
		for(int j = 0; j < count; j++){
			int num;
			cin >> num;
			row_data.push_back(num);
			
			if(!appeared[num-1]){
				appeared[num-1] = true; //一篇文章只统计一次 
				result[num-1][0] += 1;//出现的文章数+1
			}
			result[num-1][1] += 1;//单词出现数+1 
		}
		data.push_back(row_data);
	}
	
	cout << "读取数据如下" << endl;
	for(const auto& row : data){
		for(const auto&num : row){
			cout << num << " ";
		}
		cout << endl;
	}
	cout << "输出结果如下" << endl;
	for(int i = 0; i < m; i++){
		cout << result[i][0] <<" " << result[i][1]<< endl;
	} 
	return 0;
}

简化版

#include <iostream>
#include <vector>
#include <cstring>  // 用于 memset
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int result[m][2];  // 输出结果，行数为单词编号，列数为2，分别是文章数，出现次数
    
    // 注意，C++中局部数组不会自动初始化为0！要手动初始化！！
    memset(result, 0, sizeof(result));

    // 遍历每篇文章
    for (int i = 0; i < n; i++) {
        int count;
        cin >> count;
        bool appeared[m] = {false};  // 每篇文章内单词是否出现的标记

        for (int j = 0; j < count; j++) {
            int num;
            cin >> num;

            // 如果该单词尚未在本篇文章中出现过，增加文章数
            if (!appeared[num - 1]) {
                appeared[num - 1] = true;
                result[num - 1][0] += 1;  // 出现的文章数 + 1
            }
            result[num - 1][1] += 1;  // 单词出现次数 + 1
        }
    }

    // 输出结果
    for (int i = 0; i < m; i++) {
        cout << result[i][0] << " " << result[i][1] << endl;
    }
    return 0;
}