东师附中B层团队冲刺NOIP2019知识点模拟（6）题解版

传送门

password：12345ssdlh

听说经常打题解rp++

T1

搜索啊

没什么好说的

代码

T1

T2

听说暴力能AC

但我们还是要想正解

显然先按v排序

然后维护Σ_Δd就好了

用个树状数组维护一发就好了

代码

T2

T3

在ACM里试贪心无疑是一种好方法

按照重量+力量排序（然而并不知道为什么）

emm 直接给代码吧

T3

T4

正解使用带权并查集的，但我不会

于是用普通并查集水过

先预处理出来所有点的相对坐标

然后用并查集判连通就好了

代码

T4

T5

很容易推出dp式dp[i]=Σdp[j],s(j+1,i)>=0

展开s，可得S[i]-S[j]>=0,S表示前缀和

于是，就是说，只要S[i]>=S[j],j就可以更新i

用一个树状数组维护一发就好了

代码

T5

T6

裸的线段树

就是维护的东西多一点

除了维护一个区间的最长0的长度之外，还要维护包含左端点的最长0核保函右端点的最长0就好了

然后合并的话自行想一想应该怎么合就好了

代码

T6

T7

一个区间DP

设dp[i][j][0/1]表示已经吃了i到j的草，并且站在这段区间的左面或右面时，最少的损失

那么

dp[i][j][0]=min(dp[i+1][j][0]+abs(a[i+1]-a[i])*(n-j+i),dp[i+1][j][1]+abs(a[j]-a[i])*(n-j+i));

dp[i][j][1]=min(dp[i][j-1][0]+abs(a[i]-a[j])*(n-j+i),dp[i][j-1][1]+abs(a[j-1]-a[j])*(n-j+i));

代码

T7

东师附中B层团队冲刺NOIP2019知识点模拟（6）题解版

原文：https://www.cnblogs.com/yanghaokun/p/11390419.html