企业官网建设流程全解析

静态网站托管,html网页制作源代码成品,企业网站货物查询怎么做,山西seo优化公司信奥赛C提高组csp-s之离散化 1. 什么是离散化#xff1f; 离散化是一种将无限或大范围的数据映射到有限、连续的小范围内的技术。 为什么需要离散化#xff1f; 数据范围太大#xff0c;无法直接作为数组下标#xff08;如10 9 ^9 9#xff09;只需要数据的相对大小关系…信奥赛C提高组csp-s之离散化1. 什么是离散化离散化是一种将无限或大范围的数据映射到有限、连续的小范围内的技术。为什么需要离散化数据范围太大无法直接作为数组下标如109 ^99只需要数据的相对大小关系不需要具体数值节省内存空间便于使用数组、线段树等数据结构2. 离散化的基本原理基本思想原始数据: [1000, 200000, 300, 1000, 5000] 离散化后: [1, 3, 0, 1, 2]保持原始数据的大小关系不变但将数值压缩到小范围内。3. 离散化的实现方法方法一排序 去重 二分查找最常用#includebits/stdc.husingnamespacestd;// 离散化函数vectorintfun(vectorintnums){vectorinttmpnums;// 1. 排序sort(tmp.begin(),tmp.end());// 2. 去重tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());// 3. 二分查找映射vectorintresult;for(intx:nums){intposlower_bound(tmp.begin(),tmp.end(),x)-tmp.begin();result.push_back(pos);// 或 pos1 如果要从1开始}returnresult;}方法二使用map自动排序和去重vectorintfun(vectorintnums){vectorinttmpnums;sort(tmp.begin(),tmp.end());tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());unordered_mapint,intm;for(inti0;itmp.size();i){m[tmp[i]]i;}vectorintresult;for(intx:nums){result.push_back(m[x]);}returnresult;}4. 研究案例题目背景曹操平定北方以后公元 208 年率领大军南下进攻刘表。他的人马还没有到荆州刘表已经病死。他的儿子刘琮听到曹军声势浩大吓破了胆先派人求降了。孙权任命周瑜为都督拨给他三万水军叫他同刘备协力抵抗曹操。隆冬的十一月天气突然回暖刮起了东南风。没想到东吴船队离开北岸大约二里距离前面十条大船突然同时起火。火借风势风助火威。十条火船好比十条火龙一样闯进曹军水寨。那里的船舰都挤在一起又躲不开很快地都烧起来。一眨眼工夫已经烧成一片火海。曹操气急败坏的把你找来要你钻入火海把连环线上着火的船只的长度统计出来题目描述给定每个起火部分的起点和终点请你求出燃烧位置的长度之和。输入格式第一行一个整数表示起火的信息条数n nn。接下来n nn行每行两个整数a , b a, ba,b表示一个着火位置的起点和终点注意左闭右开。输出格式输出一行一个整数表示答案。输入样例 13 -1 1 5 11 2 9输出样例 111数据规模与约定对于全部的测试点保证1 ≤ n ≤ 2 × 10 4 1 \leq n \leq 2 \times 10^41≤n≤2×104− 2 31 ≤ a b 2 31 -2^{31} \leq a b \lt 2^{31}−231≤ab231且答案小于2 31 2^{31}231。思路分析这道题的核心是区间合并问题。给定多个区间左闭右开需要计算这些区间覆盖的总长度重叠部分只计算一次。解题思路离散化由于坐标范围很大− 2 31 到 2 31 -2^{31}到2^{31}−231到231直接开数组会内存溢出所以需要将坐标离散化标记覆盖将每个区间映射到离散化后的坐标上标记被覆盖的区间段计算总长遍历所有离散化后的区间段累加被标记的区间长度具体步骤读入所有区间收集所有端点值对端点进行排序并去重离散化将每个原始区间映射到离散化后的下标范围用布尔数组标记每个离散化区间段是否被覆盖累加所有被标记的区间段的长度代码实现#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义区间对类型intn;intmain(){cinn;vectorPIIsegs;// 存储原始区间vectorintalls;// 存储所有端点用于离散化// 读入数据并收集所有端点for(inti1;in;i){inta,b;cinab;segs.push_back({a,b});// 存储原始区间alls.push_back(a);// 收集左端点alls.push_back(b);// 收集右端点}// 离散化处理sort(alls.begin(),alls.end());// 对所有端点排序// 去重unique返回去重后的尾迭代器alls.erase(unique(alls.begin(),alls.end()),alls.end());// c数组标记离散化后的区间段是否被覆盖// 每个区间段对应alls中相邻两个端点之间的部分vectorboolc(alls.size()-1,false);// 处理每个原始区间标记覆盖的区间段for(autoseg:segs){// 使用二分查找找到端点在离散化数组中的位置intllower_bound(alls.begin(),alls.end(),seg.first)-alls.begin();intrlower_bound(alls.begin(),alls.end(),seg.second)-alls.begin();// 标记[l, r)之间的所有区间段为已覆盖// 注意这里是ir因为是左闭右开区间for(intil;ir;i){c[i]true;}}// 计算总长度longlongans0;for(inti0;ic.size();i){if(c[i]){// 如果第i个区间段被覆盖累加其长度// 长度 alls[i1] - alls[i]ans(alls[i1]-alls[i]);}}coutansendl;return0;}功能分析1. 数据结构设计segs: 存储原始的起火区间alls: 存储所有端点坐标用于离散化c: 布尔数组标记离散化后的每个小区间是否被覆盖2. 核心算法流程离散化阶段将所有端点排序、去重将无限空间映射到有限下标区间映射阶段将每个原始区间[a,b)映射到离散化后的下标范围[l,r)标记阶段标记所有被覆盖的离散化区间计算阶段累加被标记区间的实际长度3. 关键点说明离散化必要性坐标范围达到2^31直接开数组会MLE二分查找优化lower_bound在有序数组中快速定位坐标区间处理注意题目是左闭右开区间循环条件为ir长度计算离散化后每个区间段长度需要还原为原始坐标差4. 复杂度分析时间复杂度O(n log n)主要开销在排序和二分查找空间复杂度O(n)存储端点数组和标记数组5. 示例解释对于输入3 -1 1 5 11 2 9处理过程所有端点-1, 1, 5, 11, 2, 9 → 排序去重后-1, 1, 2, 5, 9, 11离散化区间段[-1,1), [1,2), [2,5), [5,9), [9,11)标记覆盖[-1,1) → 覆盖[5,11) → 覆盖[5,9)和[9,11)[2,9) → 覆盖[2,5)和[5,9)总长度(-1到1) (2到5) (5到9) (9到11) 2 3 4 2 115. 离散化的注意事项要点总结保持顺序离散化后要保持原始数据的大小关系去重是必须的相同的值应该映射到同一个离散值边界处理考虑是从0开始还是从1开始树状数组通常从1开始内存管理离散化数组大小 不同元素的个数查询效率使用二分查找 O(logn)常见错误// 错误忘记去重sort(alls.begin(),alls.end());// 缺少alls.erase(unique(alls.begin(), alls.end()), alls.end());// 错误二分查找写错// 正确应该是 lower_bound不是 upper_bound6. 离散化的时间复杂度分析步骤时间复杂度说明排序O(nlogn)主要开销去重O(n)线性扫描映射O(nlogn)n次二分查找总计O(nlogn)通常可以接受7. 练习题推荐基础练习统计每个数出现的次数数据范围大区间和查询AcWing 802进阶练习求逆序对数量配合树状数组扫描线问题矩形面积并数星星问题二维偏序8. 模板代码// 离散化通用模板classDiscretizer{private:vectorintvals;public:voidadd(intx){vals.push_back(x);}voiddiscretize(){sort(vals.begin(),vals.end());vals.erase(unique(vals.begin(),vals.end()),vals.end());}intget_id(intx){returnlower_bound(vals.begin(),vals.end(),x)-vals.begin()1;}intsize(){returnvals.size();}};总结离散化是信奥赛中的重要技巧主要用于处理大数据范围但数据量小的问题将数据映射到连续区间便于使用数组等数据结构与树状数组、线段树等结合解决统计问题掌握离散化的关键在于理解其保持顺序、压缩空间的核心思想并熟练运用排序、去重、二分查找这三个基本操作。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、csp高频考点知识详解及案例实践CSP信奥赛C之动态规划CSP信奥赛C之标准模板库STL信奥赛C提高组csp-s知识详解及案例实践四、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}