【蓝桥模板】——考试倒计时3天，你和省一就差这最后10分了（差分模板）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【蓝桥模板】——考试倒计时3天，你和省一就差这最后10分了（差分模板）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

大家好，我是爱分享的小蓝，欢迎交流指正~

蓝桥模板,备战蓝桥,python,蓝桥杯,算法,动态规划,数据结构

全文目录🧭

🎁差分模板

🌲差分-树木上药

🚀传送锚点

💡思路点拨

🍞代码详解

🎄差分-小明的彩灯

🚀传送锚点

💡思路点拨

🍞代码详解

🎁差分模板

差分三部曲=差分相减+转换加减+前缀相加

#差分三部曲

#1.差分相减(差分公式)
for i in range(len(dp)-1,0,-1):
    dp[i]-=dp[i-1]
#2.转换加减(区间加减→端点加减)
    dp[l-1]+=v  
    dp[r]-=v
#3.前缀相加(前缀和公式)
for i in range(1,n):
    dp[i]+=dp[i-1]

'''
dp=[1, 2, 3, 4, 5, 7, 2]+[0]

首先假设有一个数组：

1 2 3 4 5 7 2

差分后：
1 1 1 1 1 2 -5 -2

一般应用场景：
让你对区间 [l,r] 加减操作 N 次

如：
从第二个元素到第五个元素每个+3
从第二个元素到第四个元素每个-2
从第一个元素到第三个元素每个+1
....

这里我们先演示前三个：
对于每个 [l,r] 区间的加减操作都转化为对端点 l,r+1 的操作
从第二个元素到第五个元素每个+3：
转化为：[l]+3 并且 [r+1]-3

那么原序列变成了：
1 1 1 1 1 2 -5 -2
1 4 1 1 1 -1 -5 -2

然后我们按照 a[i]=a[i]+a[i-1] 复原：
1 5 6 7 8 7 2 0

去掉最后一项，跟原序列对比：
1 2 3 4 5 7 2
1 5 6 7 8 7 2
确实是都加上了 3。

我们继续操作：
从第二个元素到第四个元素每个-2
转化为：[l]-2 并且 [r+1]+2

那么序列变成了： 
1 4 1 1 1 -1 -5 -2
1 2 1 1 3 -1 -5 -2

然后我们按照a[i]=a[i]+a[i-1] 复原
1 3 4 5 8 7 2 0

与上次复原后对比：
1 5 6 7 8 7 2
1 3 4 5 8 7 2 


我们最后直接做三次，最后还原：
从第二个元素到第五个元素每个+3
从第二个元素到第四个元素每个-2
从第一个元素到第三个元素每个+1

1 2 3 4 5 7 2

原序列差分后：
2 2 1 0 3 -1 -5 -2

2 号元素 + 3 
6 号元素 - 3
2 号元素 - 2
5 号元素 + 2
1 号元素 + 1 
4 号元素 - 1

差分序列变成：
2 2 1 0 3 -1 -5 -2

复原后：
2 4 5 5 8 7 5 0

与原序列对比：
1 2 3 4 5 7 2
2 4 5 5 8 7 5

'''

参考资料：原理解释样例解释

🌲差分-树木上药

🚀传送锚点

蓝桥模板,备战蓝桥,python,蓝桥杯,算法,动态规划,数据结构

💡思路点拨

老规矩，先来一道差集的经典例题「树木上药」，熟悉一下差分三部曲~

1、差分相减：先创建一个dp列表，相隔两个元素相减。因为这道题dp列表初始化都为0，运算之后还是0不变，所以可以跳过第一步不写，写上是为了更好理解。

2、转换加减：区间的加减转换成两个端点的加减，左端点加上权值，右端点减去权值。

3、前缀相加：将第一步的差集用前缀和还原回去，这里用到之前学过的前缀和模板。

🍞代码详解

#差分-树木打药
n,m=map(int, input().split())
dp=[0]*n

#1.差分相减(差分公式)
#可以跳过不写

#2.转换加减(区间加减→端点加减)
for i in range(m):
    l,r,v= map(int, input().split())
    dp[l-1]+=v  #l的下标是l-1
    dp[r]-=v    #r+1的下标是r

#3.前缀相加(前缀和公式)
for i in range(1,n):
    dp[i]+=dp[i-1]

print(sum(dp))
'''
input:
500 3
150 300 4
100 200 20
470 471 19
print:
2662
'''

🎄差分-小明的彩灯

🚀传送锚点

蓝桥模板,备战蓝桥,python,蓝桥杯,算法,动态规划,数据结构

💡思路点拨

接下来，一道差集的简单题「小明的彩灯」，检验一下差分三部曲的掌握情况吧~

1、差分相减：先创建一个dp列表，差分相减直接跳过。

2、转换加减：区间彩灯的亮度加减，转化为两个端点的亮度加减。

3、前缀相加：前缀和还原回去，就完成差分模板了。

🍞代码详解

#差分-小明的彩灯
n,q=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(q):
    l,r,x=map(int,input().split())
    dp[l-1]+=x
    dp[r]-=x
for i in range(1,n):
    dp[i]+=dp[i-1]
for i in range(n):
    print(max(dp[i]+a[i],0),end=" ")
'''
input:
5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100
print:
0 5 5 6 10
'''