当前位置: 首页 > news >正文

CCF 第33次CCF计算机软件能力认证第二题

相似度计算

刷新 

时间限制: 1.0 秒

空间限制: 512 MiB

下载题目目录(样例文件)

题目背景

两个集合的 Jaccard 相似度定义为:𝑆𝑖𝑚(𝐴,𝐵)=∣𝐴∩𝐵∣∣𝐴∪𝐵∣Sim(A,B)=∣A∪B∣∣A∩B∣​即交集的大小除以并集的大小。当集合 𝐴A 和 𝐵B 完全相同时,𝑆𝑖𝑚(𝐴,𝐵)=1Sim(A,B)=1 取得最大值;当二者交集为空时,𝑆𝑖𝑚(𝐴,𝐵)=0Sim(A,B)=0 取得最小值。

题目描述

除了进行简单的词频统计,小 P 还希望使用 Jaccard 相似度来评估两篇文章的相似性。 具体来说,每篇文章均由若干个英文单词组成,且英文单词仅包含“大小写英文字母”。 对于给定的两篇文章,小 P 首先需要提取出两者的单词集合 𝐴A 和 𝐵B,即去掉各自重复的单词。 然后计算出:

  • ∣𝐴∩𝐵∣∣A∩B∣,即有多少个不同的单词同时出现在两篇文章中;
  • ∣𝐴∪𝐵∣∣A∪B∣,即两篇文章一共包含了多少个不同的单词。

最后再将两者相除即可算出相似度。 需要注意,在整个计算过程中应当忽略英文字母大小写的区别,比如 theThe 和 THE 三者都应被视作同一个单词。

试编写程序帮助小 P 完成前两步,计算出 ∣𝐴∩𝐵∣∣A∩B∣ 和 ∣𝐴∪𝐵∣∣A∪B∣;小 P 将亲自完成最后一步的除法运算。

输入格式

从标准输入读入数据。

输入共三行。

输入的第一行包含两个正整数 𝑛n 和 𝑚m,分别表示两篇文章的单词个数。

第二行包含空格分隔的 𝑛n 个单词,表示第一篇文章;

第三行包含空格分隔的 𝑚m 个单词,表示第二篇文章。

输出格式

输出到标准输出。

输出共两行。

第一行输出一个整数 ∣𝐴∩𝐵∣∣A∩B∣,即有多少个不同的单词同时出现在两篇文章中;

第二行输出一个整数 ∣𝐴∪𝐵∣∣A∪B∣,即两篇文章一共包含了多少个不同的单词。

样例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} ∣𝐴∣=8∣A∣=8

𝐵=B= {bles, fouler, les, lherbe, menue, par, picote} ∣𝐵∣=7∣B∣=7

𝐴∩𝐵=A∩B= {les, par} ∣𝐴∩𝐵∣=2∣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

子任务

80%80% 的测试数据满足:𝑛,𝑚≤100n,m≤100 且所有字母均为小写;

全部的测试数据满足:𝑛,𝑚≤104n,m≤104 且每个单词最多包含 1010 个字母。


先吐槽一下沟槽的CCF。不能提交看自己的代码能不能ac了。

这个题我一开始想到的是检索。

代码对不对我不清楚,给的样例全过了,我这个思路的话时间复杂度很小。

