【CSP】2022–09-3 防疫大数据 100分 STL大模拟 使用map优化索引 有坑得注意
2022–09-3 防疫大数据 STL大模拟 使用map优化索引
- 2022–09-3 防疫大数据 STL大模拟 使用map优化索引
- 基本思路
- 遇到的问题(学到的东西)
- 感悟
- 完整代码
2022–09-3 防疫大数据 STL大模拟 使用map优化索引
这题中规中矩,不算太难也不算太简单,难点就是能否理清逻辑,注意细节 (这题好坑找bug找了好久啊也怪自己太傻),但是这些错,自己不写是不知道的,还得自己找出来,加深自己的印象。
基本思路
做csp的大模拟题的基本思路就是,将给的数据用一定的数据结构存起来,这个数据结构要方便后边搜索,然后题目的问题一般本质就是搜索。所以要仔细读题,如果给出了形式化描述(数学表达式)尽量用题目给的表达式来写代码,这样错的概率更低。
针对于本题,题目的数据分为两类,一类是城市数据,另一类游客的到访数据,然后题目就差不多是求他们两个的交集(用题目给定的规则来交)。
城市的数据是 给出有风险的城市的集合,风险的开始日期是给出数据的日期
游客的到访数据 是给出到访的时间 到访的地点 游客id
注意游客这里就有两个日期:收到到访数据的日期, 和访问的日期
我们分别建立索引,城市用城市id建立索引、游客用收到数据的日期建立索引,然后搜索的时候,就会加快速度找到。
然后根据题目的要求来匹配
形式化地,在 d 日生成的风险名单中,用户 u 被列入风险名单,当且仅当:
存在一个日期 d 0 ∈ ( d − 7 , d ] d_0 \in (d-7,d] d0∈(d−7,d],存在一条 d 0 d_0 d0 日收到的漫游数据 < d 1 , u , r > <d_1,u,r> <d1,u,r>,使得
- d 1 ∈ ( d − 7 , d ] d_1 \in (d-7,d] d1∈(d−7,d],并且
- 对于任意的 D ∈ [ d 1 , d ] D \in [d_1,d] D∈[d1,d],地区 r 在 D 日处于风险状态。
所以就是要遍历d日的前6天的到访数据,然后判断该地是不是风险地区在那个区间上。
遇到的问题(学到的东西)
这题随便一写什么都不用考虑,只要模拟出来了基本都是40分,然后我一开始就是40分,然后怎么也找不到bug,然后逐渐找到了几个bug但是还是40分,最终参考别人的代码还是找到了bug,考场上要是找不到只能认栽了。
- 风险地区的风险区间合并问题
这个问题我一开始,没有注意到,就是要把风险区间有交集的进行合并,但是这个合并的逻辑有了一点点问题,下面会提到
- 风险地区的风险区间合并问题的实现
实现的过程中是后一个插入前一个的,但是会导致最后一个没有插入
修改之前
// 合并一下区间for (auto item : place_time){struct places temp;temp.length = -1; // 标记为还没初始化for (auto p : item.second){if (temp.length != -1 && p.day >= temp.day && p.day <= temp.day + temp.length){int end1 = p.day + p.length - 1;int end2 = temp.day + temp.length - 1;temp.length += end1 - end2;}else{place_time2[item.first].push_back(temp);temp = p;}}}并且会报错,因为没有初始化的temp也会被插入
修改后的
// 合并一下区间for (auto item : place_time){struct places temp;temp.length = -1; // 标记为还没初始化for (auto p : item.second){if (temp.length != -1 && p.day >= temp.day && p.day <= temp.day + temp.length){int end1 = p.day + p.length - 1;int end2 = temp.day + temp.length - 1;temp.length += end1 - end2;}else{if (temp.length != -1)place_time2[item.first].push_back(temp);temp = p;}}if (temp.length != -1)place_time2[item.first].push_back(temp);}
- 判断是不是风险用户的问题
这点一开始是自己找的规律然后按着自己想到去判断的,没想到的少了一些条件,然后补上了,但是仍然是40分,之后百思不得其解
- 区间合并的逻辑问题
原来这个区间合并,不只是有交集的区间合并,就算是没有交集但是中间没有间隔的区间也要合并的,这点我是看了别人的代码才想到的,考试要是碰见这个直接就g了
修改之前
// 合并一下区间for (auto item : place_time){struct places temp;temp.length = -1; // 标记为还没初始化for (auto p : item.second){if (temp.length != -1 && p.day >= temp.day && p.day <= temp.day + temp.length-1){int end1 = p.day + p.length - 1;int end2 = temp.day + temp.length - 1;temp.length += end1 - end2;}else{if (temp.length != -1)place_time2[item.first].push_back(temp);temp = p;}}if (temp.length != -1)place_time2[item.first].push_back(temp);}修改之后
// 合并一下区间for (auto item : place_time){struct places temp;temp.length = -1; // 标记为还没初始化for (auto p : item.second){if (temp.length != -1 && p.day >= temp.day && p.day <= temp.day + temp.length){int end1 = p.day + p.length - 1;int end2 = temp.day + temp.length - 1;temp.length += end1 - end2;}else{if (temp.length != -1)place_time2[item.first].push_back(temp);temp = p;}}if (temp.length != -1)place_time2[item.first].push_back(temp);}就是这个
if (temp.length != -1 && p.day >= temp.day && p.day <= temp.day + temp.length)改变了
之后就可以拿到了100分,

