广州好蜘蛛网站建设,seo托管服务,织梦网站首页幻灯片不显示,个人电子邮箱怎么注册前缀和与差分 文章目录前缀和与差分应用总结前缀和截断数组思路代码最大加权矩形题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码差分海底高铁题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码改变数组元素思路代码应用总结 前缀和用来…前缀和与差分 文章目录前缀和与差分应用总结前缀和截断数组思路代码最大加权矩形题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码差分海底高铁题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码改变数组元素思路代码应用总结 前缀和用来查询一段区间的和。 具体应用有求最大子段和求二维矩阵规定长度的子矩阵和对于没有规定具体长度的子矩阵和可以通过前缀和压缩 差分 对一段区间的操作转换为对首尾差值的加减。 应用于对一段区间整体操作与前缀和相结合输出结果。
前缀和
截断数组
给定一个长度为 n 的数组 a1,a2,…,an 。
现在要将该数组从中间截断得到三个非空子数组。
要求三个子数组内各元素之和都相等。
请问共有多少种不同的截断方法
输入格式 第一行包含整数 n 。
第二行包含 n 个整数 a1,a2,…,an 。
输出格式 输出一个整数表示截断方法数量。
数据范围 前六个测试点满足 1≤n≤10 。 所有测试点满足 1≤n≤105 −10000≤ai≤10000 。
输入样例1 4 1 2 3 3 输出样例1 1 输入样例2 5 1 2 3 4 5 输出样例2 0 输入样例3 2 0 0 输出样例3 0
思路
将数组分为等和的三段对应于前缀和就是找到公差设为aveaveave为总和三分之一的前缀和数组等差数列。 公差相等三段前缀和的特征为第一段为aveaveave第二段为2ave2ave2ave第三段为3ave3ave3ave。记录所有可能第一段的个数当遍历到可能第二段时用第一段数量更新数量因为第一段和第二段确定后第三段也相应确定所以第三段可以不管他。
代码
N 100010a [0] * N
n int(input())a[1 : n 1] list(map(int, input().split()))for i in range(1, n 1) : # 计算前缀和a[i] a[i - 1]if a[n] % 3 or n 3 : # 当元素个数小于3或者和不是3的倍数时肯定无法分组print(0)
else :ave a[n] // 3 # 公差ans, cnt 0, 0for i in range(2, n) :if a[i - 1] ave : cnt 1 # 记录第一段个数if a[i] 2 * ave : ans cnt # 遇见每个第二段时都能确定分段方法print(ans)最大加权矩形
题目描述
为了更好的备战 NOIP2013电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为我们不光需要机房我们还需要运动于是就决定找校长申请一块电脑组的课余运动场地听说她们都是电脑组的高手校长没有马上答应他们而是先给她们出了一道数学题并且告诉她们你们能获得的运动场地的面积就是你们能找到的这个最大的数字。
校长先给他们一个 n×nn\times nn×n 矩阵。要求矩阵中最大加权矩形即矩阵的每一个元素都有一权值权值定义在整数集上。从中找一矩形矩形大小无限制是其中包含的所有元素的和最大 。矩阵的每个元素属于 [−127,127][-127,127][−127,127] ,例如 0 –2 –7 0 9 2 –6 2
-4 1 –4 1
-1 8 0 –2在左下角
9 2
-4 1
-1 8和为 151515。
几个女孩子有点犯难了于是就找到了电脑组精打细算的 HZHTZY 小朋友帮忙计算但是遗憾的是他们的答案都不一样涉及土地的事情我们可不能含糊你能帮忙计算出校长所给的矩形中加权和最大的矩形吗
输入格式
第一行nnn接下来是 nnn 行 nnn 列的矩阵。
输出格式
最大矩形子矩阵的和。
样例 #1
样例输入 #1
4
0 -2 -7 09 2 -6 2
-4 1 -4 1
-1 8 0 -2样例输出 #1
15提示
1≤n≤1201 \leq n\le 1201≤n≤120
思路
求最大子矩阵和让人想到了最大子段和然而矩阵是在二维进行操作。因此需要将矩阵进行压缩我们选择对行进行压缩对连续的行之间可以看成是一行通过组合的形式可以考虑到所有情况。组合通过前缀和来进行实现。
代码
N 130
a [[0] * N for _ in range(N)]n int(input())for i in range(1, n 1) :a[i][1 : n 1] list(map(int, input().split()))# 计算二维前缀和
for i in range(1, n 1) :for j in range(1, n 1) :a[i][j] a[i - 1][j] a[i][j - 1] -a[i - 1][j - 1]
# 进行矩阵压缩和求最大子段和
ans -1000010
for i in range(1, n 1) :for j in range(1, i 1) : # 从包含1行到包含i行f [0] * (n 1)minn 0for k in range(1, n 1) :f[k] a[i][k] - a[i - j][k]ans max(ans, f[k] - minn)minn min(minn, f[k])
print(ans) 差分
海底高铁
题目描述
该铁路经过 NNN 个城市每个城市都有一个站。不过由于各个城市之间不能协调好于是乘车每经过两个相邻的城市之间方向不限必须单独购买这一小段的车票。第 iii 段铁路连接了城市 iii 和城市 i1(1≤iN)i1(1\leq iN)i1(1≤iN)。如果搭乘的比较远需要购买多张车票。第 iii 段铁路购买纸质单程票需要 AiA_iAi 博艾元。
虽然一些事情没有协调好各段铁路公司也为了方便乘客推出了 IC 卡。对于第 iii 段铁路需要花 CiC_iCi 博艾元的工本费购买一张 IC 卡然后乘坐这段铁路一次就只要扣 Bi(BiAi)B_i(B_iA_i)Bi(BiAi) 元。IC 卡可以提前购买有钱就可以从网上买得到而不需要亲自去对应的城市购买。工本费不能退也不能购买车票。每张卡都可以充值任意数额。对于第 iii 段铁路的 IC 卡无法乘坐别的铁路的车。
Uim 现在需要出差要去 MMM 个城市从城市 P1P_1P1 出发分别按照 P1,P2,P3,⋯,PMP_1,P_2,P_3,\cdots,P_MP1,P2,P3,⋯,PM 的顺序访问各个城市可能会多次访问一个城市且相邻访问的城市位置不一定相邻而且不会是同一个城市。
现在他希望知道出差结束后至少会花掉多少的钱包括购买纸质车票、买卡和充值的总费用。
输入格式
第一行两个整数N,MN,MN,M。
接下来一行MMM 个数字表示 PiP_iPi。
接下来 N−1N-1N−1 行表示第 iii 段铁路的 Ai,Bi,CiA_i,B_i,C_iAi,Bi,Ci。
输出格式
一个整数表示最少花费
样例 #1
样例输入 #1
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10样例输出 #1
6394提示
222 到 333 以及 888 到 999 买票其余买卡。
对于 30%30\%30% 数据 M2M2M2。
对于另外 30%30\%30% 数据 N≤1000M≤1000N\leq1000M\leq1000N≤1000M≤1000。
对于 100%100\%100% 的数据 M,N≤105Ai,Bi,Ci≤105M,N\leq 10^5A_i,B_i,C_i\le10^5M,N≤105Ai,Bi,Ci≤105。
思路
由于每个城市只有一段路可以到达而每段路都需要买相应的车票或者使用IC卡。每段路互不相干这样对于费用的计算只需要知道每一段路经过次数。由于出差每次访问城市可能不是相邻的所以对于每次的访问需要改变所有途经的路径这就可以使用差分来记录了。
代码
N 100010
a [0] * N
f [0] * N
n, m map(int, input().split())a[1 : m 1] list(map(int, input().split()))# 计算差分,路径按照小的城市号规定
for i in range(2, m 1) :x, y a[i - 1], a[i]f[min(x, y)] 1f[max(x, y)] - 1
# 计算前缀和
for i in range(1, n) :f[i] f[i - 1]
res 0
for i in range(1, n) :x, y, z map(int, input().split())res min(x * f[i], z y * f[i])
print(res)改变数组元素
给定一个空数组 V 和一个整数数组 a1,a2,…,an 。
现在要对数组 V 进行 n 次操作。
第 i 次操作的具体流程如下
从数组 V 尾部插入整数 0 。 将位于数组 V 末尾的 ai 个元素都变为 1 已经是 1 的不予理会。 注意
ai 可能为 0 即不做任何改变。 ai 可能大于目前数组 V 所包含的元素个数此时视为将数组内所有元素变为 1 。 请你输出所有操作完成后的数组 V 。
输入格式 第一行包含整数 T 表示共有 T 组测试数据。
每组数据第一行包含整数 n 。
第二行包含 n 个整数 a1,a2,…,an 。
输出格式 每组数据输出一行结果表示所有操作完成后的数组 V 数组内元素之间用空格隔开。
数据范围 1≤T≤20000 , 1≤n≤2×105 , 0≤ai≤n , 保证一个测试点内所有 n 的和不超过 2×105 。
输入样例 3 6 0 3 0 0 1 3 10 0 0 0 1 0 5 0 0 0 2 3 0 0 0 输出样例 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0
思路
每次操作都是将一段区间进行操作很显然用差分的做法。在进行前缀和后只需要判断是否为0即可判断是否被操作过。
代码 0代表未操作
其他数字ai代表将本位置起的ai个元素全部变为1
差分是对一段区间进行一次性操作我们只需要统一区间操作的情况下
进行操作比如如果有操作则统一1,那么只要差分后的前缀和不是0则证明被变为1过
T int(input())for _ in range(T) :n int(input())a [0] * (n 2)f [0] * (n 2)f[1 : n 1] list(map(int, input().split()))for i in range(1, n 1) :if f[i] :if f[i] i :a[1] 1else :a[i - f[i] 1] 1a[i 1] - 1for i in range(1, n 1) :a[i] a[i - 1]if a[i] ! 0 :print(1, end )else : print(0, end )print()
