最新要闻
- 【独家焦点】预算3000元 找老鸟装了台12代U ITX小主机:这配置你看如何?
- 天天视讯!AMD最强核显跑分逆天!竟然逼平GTX 1650、RX 480
- 热点在线丨女演员被困五星级酒店厕所超3小时!酒店回应:属于特例
- 头条焦点:《速度与激情10》新海报发布:范迪塞尔携众家人再度狂飙
- 深圳带奶茶跑腿回港火了:一趟就能赚数百元
- 丙二醇的功效_丙二醇的功效与作用
- 每日简讯:《碟中谍7:致命清算》首张海报:阿汤哥悬崖飞车冲上云霄!
- 【快播报】CPU突然变慢、Adobe异常崩溃:NVIDIA终于出手
- 【天天播资讯】动物园棕熊能懂人话 被质疑是人假扮:回应确实是真熊
- 天天速看:深圳居住登记信息服务_深圳市居住登记服务平台
- 焦点播报:游客为拍照不听劝阻喂狐狸吃面包 无视劝阻!会危害动物
- 播报:院线票房止步9000万:《中国乒乓》官宣3月17日登陆线上平台
- 华硕发布新款迷你主机:高配i7-13700H、配备雷电4
- 网传梅西要来 黄牛提前卖票!阿根廷国家足球队辟谣“中国行”
- 【新要闻】315白皮书:价格刺客成消费者年度最关注现象、购物平台为年度被投诉最多行业
- 环球时讯:西安机场为首次坐飞机旅客安排指引服务:佩戴专属手环 全程有人引导
广告
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
全球观焦点:算法模板总结 1
【资料图】
算法模板总结
1. 基础算法
1.1 快速排序
void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r);}
1.2 归并排序
void merge_sort(int q[], int l, int r){ if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];}
1.3 整数二分
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:int bsearch_1(int l, int r){ while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l;}// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:int bsearch_2(int l, int r){ while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l;}
1.4 浮点数二分
bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r){ const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l;}
1.5 高精度加法
// C = A + B, A >= 0, B >= 0vector add(vector &A, vector &B){ if (A.size() < B.size()) return add(B, A); vector C; int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C;}
1.6 高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0vector sub(vector &A, vector &B){ vector C; for (int i = 0, t = 0; i < A.size(); i ++ ) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C;}
1.7 高精度乘低精度
// C = A * b, A >= 0, b >= 0vector mul(vector &A, int b){ vector C; int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C;}
1.8 高精度除以低精度
// A / b = C ... r, A >= 0, b > 0vector div(vector &A, int b, int &r){ vector C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C;}
1.9 一维前缀和
S[i] = a[1] + a[2] + ... a[i]a[l] + ... + a[r] = S[r] - S[l - 1]
1.10 二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
1.11 一维差分
// 给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c // 生成一维差分矩阵,要注意下标从0开始还是从1开始void insert(int l, int r, int c){ b[l] += c; b[r + 1] -= c;}for (int i = 1; i <= n; i ++ ){ insert(i, i, a[i]);}
1.12 二维差分
// 给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:// S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c // 生成二维差分矩阵,要注意下标从0开始还是从1开始void insert(int x1, int y1, int x2, int y2, int c){ b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c;}for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) insert(i, j, i, j, a[i][j]);
注:差分和前缀和互逆
1.13 位运算
求n的第k位数字: n >> k & 1返回n的最后一位1和之后的0组成的数字:lowbit(n) = n & -n;lowbit(101) = 1;lowbit(1100) = 4;
1.14 双指针算法
for (int i = 0, j = 0; i < n; i ++ ){ while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑}常见问题分类: (1) 对于一个序列,用两个指针维护一段区间 (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
1.15 离散化
vector alls; // 存储所有待离散化的值sort(alls.begin(), alls.end()); // 将所有值排序alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素// 二分求出x对应的离散化的值int find(int x) // 找到第一个大于等于x的位置{ int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n}
关键词:
如何用好免费的chatGPT
全球观焦点:算法模板总结 1
【独家焦点】预算3000元 找老鸟装了台12代U ITX小主机:这配置你看如何?
天天视讯!AMD最强核显跑分逆天!竟然逼平GTX 1650、RX 480
热点在线丨女演员被困五星级酒店厕所超3小时!酒店回应:属于特例
头条焦点:《速度与激情10》新海报发布:范迪塞尔携众家人再度狂飙
深圳带奶茶跑腿回港火了:一趟就能赚数百元
丙二醇的功效_丙二醇的功效与作用
今日热讯:《consul 简易上手指南》
每日简讯:《碟中谍7:致命清算》首张海报:阿汤哥悬崖飞车冲上云霄!
【快播报】CPU突然变慢、Adobe异常崩溃:NVIDIA终于出手
【天天播资讯】动物园棕熊能懂人话 被质疑是人假扮:回应确实是真熊
第三十一天 面向对象编程的基础
每日观点:c++11多线程入门<学习记录>
当前通讯!day03-分析SpringBoot底层机制
关于AWS-S3-Bucket-Console-Web控制页面上的Creation date与命令行-API方式如何获取到真正的CreationDate
天天速看:深圳居住登记信息服务_深圳市居住登记服务平台
焦点播报:游客为拍照不听劝阻喂狐狸吃面包 无视劝阻!会危害动物
Vue——mergeOptions【四】
播报:院线票房止步9000万:《中国乒乓》官宣3月17日登陆线上平台
华硕发布新款迷你主机:高配i7-13700H、配备雷电4
环球热点评!.NET中比肩System.Text.Json序列化反序列化组件MessagePack
路飞-项目上线
今亮点!分布式架构-可观测性-事件日志
【全球热闻】教你用Python画个可爱的皮卡丘!(附完整源码)
每日资讯:Educational Codeforces Round 123 (Rated for Div. 2)
网传梅西要来 黄牛提前卖票!阿根廷国家足球队辟谣“中国行”
【新要闻】315白皮书:价格刺客成消费者年度最关注现象、购物平台为年度被投诉最多行业
环球时讯:西安机场为首次坐飞机旅客安排指引服务:佩戴专属手环 全程有人引导
速度10倍于普通U盘!联想小新原厂颗粒固态U盘发售:USB 3.2双口
12万买C6?想多了!雪铁龙都是套路:想提车先交29万
记录--你不知道的forEach函数
智能勘探 | AIRIOT智慧油田管理解决方案
环球聚焦:NOI春季测试游记
微贺卡
《黑暗荣耀2》热播!演员透露拍摄细节:剧里的蛇是真蛇
82版《西游记》编剧戴英禄逝世 六小龄童发文悼念
当前关注:理想汽车L8首批车主调研:300名中车主开BBA的最多
环球播报:国产车崛起 豪华车丝毫不怂:市场份额继续增 有钱人多
最新资讯:努比亚Z50 Ultra首销卖爆:获京东/天猫平台销量销售额冠军
报道:第一章 软件工程概述
每日看点!centos7.9离线升级openssl和openssh9.2
python语言基础
每日焦点!Mysql数据库未添加索引引发的生产事故
对极几何的理解和原理推导
卡塔尔世界杯官方授权:富光1.5L顿顿桶29元发车
焦点精选!零碳排放!我国首款双源智能重卡成功下线:自带大辫子
视焦点讯!全球打广告最划算的一块屏?登上纽约时代广场屏幕只需40美元
《狂飙》后 张译宣传新剧《他是谁》:今晚优酷、央视开播
获赔近100万 报废奔驰翻新再销售被判退1赔3 网友:C级秒变大S
每日快讯!10Wqps 超高并发 API网关 架构演进之路
Egg.js 学习笔记01
世界快看:git提交规范
【全球速看料】早起、冥想、阅读、写作、运动
焦点讯息:观察者模式——学习笔记
天天最新:dnf游戏闪退怎么解决方法_dnf游戏闪退
停车场闸机防骗能力太弱鸡:博主实测一部手机、一张纸均可通行
曾模仿东方甄选直播带货 好未来旗下学而思大规模重启线下招生
白皮书:购物平台为2022年度消费者投诉最多的行业
天天播报:315前海鲜加工厂的狠活被曝光:硼砂泡出黄金鲍 系明令禁止食品添加剂
世界焦点!两只售价3899元:华硕ROG推出魔方幻路由器月曜白限定版
卷起来!!!看了这篇文章我才知道MySQL事务&MVCC到底是啥?
蓝牙Mesh简介(一)设备标识:UUID和Mesh地址
开源免费:分享powershell读写k8s的etcd的脚本库
环球速递!冲击全球的“硅谷银行破产”到底咋回事?会不会引爆危机?
视点!国产AYA新掌机Ayaneo 2 IGN9分好评:价格贵 但很好用!
【聚看点】央视3·15晚会官宣明晚举办 这次谁会被曝光?
世界最资讯丨配置大升级!新款比亚迪唐DM-i/汉EV冰川蓝实车亮相:绝对吸睛
上海测试9辆自动驾驶清扫车 可替代25名环卫工人
干货来袭!3天0基础Python实战项目快速学会人工智能必学数学基础全套(含源码)(第3天)概率分析篇:条件概率、全概率与贝叶斯公式
韩国电视台剪掉杨紫琼获奖感言:鼓励女性部分没了
腾讯会议重大调整!取消免费300人不限时会议使用
世界看热讯:斥资10亿美元!NASA将开发太空拖船:实现国际空间站受控坠落
那些曾被315点过名的品牌怎么样了?英菲尼迪道歉并更换变速箱 汉堡王被罚
实时焦点:车圈大V杨学良晒魅族20 Pro真机:极简设计 好看又好用!
与微软聊天机器人对话
Vue项目迁移小程序,实操干货分享
戴尔PC要100%离开中国!完整时间表曝光:真着急
天天微资讯!韩媒称特斯拉停止与比亚迪合作 马斯克:虚假报道、双方关系积极
魔兽世界将推出全新硬核玩法:一命通关、挂了就得重来
ai文件怎么打开?ai文件用什么软件打开和编辑?
斐讯k1支持千兆吗?斐讯k1路由器怎么设置?
windows如何一键还原?windows截图保存在哪里?
声卡怎么调试?声卡什么牌子的音质比较好?
笔记本fn键在哪里?fn键怎么开启和关闭?
每日短讯:可插拔组件设计机制—SPI
今日热讯:Vim 备忘清单_开发速查表分享
世界头条:Linux进程的创建与销毁
鲨鱼求偶被误认吃“同事” 官方回应:是繁殖行为 撕咬有分寸
天天热文:减肥不吃主食?医生提醒:可致大脑功能衰退
全球热消息:《小丑2》Lady Gaga小丑女新片场照 造型太好看了
全球报道:极速直追中国高铁!碳陶瓷刹车套件特斯拉Model S Plaid打破单圈纪录
【全球报资讯】一键开盖:哈尔斯600ml水杯9.9元狂促 Tritan材质款23.9元
天天热头条丨阳高县气象台发布大风蓝色预警【Ⅳ级/一般】
全球微头条丨java操作excel文件——POI
天天讯息:剑指 Offer 68 - II. 二叉树的最近公共祖先(java解题)
分布式架构-可观测性
obs studio 插件
看热讯:小米子公司发通告:拼多多、京东、淘宝上的“紫米官旗”不是我
硅谷银行停业没影响!贾跃亭要“翻身”:4月26日FF91终极发布