中国建设银银行招聘网站,帝国 网站搬家,南通大型网站建设,昆明营销型网站制作设计#x1f34e; 博客主页#xff1a;#x1f319;披星戴月的贾维斯 #x1f34e; 欢迎关注#xff1a;#x1f44d;点赞#x1f343;收藏#x1f525;留言 #x1f347;系列专栏#xff1a;#x1f319; 蓝桥杯 #x1f319;我与杀戮之中绽放#xff0c;亦如黎明的花… 博客主页披星戴月的贾维斯 欢迎关注点赞收藏留言 系列专栏 蓝桥杯 我与杀戮之中绽放亦如黎明的花朵 一起加油去追寻、去成为更好的自己 蓝桥杯倒计时 44天 文章目录、差分、例题分析、AcWing差分、AcWing差分矩阵、AcWing改变数组元素、总结提示以下是本篇文章正文内容下面案例可供参考 、差分
、差分的简单概念 差分在数学领域的理解有数列a1 a2 a3……an……其中an1 an d n 1,2,…n d为常数称为公差 即 d an1 -an , 这就是一个差分, 通常用D(an) an1- an来表示于是有D(an) d , 这是一个最简单形式的差分方程。 差分在计算机领域的理解差分是前缀和的逆运算差分的作用是在O(1)的时间复杂度下让一段区间例如是[i, n]区间内的每一个数都加或者减同一个数。 一维差分的公式s[L] c , s[R 1] - c; 其中L是区间的左端点R是区间的右端点。 二维差分的公式S[x1][y2] c; s[x1][y2 1] - c; S[x2 1] - c; s[x2 1][y2 1] c; 对于差分数组的理解原数组a[]是差分数组b[]的前缀和a[i] b[0] b[1] b[2] … b[i],所以在最后输出结果时一维差分公式a[i] a[i - 1] b[i]; 二维差分最后输出结果的公式是: a[i][j] a[i - 1][j] a[i][j - 1] b[i][j]
、图解一维前缀和 、图解二维前缀和 、例题分析
、AcWing差分
本题链接: 差分 简单分析题意就是在q次询问中每次在原数组的一段区间上加上一个值C最后输出q次询问后的结果。 代码示例
#includeiostream
using namespace std;
const int N 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c)
{b[l] c;b[r 1] - c;
}
int main ()
{cin n m;for(int i 1; i n; i){cin a[i];insert(i, i, a[i]);//对b[i]的初始化}while(m --){int l, r, c;cin l r c;insert(l, r, c);}for(int i 1; i n; i){a[i] a[i - 1] b[i];cout a[i] ;}cout endl;return 0;
}、AcWing差分矩阵
本题链接: 差分矩阵 简单分析题意就是在q次查询中每次在一个区间内加/减一个值。 代码示例
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 1010;
int b[N][N], a[N][N];
int n, m, q;
void add(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] c;b[x1][y2 1] - c;b[x2 1][y1] - c;b[x2 1][y2 1] c;
}
int main ()
{cin n m q;for(int i 1; i n; i)for(int j 1; j m; j){scanf(%d, a[i][j]);add(i, j, i, j, a[i][j]); // 每次输入一个a[i],就要初始化一下b差分数组}while(q --){int x1, y1, x2, y2, c;cin x1 y1 x2 y2 c;add(x1, y1, x2, y2, c);}for(int i 1; i n; i){for(int j 1; j m; j){a[i][j] a[i - 1][j] a[i][j - 1] - a[i - 1][j - 1] b[i][j];//这里使用二维前缀和公式printf(%d , a[i][j]);}puts();}return 0;
}、AcWing改变数组元素
本题链接: 改变数组元素 分析题意 代码示例
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N 200010;
int b[N];
int n;
int main ()
{int t;cin t;while(t --){scanf(%d, n);memset(b, 0, 4 * (n 1));for(int i 1; i n; i){int x;scanf(%d, x);x min(x, i);int l i - x 1, r i;//差分数组的左右两端b[l], b[r 1]--; //差分操作的模板} //求原数组就是差分数组的前缀和for(int i 1; i n; i){b[i] b[i - 1]; //差分和前缀和是互逆操作}for(int i 1; i n; i)printf(%d , !!b[i]); // 原来是0的还是0原来大于等于1的就变为1了。puts();}return 0;
}、总结 本文简要介绍了差分的简要概念和几道差分的经典例题希望大家读后能有所收获
