网站开发一般学多久,自己做视频网站 在优酷推广,如何做电商网站视频,wordpress百度推广2022–09-3 防疫大数据 STL大模拟 使用map优化索引 2022–09-3 防疫大数据 STL大模拟 使用map优化索引基本思路遇到的问题#xff08;学到的东西#xff09;感悟完整代码 2022–09-3 防疫大数据 STL大模拟 使用map优化索引
这题中规中矩#xff0c;不算太难也不算太简单学到的东西感悟完整代码 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_mapint, unordered_mapint, vectordayget arrive; // arrive[i][j]第i天收到j地到的用户的集合
unordered_mapint, vectorplaces place_time; // place_time[i] id为i的地方的风险时间片段的集合
unordered_mapint, vectorplaces place_time2; // place_time[i] id为i的地方的风险时间片段的集合
unordered_setint risks[1010]; // 存储每天的风险用户
bool searchIsDanger(int d1, int d, vectorplaces 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 ;vectorint risk1(risks[i].begin(), risks[i].end());sort(risk1.begin(), risk1.end());for (auto item : risk1){cout item ;}cout endl;}
}
