第33次CCF计算机软件能力认证【T1~T3】：词频统计、相似度计算、化学方程式配平

🕗 发布于 2024-10-06 03:47 高斯消元枚举模拟算法 STL

题目	概括
词频统计	枚举
相似度计算	STL工具（tranform()转换大小写）+ 模拟
化学方程式配平	大模拟+高斯消元

1、词频统计

在学习了文本处理后，小 P 对英语书中的 n 篇文章进行了初步整理。

具体来说，小 P 将所有的英文单词都转化为了整数编号。

假设这 n 篇文章中共出现了 m 个不同的单词，则把它们从 1 到 m 进行编号。

这样，每篇文章就简化为了一个整数序列，其中每个数都在 1 到 m 范围内。

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

单词 i 出现在了多少篇文章中？单词 i 在全部文章中总共出现了几次？输入格式输入共 n+1 行。

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

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

输出格式输出共 m 行。

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

数据范围全部的测试数据满足 0<n,m≤100 ，且每篇文章至少包含一个单词、最多不超过 100 个单词（1≤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
样例解释单词 2 在：
文章 1 中出现两次；
文章 3 中出现三次；
文章 4 中出现一次。
因此 x2=3,y2=6 。

思路：

较为简单，按照步骤对题目进行枚举即可

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m; 

const int N= 103; 

//统计所有文章总共包含几个i，并且包含i的文章的个数 

int a[N][N];
int lth[N];//记录长度数组 
int ma[N];
int cnt,mark;

int main()
{
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
{
cin>>lth[i];
for(int j=1;j<=lth[i];j++)
{
scanf("%d",&a[i][j]);
}
}

//开始统计个数,从单词编号入手 
for(int i=1;i<=m;i++)
{
cnt=0;
bool flag=false;
mark=0;
for(int j=1;j<=n;j++)//枚举每一个数组 
{
for(int k=1;k<=lth[j];k++)//枚举到每一个序列的最后一个 
{
if(a[j][k]==i)
{
    cnt++;
    flag=true;
}

}
if(flag)
{
mark++;//记录出现此数的文章的篇数
flag=false;
} 
}
cout<<mark<<" "<<cnt<<endl;
} 

return 0;
}

2、相似度计算

两个集合的 Jaccard 相似度定义为：

Sim(A,B)=|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≤104 且每个单词最多包含 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}|A|=8 B= {bles, fouler, les, lherbe,
menue, par, picote}|B|=7 A∩B= {les, par}|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

思路：

由于不区分大小写，所以把所有的字母都统一转化为大写进行处理（用到transform函数来处理字符串）

string x;
cin>>x;
transform(x.begin(),x.end(),x.begin(),::toupper);

用set进行去重，这样就可以简单的处理数据

代码：

#include<bits/stdc++.h>

using namespace std;

int n,m; 

const int N=1e4;

unordered_set<string>s1,s2;

int main()
{
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
{
string x;
cin>>x;
transform(x.begin(),x.end(),x.begin(),::toupper);

s1.insert(x);
}
int cnt=0;
for(int i=1;i<=m;i++)
{
string x;
cin>>x;
transform(x.begin(),x.end(),x.begin(),::toupper);

s2.insert(x);
}

for(auto t:s1)
{
if(s2.find(t)!=s2.end())
{
cnt++;
}
}

int total=s1.size()+s2.size();
cout<<cnt<<endl<<total-cnt;
return 0;
}

3、化学方程式配平

![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/c7958f2fbeae49c8911a5ab674dfed9c.jpe

思路：

很显然是一个高斯消元（题目也进行了提示），但在这之前要妥善处理好数据，以便于正确、方便的运用
对数据的处理，转化为矩阵的函数：

void getElement(string str, int &index, int in)
{
    str = str + '#';
    string ele = "";
    int num = 0;
    bool complete = false;
    for (int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if (c >= '0' && c <= '9')
        {
            complete = true;
            num = num * 10 + c - '0';
        }
        else
        {
            if (complete)
            {
                if (elei.find(ele) != elei.end())
                {
                    mat[elei[ele]][in] = num;
                }
                else
                {
                    elei[ele] = index++;
                    mat[elei[ele]][in] = num;
                }
                ele = c;
                num = 0;
                complete = false;
            }
            else
            {
                ele = ele + c;
            }
        }
    }
}

代码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 42;
double mat[N][N];
int n, m;
map<string, int> elei;
int index;

double eps = 1e-6;

void initMat()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            mat[i][j] = 0;
}

void getElement(string str, int &index, int in)
{
    str = str + '#';
    string ele = "";
    int num = 0;
    bool complete = false;
    for (int i = 0; i < str.size(); i++)
    {
        char c = str[i];
        if (c >= '0' && c <= '9')
        {
            complete = true;
            num = num * 10 + c - '0';
        }
        else
        {
            if (complete)
            {
                if (elei.find(ele) != elei.end())
                {
                    mat[elei[ele]][in] = num;
                }
                else
                {
                    elei[ele] = index++;
                    mat[elei[ele]][in] = num;
                }
                ele = c;
                num = 0;
                complete = false;
            }
            else
            {
                ele = ele + c;
            }
        }
    }
}

