The Preliminary Contest for ICPC Asia Xuzhou 2019【B. so easy】(set 解法 与正解 unordered_map+并查集)
发布日期:2021-06-29 14:25:26
浏览次数:3
分类:技术文章
本文共 1442 字,大约阅读时间需要 4 分钟。
题目大意
给你两个操作,op=1时,将那个数不可用,op=2时进行查询功能 找到从x开始第一个存在的数
非官方题解
set 内置红黑树,有默认从小到大排序功能,所以我们可以暴力一发,不过要逆向思维,对于op=1,我们就放入set中 对于op=2,我们就判断是否存在于set中,然后判断一下是否在n范围内 最后输出位置跳出循环
#include#include using namespace std;set st;int n,m;int main(){ while(~scanf("%d%d",&n,&m)){ st.clear(); while(m--){ int p,x; int ff=1; scanf("%d%d",&p,&x); if(p==1) st.insert(x); else{ for(int i=x;i<=n&&ff;i++){ if(!st.count(i)){ printf("%d\n",i); ff=0; } } } } } return 0;}
官方题解
今天算是开了眼界,知道了unordered_map 其实和map差不多,简单讲一下区别:map和set差不多都有内置红黑树,就会自动按key值按字典序从小到大排序 而unordered_map 是采用了哈希函数,没有了排序功能 从名字就看的出来。。。 但是强大的点我们甚至可以用常数的时间进行查找的功能 最坏情况下也才是O(n) 而map的话因为排序了起步都是O(nlogn) 然后官方题解采用方式还添加了并查集
不过本题把下面代码unordered_map 改为map也能过
#includeusing namespace std;unordered_map mp;int n,m;int find_pre(int x){ if(!mp.count(x)) return x; return mp[x]=find_pre(mp[x]);}int main(){ scanf("%d %d",&n,&m); int op,x; while(m--){ scanf("%d %d",&op,&x); if(op==1) mp[x]=find_pre(x+1); else{ x=find_pre(x); if(x>n) printf("-1\n"); else printf("%d\n",x); } } return 0;}
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/100605154 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月17日 09时52分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
最全架构设计实践方法论: 微服务
2019-04-29
Linux下简单几步安装AI开发环境-ROS(超有意思)
2019-04-29
epoll详解
2019-04-29
linux入门--磁盘管理之分区、格式化与挂载
2019-04-29
鸿蒙(二)基于小熊派实现LOT上云的智慧家居项目
2019-04-29
开发必备:HTTP 及 TLS
2019-04-29
Windows 11答疑:大家最关心的10个问题
2019-04-29
select、poll、epoll之间的区别
2019-04-29
Shopify!Shopify!Shopify!
2019-04-29
这是美国MarTech最大的一家独立公司:HubSpot
2019-04-29
从开发到产出:关于机器学习的七则干货建议
2019-04-29
你想成为数据科学家吗?不要把机器学习当成入门第一课
2019-04-29
你想成为数据科学家吗?不要把机器学习当成入门第一课
2019-04-29
现代社会悖论:信息泛滥是一只不守规矩的野兽
2019-04-29
如何设计自己的第一个加密交易机器人?
2019-04-29
浪费在Excel上的时间:如何开始专家式机器学习实验追踪?
2019-04-29
失业三星期:我寻找第二份编程工作之路
2019-04-29
跳过媒介,我们能不能只用思想控制计算机?
2019-04-29
服务器宕机:谷歌最近经历了“黑客攻击”吗?
2019-04-29
RepVGG:极简架构,SOTA性能,让VGG式模型再次伟大
2019-04-29