【蓝桥模板】——考试倒计时3天,你和省一就差这最后10分了(差分模板)

大家好,我是爱分享的小蓝,欢迎交流指正~ 全文目录🧭 &#x1f3…

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

全文目录🧭

🎁差分模板

🌲差分-树木上药

🚀传送锚点

💡思路点拨

🍞代码详解

🎄差分-小明的彩灯

🚀传送锚点​

💡思路点拨

🍞代码详解


🎁差分模板

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

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


🌲差分-树木上药

💡思路点拨

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

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

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

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

🍞代码详解

🎄差分-小明的彩灯

💡思路点拨

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

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

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

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

🍞代码详解


​​​ 友友们,备战蓝桥最后3天,一起冲刺省赛一等奖!​​​

​​

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/1403.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部