XP02杭州营Day1笔记
2025-08-02 20:50:27
发布于:浙江
1、枚举算法
1、枚举所有情况
2、判断每种情况是否符合条件
2、贪心算法
1、贪
排序
bool cmp(int x,int y){
return x>y; // > 从大到小; < 从小到大
}
sort(a+1,a+n+1); // 从小到大
sort(a+1,a+n+1,greater<int>()); // 从大到小
sort(a+1,a+n+1,cmp); // 从大到小
3、前缀和
定义: s[i]: 原数组 a 的前 i 个数(1 ~ i)的和
预处理: s[i] = s[i-1] + a[i]
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
应用: 求区间 [L,R] 的区间和 sum(L,R)
sum(L,R) = s[R] - s[L-1];
用在有 多次 查询 区间和 的问题 O(1)
4、差分
定义: d[i]: 原数组 a 的相邻两项元素的差值
预处理: d[i] = a[i] - a[i-1];
for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
应用: 对原数组 a 区间 [L,R] 每个数加上 c
d[L]+=c;
d[R+1]-=c;
直接对原数组 a 进行修改, 一次修改 时间复杂度 O(n);
间接对差分数组 d 进行修改, 一次修改 时间复杂度 O(1),
再通过对差分数组求前缀和得到修改后的原数组了 O(n);
用在有 多次 区间修改 的问题
5、原 前 差的转换
全部评论 1
跪求点赞
2小时前 来自 浙江
0
有帮助,赞一个