男科医院网站建设策略,网站建设中的定位设想,给公司网站设计,惠州百度seo地址✨博主#xff1a;命运之光 ✨专栏#xff1a;算法基础学习 目录
✨前缀和
✨一维前缀和
#x1f353;一维前缀和模板#xff1a;
✨二维前缀和
#x1f353;二位前缀和模板#xff1a; 前言#xff1a;算法学习笔记记录日常分享#xff0c;需要的看哈O(∩_∩)O命运之光 ✨专栏算法基础学习 目录
✨前缀和
✨一维前缀和
一维前缀和模板
✨二维前缀和
二位前缀和模板 前言算法学习笔记记录日常分享需要的看哈O(∩_∩)O感谢大家的支持 ✨前缀和
✨一维前缀和
原ia[1] a[2] a[3] …a[n]
前缀和s[i]a[1]a[2]…a[i] s[0]0(方便处理边界问题 注下标一定从1开始 1.如何求s[i]:
for(i1;in;j)s[i]s[i-1]a[i]
2.作用快O(1)
快速求出原数组里一段数的和 一维前缀和模板
S[i] a[1] a[2] ... a[i]a[l] ... a[r] S[r] -S[l -1]
✨二维前缀和 二位前缀和模板
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] ✨差分 差分实际是前缀和的逆运算 ✨一维差分 一维差分模板
给区间[l, r]中的每个数加上cB[l] c, B[r 1] - c ✨二维差分 二维差分模板
给以(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 ✨双指针
双指针算法的核心思想
for(int i0;in;i)
for(int j0;jn;j) O(n^2)
将上面的朴素算法优化到O(n) 双指针模板
for (int i 0, j 0; i n; i )
{while (j i check(i, j)) j ;// 具体问题的逻辑
}
常见问题分类
(1) 对于一个序列用两个指针维护一段区间
(2) 对于两个序列维护某种次序比如归并排序中合并两个有序序列的操作
例题统计日志
#include iostream
#include algorithm
using namespace std;
const int N1000005;
typedef struct Log{
int ts,id;
}Log;
Log logs[N];
//(tk-D,tk]
int n,d,k;
int cnt[N];//cnt[i]始终存储的是连续d分钟内idi的帖子的点赞量
bool rt[N];
bool cmp(Log qian,Log hou){if(qian.tshou.ts)return true;return false;
}
int main(){scanf(%d%d%d,n,d,k);int m0;for(int i1;in;i){scanf(%d%d,logs[i].ts,logs[i].id);mmax(m,logs[i].id);}sort(logs1,logsn1,cmp); for(int i1,j1;in;i){//i和j始终维护长度小于d的区间 cnt[logs[i].id]; while(logs[i].ts-logs[j].tsd){cnt[logs[j].id]--;j;}if(cnt[logs[i].id]k){rt[logs[i].id]true;}}for(int i0;im;i){if(rt[i]true)printf(%d\n,i);}
}
例题统计子矩阵
#include iostream
using namespace std;
const int N510;
int n,m,k;
int s[N][N];
int main(){cinnmk;for(int i1;in;i){for(int j1;jm;j){cins[i][j];s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]s[i][j];}}long long ans0;for(int l1;lm;l){for(int rl;rm;r){for(int d1,u1;dn;d){while(ud(s[d][r]-s[d][l-1]-s[u-1][r]s[u-1][l-1]k))u;if(ud)ansd-u1;}}}coutansendl;
}
✨位运算
✨操作一
n的二进制中第k位是几 1.先把第k位移到最后一位nk
2.看个位是几x1 十进制转化成二进制、八进制、十六进制连除法 二进制、八进制、十六进制转化成十进制 关于原码反码补码
原码、反码和补码是计算机中用来表示带符号整数的三种编码方式。
1. 原码Sign-Magnitude
原码是最简单的表示方法将一个整数按照正负号和数值进行编码。具体规则如下
正数的原码是其二进制表示形式。负数的原码是将对应的正数的原码最高位改为1。
例如假设用8位二进制表示整数数字3的原码是00000011数字-3的原码是10000011。
2. 反码Ones Complement
反码是在原码的基础上将负数的表示方式进行改进。具体规则如下
正数的反码与其原码相同。负数的反码是将对应的正数的原码按位取反即将0变为1将1变为0。
例如数字3的反码是00000011数字-3的反码是11111100。
3. 补码Twos Complement
补码是在反码的基础上进行改进是计算机中最常用的表示方式。具体规则如下
正数的补码与其原码相同。负数的补码是将对应的正数的原码按位取反然后再加1。
例如数字3的补码是00000011数字-3的补码是11111101。
补码的使用在计算机中具有以下好处
可以统一处理正数和负数的加减运算无需单独处理符号位。补码只有一个表示零的编码避免了正零和负零的问题。补码的表示范围比原码和反码更广能够表示的最大正整数比较大。 需要注意的是在使用补码表示的计算机系统中最高位通常被用作符号位即0表示正数1表示负数。这种表示方式使得补码能够直接进行加减运算并且可以方便地检测结果的正负。
