可以做h5的网站,韶关网站建设制作,建设银行网网站打不开,创业找项目更多 CSP 认证考试题目题解可以前往#xff1a;CSP-CCF 认证考试真题题解 原题链接#xff1a; 202403-1 词频统计
时间限制#xff1a; 1.0 秒 空间限制#xff1a; 512 MiB
题目描述
在学习了文本处理后#xff0c;小 P 对英语书中的 n n n 篇文章进行了初步整理。 … 更多 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 n1 n1 行。
输入的第一行包含两个正整数 n n n 和 m m m分别表示文章篇数和单词编号上限。
输入的第 i 1 i 1 i1 行 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 x23、 y 2 6 y_2 6 y26。
子任务
全部的测试数据满足 0 n , m ≤ 100 0 n, m \leq 100 0n,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}(100nm) O(100nm)。
参考代码
/*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 pairint, int
#ifdef DEBUG#include debug.h
#else#define dbg(...) void(0)
#endifconst 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 LOCALfreopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.in, r, stdin);freopen(C:\\Users\\admin\\CLionProjects\\Practice\\data.out, w, stdout);
#endifios::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 函数分开写纯属个人习惯主要是为了多组数据。