5. 还学到了使用freopen()
如果你的csp考场上 无法往终端里复制数据,可以直接使用
freopen("1.txt", "r", stdin);
注意1.txt是相对路径,可以替换成你的输入的路径,然后其他什么都不用改变,就可以了。
感悟
这题竟然是没有一次做出来,而且还是看了别人的思路才找出来问题的。中间其实改了很多次,就是没有改到点上,以后联系的时候,如果不是真错了,就不改,或者要保留原版的,不然没办法真正的找到错误。
如果考试中有这中情况,得把每个实现的点都列出来,然后逐个分析,不能一带而过,想一想真的是这样的吗?尤其是写if的时候的。而且不能只盯着一个点不看别的,浪费时间又找不到错误。
完整代码
#include <bits/stdc++.h>
using namespace std;
int n;
struct dayget
{int u;int day; // 到达的一天
};
struct places
{int id; // 地方的idint day; // 风险的开始日期int length; // 风险的长度
};
unordered_map<int, unordered_map<int, vector<dayget>>> arrive; // arrive[i][j]第i天收到j地到的用户的集合
unordered_map<int, vector<places>> place_time; // place_time[i] id为i的地方的风险时间片段的集合
unordered_map<int, vector<places>> place_time2; // place_time[i] id为i的地方的风险时间片段的集合
unordered_set<int> risks[1010]; // 存储每天的风险用户
bool searchIsDanger(int d1, int d, vector<places> dage)
{for (int i = 0; i < dage.size(); i++){if (dage[i].day <= d1 && dage[i].day + dage[i].length - 1 >= d){return true;}}return false;
}
int main()
{// freopen("1.txt", "r", stdin);cin >> n;for (int i = 0; i < n; i++){int r, m;cin >> r >> m;for (int j = 0; j < r; j++){int p;cin >> p;struct places t = {p, i, 7};place_time[p].push_back(t);}for (int j = 0; j < m; j++){int d, u, r1;cin >> d >> u >> r1;struct dayget t = {u, d};if (d < i - 6) // 如果收到收到消息的是7天之前的就不要了continue;arrive[i][r1].push_back(t);}}// 合并一下区间for (auto item : place_time){struct places temp;temp.length = -1; // 标记为还没初始化for (auto p : item.second){if (temp.length != -1 && p.day >= temp.day && p.day <= temp.day + temp.length){int end1 = p.day + p.length - 1;int end2 = temp.day + temp.length - 1;temp.length += end1 - end2;}else{if (temp.length != -1)place_time2[item.first].push_back(temp);temp = p;}}if (temp.length != -1)place_time2[item.first].push_back(temp);}for (int d = 0; d < n; d++){for (int i = max(0, d - 6); i <= d; i++){for (auto c : arrive[i]) // 分析第i天到访的所有地方{int r = c.first;for (auto user : c.second) // 到访r地的所有的人 然后判断是不是该设定为风险人员{int d1 = user.day;if (d1 >= d - 6 && searchIsDanger(d1, d, place_time2[r])){risks[d].insert(user.u);}}}}}for (int i = 0; i < n; i++){cout << i << ' ';vector<int> risk1(risks[i].begin(), risks[i].end());sort(risk1.begin(), risk1.end());for (auto item : risk1){cout << item << ' ';}cout << endl;}
}
相关文章:
【CSP】2022–09-3 防疫大数据 100分 STL大模拟 使用map优化索引 有坑得注意
2022–09-3 防疫大数据 STL大模拟 使用map优化索引 2022–09-3 防疫大数据 STL大模拟 使用map优化索引基本思路遇到的问题(学到的东西)感悟完整代码 2022–09-3 防疫大数据 STL大模拟 使用map优化索引 这题中规中矩,不算太难也不算太简单&am…...
【Linux基础(三)】信号
学习分享 1、信号的基本概念2、查看信号列表3、常见信号名称4、signal库函数5、发送信号kill6、kill - signal (无参信号)示例6.1、kill - signal (不可靠信号)示例6.2、kill - signal (可靠信号)示例 7、信号分类7.1、信号运行原理分类7.2、信号是否携带…...
GEE图像可视化常用函数
目录 图层操作Map.addLayer()Map.centerObject() 直方图ui.Chart.image.histogram() 时间序列统计ui.Chart.image.series()ui.Chart.image.seriesByRegion() …...
c++基础语法
文章目录 前言命名空间命名空间的使用 缺省参数缺省参数的使用 函数重载函数重载的作用函数重载的使用函数重载原理 引用引用的使用引用的使用场景引用和指针 extern Cinlineauto范围fornullptr 前言 大家好我是jiantaoyab,这篇文章给大家带来的是c语言没有的一些特…...
【工作实践-07】uniapp关于单位rpx坑
问题:在浏览器页面退出登录按钮上“退出登录”字样消失,而在手机端页面正常;通过查看浏览器页面的HTML代码,发现有“退出登录”这几个字,只不过由于样式问题,这几个字被挤到看不见了。 样式代码中有一行为:…...
服务层组件
目录 连接层(Connection Pool) SQL接口(SQL Interface) 查询缓存(Caches&Buffers) Management Services&Utilities 查询分析器(Parser) 优化器(Optimizer)...
【学习笔记】VMware vSphere 6.7虚拟化入门
VMware vSphere 6.7虚拟化入门课程介绍 课程内容 1、VMware vSphere 6.7虚拟化入门课程介绍 2、ESXi6.7控制台设置 3、使用vSpkere Host client管理虚拟机 4、VMware EsXi基础操作 5、VMware Esxi存储管理 6、管理ESXi主机网络与虚拟机网络 7、安装配置vCenter Server Applia…...
如何防范企业内部安全威胁?
1 用户行为分析(UEBA) 现代化的用户行为分析产品具有多种优势功能,使企业能够有效地检测内部威胁。用户行为分析软件通过收集和分析来自各种来源的数据来分析和检测内部人员的可疑行为。这些来源包括网络日志和用户活动日志。通过检查这些数…...
内网渗透-跨域环境渗透-1
目录 smbclient工具 mimikatz工具 Kerbers协议 NTLM认证 hash传递攻击(PTH攻击) 黄金票据攻击 白银票据 MS14-068 smbclient工具 在linux里面连接远程windows共享目录,可以使用这个工具 第一种连接方式:smbclient -L 目…...
安信可IDE(AiThinker_IDE)编译ESP8266工程方法
0 工具准备 AiThinker_IDE.exe ESP8266工程源码 1 安信可IDE(AiThinker_IDE)编译ESP8266工程方法 1.1 解压ESP8266工程文件夹 我们这里使用的是NON-OS_SDK,将NON-OS_SDK中的1_UART文件夹解压到工作目录即可 我这里解压到了桌面,…...
【java数据结构】HashMap和HashSet
目录 一.认识哈希表: 1.1什么是哈希表? 1.2哈希表的表示: 1.3常见哈希函数: 二.认识HashMap和HashSet: 2.1关于Map.Entry的说明:,> 2.2Map常用方法说明: 2.3HashMap的使用案例: 2.4Set常见方法…...
基于Springboot的高校汉服租赁网站(有报告)。Javaee项目,springboot项目。
演示视频: 基于Springboot的高校汉服租赁网站(有报告)。Javaee项目,springboot项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构…...
分布式解决方案
目录 1. 分布式ID1-1. 传统方案1-2. 分布式ID特点1-3. 实现方案1-4. 开源组件 2. 分布式Session2-1. 传统Session2-2. Spring-Session2-3. Token Redis2-4. JWT2-5. 拦截器统一处理Token2-6. Oauth2 3. 分布式锁3-1. redis3-2. Zookeeper 1. 分布式ID 1-1. 传统方案 时间戳U…...
力扣刷题日记——L724. 寻找数组的中心下标
1. 前言 今天是力扣刷题日记的第二天,今天依旧是一道简单题啊,慢慢来,先看看题目是什么吧。 2. 题目描述 给你一个整数数组 nums ,请计算数组的 中心下标。 数组 中心下标 是数组的一个下标,其左侧所有元素相加的和…...
【Kotlin】类和对象
1 前言 Kotlin 是面向对象编程语言,与 Java 语言类似,都有类、对象、属性、构造函数、成员函数,都有封装、继承、多态三大特性,不同点如下。 Java 有静态(static)代码块,Kotlin 没有࿱…...
Docker完整版(一)
Docker完整版(一) 一、Docker概述1.1、Docker简介1.2、Docker的用途1.3、容器与虚拟机的区别1.4、Docker系统架构1.5、Docker仓库 二、Docker引擎2.1、Docker引擎架构2.2、Docker引擎分类2.3、Docker引擎的安装2.4、Docker镜像加速器 三、Docker镜像3.1、…...
AIOPS:Zabbix结合讯飞星火做自动化告警+邮件通知并基于人工智能提供解决方案
目前Zabbix官方已经提供Zabbix+ChatGPT的解决方案 ChatGPT一周年,你充分利用了吗?Zabbix+ChatGPT,轻松化解告警! 但是由于需要魔法等其他因素,比较不稳定,遂决定使用国内模型,这里我挑选的是讯飞星火,基于我之前的文档,在此基础上通过Zabbix的告警脚本实现调用AI模型…...
AHU 汇编 实验六
一、实验名称:实验6 输入一个16进制数,把它转换为10进制数输出 实验目的: 培养汇编中设计子程序的能力 实验过程: 源代码: data segmentbuff1 db Please input a number(H):$buff2 db 30,?,30 dup(?),13,10buff3 …...
Linux的输出、输入重定向和管道
目录 输出重定向 输入重定向 < << 管道操作 输出重定向 当我输⼊⼀个命令之后,回⻋,命令产⽣了结果,结果默认是输出到屏幕上的。 默认情况,⽆论⼀个命令执⾏正确与否,结果都会默认输出到屏幕上。 在有…...
java-新手笔记(枚举)
枚举(Enumeration)是一种特殊的类,用于表示固定数量的常量值。 枚举类型使得代码更加清晰,易于维护,同时也增加了类型安全。 这边使用一个枚举封装重要数据 enum Day {SUNDAY,MONDAY,TUESDAY,WEDNESDAY,THURSDAY,FR…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
