更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202403-1 词频统计

时间限制： 1.0 秒

空间限制： 512 MiB

题目描述

在学习了文本处理后，小 P 对英语书中的

n

n

n 篇文章进行了初步整理。 具体来说，小 P 将所有的英文单词都转化为了整数编号。假设这

n

n

n 篇文章中共出现了

m

m

m 个不同的单词，则把它们从

1

1

1 到

m

m

m 进行编号。 这样，每篇文章就简化为了一个整数序列，其中每个数都在

1

1

1 到

m

m

m 范围内。

现给出小 P 处理后的

n

n

n 篇文章，对于每个单词

i

i

i（

1

≤

i

≤

m

1 \leq i \leq m

1≤i≤m），试统计：

单词

i

i

i 出现在了多少篇文章中？单词

i

i

i 在全部文章中总共出现了几次？

输入格式

从标准输入读入数据。

输入共

n

+

1

n+1

n+1 行。

输入的第一行包含两个正整数

n

n

n 和

m

m

m，分别表示文章篇数和单词编号上限。

输入的第

i

+

1

i + 1

i+1 行（

1

≤

i

≤

n

1 \leq i \leq n

1≤i≤n）包含由空格分隔的若干整数， 其中第一个整数

l

i

l_i

li​ 表示第

i

i

i 篇文章的长度（单词个数）； 接下来

l

i

l_i

li​​ 个整数表示对应的整数序列，序列中每个整数均在

1

1

1 到

m

m

m 范围内，各对应原文中的一个单词。

输出格式

输出到标准输出。

输出共

m

m

m 行。

第

i

i

i 行（

1

≤

i

≤

m

1 \leq i \leq m

1≤i≤m）输出由空格分隔的两个整数

x

i

x_i

xi​​ 和

y

i

y_i

yi​​，表示共有

x

i

x_i

xi​ 篇文章包含单词

i

i

i，总计出现次数为

y

i

y_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

2

2 在：

文章

1

1

1 中出现两次；文章

3

3

3 中出现三次；文章

4

4

4 中出现一次。

因此

x

2

=

3

x_2 = 3

x2​=3、

y

2

=

6

y_2 = 6

y2​=6。

子任务

全部的测试数据满足

0

<

n

,

m

≤

100

0 < n, m \leq 100

0<n,m≤100，且每篇文章至少包含一个单词、最多不超过

100

100

100 个单词（

1

≤

l

i

≤

100

1 \leq l_i \leq 100

1≤li​≤100）。

题解

a

i

a_i

ai​ 表示单词

i

i

i 出现在了多少篇文章中；

b

i

b_i

bi​ 表示单词

i

i

i 在全部文章中总共出现了几次；

v

i

s

i

vis_i

visi​ 表示从第

1

1

1 篇文章到第

n

n

n 篇遍历文章，最后一次遇到单词

i

i

i 是在哪篇文章。

对于

a

i

a_i

ai​，如果遇到了

i

i

i 单词，判断

v

i

s

i

vis_i

visi​ 是否为当前文章，如果不是就代表

a

i

a_i

ai​ 出现在了一篇新的文章中，那么就将

a

i

a_i

ai​ 加上

1

1

1，并将

v

i

s

i

vis_i

visi​ 变为当前文章。

对于

b

i

b_i

bi​，如果遇到了

i

i

i 单词，直接将

b

i

b_i

bi​ 加上

1

1

1 即可。

时间复杂度：

O

(

100

n

+

m

)

\mathcal{O}(100n+m)

O(100n+m)。

参考代码（2ms，3656KB）

/*

Created by Pujx on 2024/5/8.

*/

#pragma GCC optimize(2, 3, "Ofast", "inline")

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

//#define int long long

//#define double long double

using i64 = long long;

using ui64 = unsigned long long;

using i128 = __int128;

#define inf (int)0x3f3f3f3f3f3f3f3f

#define INF 0x3f3f3f3f3f3f3f3f

#define yn(x) cout << (x ? "yes" : "no") << endl

#define Yn(x) cout << (x ? "Yes" : "No") << endl

#define YN(x) cout << (x ? "YES" : "NO") << endl

#define mem(x, i) memset(x, i, sizeof(x))

#define cinarr(a, n) for (int _ = 1; _ <= n; _++) cin >> a[_]

#define cinstl(a) for (auto& _ : a) cin >> _

#define coutarr(a, n) for (int _ = 1; _ <= n; _++) cout << a[_] << " \n"[_ == n]

#define coutstl(a) for (const auto& _ : a) cout << _ << ' '; cout << endl

#define all(x) (x).begin(), (x).end()

#define md(x) (((x) % mod + mod) % mod)

#define ls (s << 1)

#define rs (s << 1 | 1)

#define ft first

#define se second

#define pii pair<int, int>

#ifdef DEBUG

#include "debug.h"

#else

#define dbg(...) void(0)

#endif

const int N = 2e5 + 5;

//const int M = 1e5 + 5;

const int mod = 998244353;

//const int mod = 1e9 + 7;

//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }

//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N], b[N], vis[N];

int n, m, t, k, q;

void work() {

cin >> n >> m;

for (int i = 1; i <= n; i++) {

cin >> t;

for (int j = 1; j <= t; j++) {

cin >> k;

if (vis[k] != i) a[k]++, vis[k] = i;

b[k]++;

}

}

for (int i = 1; i <= m; i++)

cout << a[i] << ' ' << b[i] << endl;

}

signed main() {

#ifdef LOCAL

freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);

freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);

#endif

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

int Case = 1;

//cin >> Case;

while (Case--) work();

return 0;

}

/*

_____ _ _ _ __ __

| _ \ | | | | | | \ \ / /

| |_| | | | | | | | \ \/ /

| ___/ | | | | _ | | } {

| | | |_| | | |_| | / /\ \

|_| \_____/ \_____/ /_/ \_\

*/

关于代码的亿点点说明：

代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ... 是用来开启 O2、O3 等优化加快代码速度。中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。"debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。