总体的思路是a,b,c等26个字母赋值为1,2,3,4-.....26这样的值,用一个结构体储存。如果要判断这个字符是否已经出现,假入我们现在用的是字符串判定,那么每一个字符都要判定,增加了时间复杂度,我们可以在转化成小写的时候做一些处理。我们可以记录路径过程:abc路径过程为321,这样可以保证每一个字符串有唯一的对应的路径。也需要记录路径的和:还是上面的情况,路径和为1+2+3=6。路径和可以作为检索的下标(最大也就260,10个z)。为什么不采用路径过程作为检索下标呢?因为路径过程的值很大,需要非常大的空间(可以达到longlong范围)。我们采用vector二维数组来储存两个字符串。储存a,b(第一个和第二个)字符串的时候顺便记录重复的单词temp_same。在记录b时,我们还需要记录多少个不同的单词同时出现在两篇文章中cnt_same。最后结果就是cnt_same和n+m-temp_same-cnt_same。

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
struct A
{long long l=0;//记录路径 假设a=1,b=2,c=3;那么abc为321; int tot=0;//记录路径总和假设a=1,b=2,c=3;那么abc为6; int cnt=0;//记录出现了多少次 bool j=0;string s;
}a;
vector<vector<A> >v(300);
vector<vector<A> >v1(300);
int cnt_same=0;
bool w_0(int temp )
{return ((temp/10)!=0);
}
A lowercase(string s)
{int l=s.length();A a;a.s=s;int chang=0,temp;//记录a.l长度 for(int i=0;i<l;i++){if(s[i]<'a')//大写情况 {temp=s[i]-'A'+1;a.tot+=temp;a.l+=temp*pow(10,chang);chang+=w_0(temp)+1;}else{temp=s[i]-'a'+1;a.tot+=temp;a.l+=temp*pow(10,chang);chang+=w_0(temp)+1;}}return a;
}
int main()
{int n,m;string s;cin>>n>>m;int temp_same=0;//记录每一行字符串自己内部重复的总数量 for(int i=0;i<n;i++){cin>>s;a=lowercase(s);int flag=0;for(int j=0;j<v[a.tot].size();j++){if(v[a.tot][j].l==a.l){v[a.tot][j].cnt++;temp_same++;flag=1;break;}}if(flag==0){a.cnt++;v[a.tot].push_back(a);} }//第一个字符串处理完毕 for(int i=0;i<m;i++){cin>>s;a=lowercase(s);int flag=0;for(int j=0;j<v[a.tot].size();j++){if(v[a.tot][j].l==a.l){if(v[a.tot][j].j==0){v[a.tot][j].j=1;cnt_same++;}}}//记录多少相同的单词 for(int j=0;j<v1[a.tot].size();j++){if(v1[a.tot][j].l==a.l){v1[a.tot][j].cnt++;temp_same++;flag=1;break;}}if(flag==0){a.cnt++;v1[a.tot].push_back(a);} }cout<<cnt_same<<endl;cout<<m+n-temp_same-cnt_same<<endl;
}

相关文章:

CCF 第33次CCF计算机软件能力认证第二题

相似度计算 刷新 时间限制&#xff1a; 1.0 秒 空间限制&#xff1a; 512 MiB 下载题目目录&#xff08;样例文件&#xff09; 题目背景 两个集合的 Jaccard 相似度定义为&#xff1a;&#x1d446;&#x1d456;&#x1d45a;(&#x1d434;,&#x1d435;)∣&#x1d…...

python 学习积累

持续更新中 感受python的强大之case列举&#xff1a; 1. 生成的map list要经过json格式化写入文件&#xff0c;请用python实现这一需求 import json map{"name": "张三", "age": 18, "address": "北京"} list[] for i in …...

ARM day1总结

思维导图...

套路化编程:C# ListView 保存、恢复列宽度

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 目录 技术基础 保存列头 删…...

python单元测试

文章目录 单元测试定义断言函数Test FixturesMockpatch装饰器模拟&#xff08;首选&#xff09;上下文管理器模拟手动模拟 测试实例 测试覆盖率pytest框架起步安装使用常用参数跳过测试pytest.fixtureconftest.py参数化测试 数据库查询的mock覆盖率 单元测试 定义 单元测试是…...

华为---静态路由-浮动静态路由及负载均衡(二)

7.2 浮动静态路由及负载均衡 7.2.1 原理概述 浮动静态路由(Floating Static Route)是一种特殊的静态路由&#xff0c;通过配置去往相同的目的网段&#xff0c;但优先级不同的静态路由&#xff0c;以保证在网络中优先级较高的路由&#xff0c;即主路由失效的情况下&#xff0c…...

Maven deploy上传远程私服失败

Failed to execute goal org.apache.maven.plugins:maven-deploy-plugin:2.8.2:deploy (default-deploy) on project 你的项目: Cannot deploy artifacts when Maven is in offline mode 解决方案&#xff1a; 1.IDEA把这个钩子去掉 2. settings.xml里把 <offline>标…...

通天星CMSV6车载定位监控平台 point_manage/merge SQL注入致RCE漏洞复现

0x01 产品简介 通天星CMSV6车载定位监控平台拥有以位置服务、无线3G/4G视频传输、云存储服务为核心的研发团队,专注于为定位、无线视频终端产品提供平台服务,通天星CMSV6产品覆盖车载录像机、单兵录像机、网络监控摄像机、行驶记录仪等产品的视频综合平台。 0x02 漏洞概述 …...

图像识别技术在人脸识别领域的新突破

