草庐IT

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

小蓝刷题 2023-04-13 原文

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

全文目录🧭

🎁差分模板

🌲差分-树木上药

🚀传送锚点

 💡思路点拨

🍞代码详解  

 🎄差分-小明的彩灯

🚀传送锚点​

 💡思路点拨

🍞代码详解 

🎁差分模板

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

#差分三部曲

#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

'''

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

🌲差分-树木上药

🚀传送锚点

 💡思路点拨

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

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
'''

 🎄差分-小明的彩灯

🚀传送锚点

 💡思路点拨

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

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
'''

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

​​

蓝桥mdashstrongxffxff1apython蓝桥杯算法动态规划数据结构

有关【蓝桥模板】——考试倒计时3天，你和省一就差这最后10分了（差分模板）的更多相关文章

  1. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  2. ruby-on-rails - Mandrill API 模板 - 2

    我正在使用Mandrill的RubyAPIGem并使用以下简单的测试模板:testastic按照Heroku指南中的示例，我有以下Ruby代码:require'mandrill'm=Mandrill::API.newrendered=m.templates.render'test-template',[{:header=>'someheadertext',:main_section=>'Themaincontentblock',:footer=>'asdf'}]mail(:to=>"JaysonLane",:subject=>"TestEmail")do|format|format.h

  3. ruby - Chef Ruby 遍历 .erb 模板文件中的属性 - 2

    所以这可能有点令人困惑，但请耐心等待。简而言之，我想遍历具有特定键值的所有属性，然后如果值不为空，则将它们插入到模板中。这是我的代码:属性:#===DefaultfileConfigurations#default['elasticsearch']['default']['ES_USER']=''default['elasticsearch']['default']['ES_GROUP']=''default['elasticsearch']['default']['ES_HEAP_SIZE']=''default['elasticsearch']['default']['MAX_OP

  4. ruby - Hanami link_to 助手只呈现最后一个元素 - 2

    我是HanamiWorld的新人。我已经写了这段代码:moduleWeb::Views::HomeclassIndexincludeWeb::ViewincludeHanami::Helpers::HtmlHelperdeftitlehtml.headerdoh1'Testsearchengine',id:'title'hrdiv(id:'test')dolink_to('Home',"/",class:'mnu_orizontal')link_to('About',"/",class:'mnu_orizontal')endendendendend我在模板上调用了title方法。htm

  5. ruby - 如果它是标点符号，我怎么能从字符串中删除最后一个字符，在 ruby​​ 中？ - 2

    啊，正则表达式有点困惑。我正在尝试删除字符串末尾所有可能的标点符号:ifstr[str.length-1]=='?'||str[str.length-1]=='.'||str[str.length-1]=='!'orstr[str.length-1]==','||str[str.length-1]==';'str.chomp!end我相信有更好的方法来做到这一点。有什么指点吗？ 最佳答案 str.sub!(/[?.!,;]?$/,'')[?.!,;]-字符类。匹配这5个字符中的任何一个(注意，。在字符类中并不特殊)?-前一个字符或组

  6. 由于 libgmp.10.dylib 的问题，Ruby 2.2.0 无法运行 - 2

    我刚刚安装了带有RVM的Ruby2.2.0，并尝试使用它得到了这个:$rvmuse2.2.0--defaultUsing/Users/brandon/.rvm/gems/ruby-2.2.0dyld:Librarynotloaded:/usr/local/lib/libgmp.10.dylibReferencedfrom:/Users/brandon/.rvm/rubies/ruby-2.2.0/bin/rubyReason:Incompatiblelibraryversion:rubyrequiresversion13.0.0orlater,butlibgmp.10.dylibpro

  7. ruby - Ruby 性能中的计时器 - 2

    我正在寻找一个用ruby​​演示计时器的在线示例，并发现了下面的代码。它按预期工作，但这个简单的程序使用30Mo内存(如Windows任务管理器中所示)和太多CPU有意义吗？非常感谢deftime_blockstart_time=Time.nowThread.new{yield}Time.now-start_timeenddefrepeat_every(seconds)whiletruedotime_spent=time_block{yield}#Tohandle-vesleepinteravalsleep(seconds-time_spent)iftime_spent

  8. ruby - ri 有空文件 – Ubuntu 11.10, Ruby 1.9 - 2

    我正在运行Ubuntu11.10并像这样安装Ruby1.9:$sudoapt-getinstallruby1.9rubygems一切都运行良好，但ri似乎有空文档。ri告诉我文档是空的，我必须安装它们。我执行此操作是因为我读到它会有所帮助:$rdoc--all--ri现在，当我尝试打开任何文档时:$riArrayNothingknownaboutArray我搜索的其他所有内容都是一样的。 最佳答案 这个呢？apt-getinstallri1.8编辑或者试试这个:(非rvm)geminstallrdocrdoc-datardoc-da

  9. Ruby - 删除文件中的最后一个字符？ - 2

    看起来一定很简单，但我就是想不通。如何使用RubyIO删除文件的最后一个字符？我查看了deletingthelastlineofafile的答案使用Ruby但没有完全理解它，必须有更简单的方法。有什么帮助吗？ 最佳答案 有File.truncate:truncate(file_name,integer)→0Truncatesthefilefile_nametobeatmostintegerbyteslong.Notavailableonallplatforms.所以你可以这样说:File.truncate(file_name,Fil

  10. ruby-on-rails - gem install rmagick -v 2.13.1 错误 Failed to build gem native extension on Mac OS 10.9.1 - 2

    我已经通过提供MagickWand.h的路径尝试了一切，我安装了命令工具。谁能帮帮我？$geminstallrmagick-v2.13.1Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingrmagick:ERROR:Failedtobuildgemnativeextension./Users/ghazanfarali/.rvm/rubies/ruby-1.8.7-p357/bin/rubyextconf.rbcheckingforRubyversion>=1.8.5...yescheckingfor/

随机推荐