void _swap(int a, int b)
{
    double tmp;
    for (int i = 0; i < m; i++)
    {
        tmp = mat[a][i];
        mat[a][i] = mat[b][i];
        mat[b][i] = tmp;
    }
}

void _sub(int a, int b)
{
    double magni = mat[a][b] / mat[b][b];
    for (int i = b; i < m; i++)
    {
        mat[a][i] -= mat[b][i] * magni;
    }
}
int main()
{
    cin >> n;
    while (n--)
    {
        cin >> m;
        string str;
        initMat();
        elei.clear();
        index = 0;

        for (int i = 0; i < m; i++)
        {
            cin >> str;
            getElement(str, index, i);
        }
        for (int i = 0; i < m; i++)
        {
            int j;
            for (j = i; j < index; j++)
                if (fabs(mat[j][i]) >= eps)
                    break;

            if (j == index)
                continue;
            else if (j != i)
            {
                _swap(i, j); // swap i j
            }

            for (j = i + 1; j < index; j++)
            {
                if (fabs(mat[j][i]) >= eps)
                {
                    _sub(j, i); // j line sub i
                }
            }
        }
        int k;
        for (k = 0; k < index && k < m; k++)
            if (fabs(mat[k][k]) <= eps)
                break;
        if (k < m)
            cout << "Y" << endl;
        else
            cout << "N" << endl;
    }
    return 0;
}

原文地址：https://blog.csdn.net/2301_76941161/article/details/142719714

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：UE5 小地图的基础方法
下一篇：洛谷刷题 P1042 [NOIP2003 普及组] 乒乓球

【机器学习(十一)】糖尿病数据集分类预测案例分析—XGBoost分类算法—Sentosa_DSML社区版
相比传统代码方式，利用Sentosa_DSML社区版完成机器学习算法的流程更加高效和自动化，传统方式需要手动编写大量代码来处理数据清洗、特征工程、模型训练与评估，而在Sentosa_DSML社区版中，
阅读更多2024-10-06
C语言 | Leetcode C语言题解之第448题找到所有数组中消失的数字
C语言 | Leetcode C语言题解之第448题找到所有数组中消失的数字
阅读更多2024-10-06
网络编程面试题
第一次挥手（FIN）客户端发送一个带有FIN标志的段（FIN=1），表示客户端已经没有数据要发送了。客户端进入FIN_WAIT_1状态。第二次挥手（ACK）服务器收到FIN段后，发送一个带有ACK标志
阅读更多2024-10-06
R语言的下载、安装及环境配置（Rstudio&VSCode）
R for Windows是一个免费的用于统计计算和统计制图的优秀工具，是R语言开发工具。它拥有数据存储和处理系统、数组运算工具（其向量、矩阵运算方面功能尤其强大）、完整连贯的统计分析工具、优秀的统计
阅读更多2024-10-06
音视频入门基础：FLV专题（8）——FFmpeg源码中，解码Tag header的实现
FFmpeg源码中通过flv_read_packet函数解码每个Tag的Tag header，根据Tag header的TagType属性来判断该Tag为音频Tag，视频Tag还是脚本Tag，分别执行
阅读更多2024-10-06
胤娲科技：AI重塑会议——灵动未来，会议新纪元
灵动会议采用了RTE和AI双引擎架构，RTE技术确保低延迟、高可靠的音视频传输，让大模型能够接收到高质量的音视频内容，进行更准确的处理。同时，采用aPaaS低代码设计，提供灵活的API接口和即插即用的
阅读更多2024-10-06
【CSDN入门级教程】
你好！这是你第一次使用 Markdown编辑器所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。我们对Markdown编辑
阅读更多2024-10-06
k8s 中微服务之 MetailLB 搭配 ingress-nginx 实现七层负载
LoadBalancer和NodePort很相似，目的都是向外部暴露一个端口，区别在于LoadBalancer会在集群的外部再来做一个负载均衡设备，而这个设备需要外部环境支持的，外部服务发送到这个设备
阅读更多2024-10-06
TopK算法在大数据重复数据分析中的应用与挑战
在当今信息爆炸的时代，数据已成为企业和组织决策的重要依据。数据分析能够帮助识别趋势、优化流程并提升客户体验。通过对海量数据的深入分析，组织可以获取更具洞察力的信息，从而做出明智的决策，增强竞争力。To
阅读更多2024-10-06
在 Ubuntu ECS 实例上部署高性能安全的 Redis 服务指南
本文将详细介绍如何在 Ubuntu 系统的阿里云 ECS 实例上安装和配置 Redis，分配 2GB 内存，并进行全面的性能优化和安全配置，使其功能接近阿里云的商用 Redis 服务。通过上述步骤，您
阅读更多2024-10-06

第33次CCF计算机软件能力认证【T1~T3】：词频统计、相似度计算、化学方程式配平

1、词频统计

思路：

代码：

2、相似度计算

思路：

代码：

3、化学方程式配平

思路：

代码：

相关文章