对于一个给定的数列
,它的前缀和数列
是通过递推能求出的基本信息之一:
前缀和的作用
一个部分和,即数列
某个下标区间内的数的和,可表示为前缀和相减的形式
对于多维空间,同样可以定义前缀和,求部分和配合 容斥原理 即可实现
具体“容斥原理”会在数论章节讲解
例如 二维前缀和:
对于一个给定的数列
,它的差分数列
定义为:
差分的作用
“前缀和” 与 “差分” 互为逆运算:
的前缀和序列就是原序列
;
的差分序列也是原序列
;
把序列
的区间
加
(即把
都加上
),其差分序列
的变化为:
这有助于我们把原序列的 “区间操作” 转化为差分序列上的 “单点操作” 进行计算,从而降低求解难度
差分也可以在树上进行运用,会在图的章节进行讲解
地图上有
个目标,用整数
表示目标在地图上的位置,每个目标都有一个价值
。
注意:不同目标可能在同一位置。
现在有一种新型的激光炸弹,可以摧毁一个包含
个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和
,
轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数
和
,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来
行,每行输入一组数据,每组数据包括三个整数
,
,
,分别代表目标的
坐标,
坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
,
,
,
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
二维前缀和
值得注意的一点,虽然“目标”位于网格线的交点,而我们的前缀和是以方格为单位累加的
因此我们不妨把“目标”统一偏移到网格的方格中:
且偏移后,新问题与原问题等价,并且新边界变得更好处理
for (int i = 1; i < N; i ++ )
for (int j = 1; j < N; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
for (int i = m; i < N; i ++ )
for (int j = m; j < N; j ++ )
res = max(res, s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m]);
给定一个长度为
的数列
,每次可以选择一个区间
,使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行输入正整数
。
接下来
行,每行输入一个整数,第
行的整数代表
。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
,
输入样例:
4
1
1
2
2
输出样例:
1
2
一维差分
区间修改,联想到用差分数组来维护,最终目标是使差分数组 除首元素外全为 0
每次修改一个区间,对于维护的差分数组变化情况分类:
:b[l] -- , b[r + 1] ++
或 b[l] ++ , b[r + 1] --
:b[1] -- , b[r + 1] ++
或 b[1] ++ , b[r + 1] --
:b[l] --
或 b[l] ++
:b[1] --
或 b[1] ++
(多余操作)
观察易得:
为了让操作次数尽可能少,应尽可能使用操作 1
因此不妨设
中正数总和为
,
中负数总和为
然后让正负数配对,尽量执行操作 1,执行次数为
剩余
个要么全是正数,要么全是负数,调用操作 2 或操作 3 都可,执行次数为
次
由于每次调用操作 2 时会改变一次首元素的值,因此首元素的可能值就有
种可能
因此最终答案为:
和
long long p = 0, q = 0;
for (int i = 2; i <= n; i ++ )
{
if (b[i] > 0) p += b[i];
else if (b[i] < 0) q -= b[i];
}
cout << max(p, q) << endl << abs(p - q) + 1 << endl;
有
头牛站成一行,被编队为
,每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。
现在,我们只知道其中最高的牛是第
头,它的身高是
,剩余牛的身高未知。
但是,我们还知道这群牛之中存在着
对关系,每对关系都指明了某两头牛
和
可以相互看见。
求每头牛的身高的最大可能值是多少。
输入格式
第一行输入整数
,数据用空格隔开。
接下来
行,每行输出两个整数
和
,代表牛
和牛
可以相互看见,数据用空格隔开。
输出格式
一共输出
行数据,每行输出一个整数。
第
行输出的整数代表第
头牛可能的最大身高。
数据范围
,
,
,
输入样例:
9 3 5 5
1 3
5 3
4 3
3 7
9 8
输出样例:
5
4
5
3
4
4
5
5
5
注意: 此题中给出的关系对可能存在重复
我们希望每对牛之间可以相互看见,并且每头牛的高度最高
一开始不妨假设所有牛的高度都是给出的最高牛的高度
要使第
头牛与第
头牛可以互相看见,那么只需让区间
的牛高度减少 1 即可
可以直接用差分序列来维护原序列,则每次修改操作为:b[x + 1] -- , b[y] ++
int b[N];
set<PII> S;
int main()
{
cin >> n >> p >> h >> m; b[1] = h;
while (m -- )
{
int x, y;
cin >> x >> y;
if (x > y) swap(x, y);
if (S.count({x, y})) continue;
S.insert({x, y});
b[x + 1] -- , b[y] ++ ;
}
for (int i = 1; i <= n; i ++ )
{
b[i] = b[i - 1] + b[i];
cout << b[i] << endl;
}
return 0;
}