图像识别技术在人脸识别领域的新突破主要体现在多个方面&#xff0c;这些突破不仅提高了人脸识别的准确性和效率&#xff0c;还拓展了其应用领域。以下是对这些新突破的详细归纳&#xff1a; 深度学习技术的应用&#xff1a; 深度学习技术&#xff0c;特别是卷积神经网络&…...

iview 组件里面的(任何一个月)整月日期全部选中_iview时间轴选中有历史记录日期

iview 组件里面的整月日期全部选中&#xff1a; ①&#xff1a;第一种是当前月的日期全部选中&#xff1a; 先上效果图&#xff1a;当前月分 获取到的值&#xff1a; 当前月的方法&#xff1a; // getDateStr() {// var curDate new Date();// var curMonth curDate.ge…...

Charles配置与API数据抓取

2024软件测试面试刷题&#xff0c;这个小程序&#xff08;永久刷题&#xff09;&#xff0c;靠它快速找到工作了&#xff01;&#xff08;刷题APP的天花板&#xff09;-CSDN博客跳槽涨薪的朋友们有福了&#xff0c;今天给大家推荐一个软件测试面试的刷题小程序。https://blog.c…...

[FreeRTOS 内部实现] 信号量

文章目录 基础知识创建信号量获取信号量释放信号量信号量 内部实现框图 基础知识 [FreeRTOS 基础知识] 信号量 概念 创建信号量 #define queueQUEUE_TYPE_BINARY_SEMAPHORE ( ( uint8_t ) 3U ) #define semSEMAPHORE_QUEUE_ITEM_LENGTH ( ( uint8_t ) 0U ) #define xSe…...

Vue57-组件的自定义事件_解绑

给谁绑的自定义事件&#xff0c;就找谁去触发&#xff1b;给谁绑的自定义事件&#xff0c;就找谁去解绑&#xff1b; 一、解绑自定义事件 1-1、解绑一个自定义事件 到student.vue组件中去解绑。 1-2、解绑多个自定义事件 使用数组来解绑多个。 1-3、解绑所有的自定义事件 二、…...

Java启动jar设置内存分配详解

在微服务架构越来越盛行的情况下&#xff0c;我们通常一个系统都会拆成很多个小的服务&#xff0c;但是最终部署的时候又因为没有那么多服务器只能把多个服务部署在同一台服务器上&#xff0c;这个时候问题就来了&#xff0c;服务器内存不够&#xff0c;这个时候我们就需要对每…...

Feign Client超时时间设置不生效问题

在使用Feign Client时&#xff0c;可以通过两种方式来设置超时时间&#xff1a; 针对整个Feign Client设置超时时间 可以在Feign Client的配置类中通过修改Request.Options对象来设置超时时间。Request.Options对象有两个属性&#xff0c;connectTimeoutMillis用于设置连接超…...

Haproxy部署Web群集

概论 HAProxy是可提供高可用性、负载均衡以及基于TCP和HTTP应用的代理&#xff0c;是免费、快速并且可靠的一种解决方案。HAProxy非常适用于并发大&#xff08;并发达1w以上&#xff09;web站点&#xff0c;这些站点通常又需要会话保持或七层处理。HAProxy的运行模式使得它可以…...

C++STL梳理

CSTL标准手册&#xff1a; https://cplusplus.com/reference/stl/ https://cplusplus.com/reference/vector/vector/at/ 1、STL基础 1.1、STL基本组成(6大组件13个头文件) 通常认为&#xff0c;STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成&…...

找出1000以内的所有的完数

完数的概念&#xff1a;完数&#xff08;Perfect Number&#xff09;是一个正整数&#xff0c;它等于除了它本身以外所有正因子之和。例如&#xff0c;6的因子有1、2、3和6&#xff0c;其中1236&#xff0c;所以6是一个完数。 #include <stdio.h> // 函数用于计算一个数…...

3110. 字符串的分数

给你一个字符串 s 。一个字符串的 分数 定义为相邻字符 ASCII 码差值绝对值的和。 请你返回 s 的 分数 。 示例 1&#xff1a; 输入&#xff1a;s "hello" 输出&#xff1a;13 解释&#xff1a; s 中字符的 ASCII 码分别为&#xff1a;h 104 &#xff0c;e 1…...

Mybatis MySQL allowMultiQueries 一次性执行多条语句

在JDBC 增加参数allowMultiQueries jdbc:mysql://localhost:3306/abc?&allowMultiQueriestrue <insert id"addRi" parameterType"java.util.List">DELETE FROM sys_ri WHERE sr_id #{roId} AND sr_fion_id #{fod};INSERT into sys_rVALUES&…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...