P1969 积木大赛 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • bjxdw
    大佬
  • Brandon鹏
    666
  • kjl_L
    666
  • 刘政
    666
  • fearlessand
    听不懂,好高级
  • zhouxiaoyi
    感谢DALAO
  • Macrohard
    大佬%%%%
  • throusea
    2333
  • 看客
    6666666666666
  • Ureka_Gestalt
    666
作者: FP·荷兰猪 更新时间: 2017-04-27 19:54  在Ta的博客查看 举报    367  
#include <iostream>
using namespace std;
int main()
{
    int n,a,last=0,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(a>last)ans+=(a-last);
        last=a;
    }
    cout<<ans<<endl;
}
//把序列分成(a1,..ai)(ai+1,...aj)......(ak,...an)多个非递减序列。
//然后所有段中最大值的和减去除第一段外的段的最小值,化简一下,就出来了

评论

  • Blackcomb
    不开数组AC……这思想远超常人
  • DimensionTripper
    思想远超常人
  • Brandon鹏
  • Ace_Heart
    膜拜大佬的思维
  • 小神犇
    666
  • Steven_Meng
    %%%大佬
  • bjrenjikai
    %%%%%%%%
  • SodiumThiocyanate
    Orz
  • ETO组织成员
    orz
  • tan_gent
    666
作者: ww3113306 更新时间: 2017-10-31 22:34  在Ta的博客查看 举报    119  

刚刚居然发现这是noip的题。。。震惊。。。

然而并不需要DP,线段树,,,什么什么的

纯模拟就好了啊

而且数组也不需要啊,,5个变量就好了

因为存储中间答案是没有用的

#include<bits/stdc++.h>
using namespace std;
int s,n,ans,now;
int main()
{
    int i;
    scanf("%d",&n);
    scanf("%d",&ans);//肯定至少要第一块那么多次(实际上是所以目标值的最大值那么多次,但是要找最大值麻烦,反正后面可以解决,所以直接读第一块就好了)
    now=ans;//记录当前目标积木高度
    for(i=1;i<n;i++)
    {
        scanf("%d",&s);
        if(s>now) ans+=(s-now);//如果后面的大于当前目标,显然要多搞几次才行,,,
//如果小于,现在在搞这一块的时候顺便就可以把下一块弄好了
//所以只要+下一块比现在多的就可以了
        now=s;//更新现在目标的值
    }
    printf("%d",ans);//愉快输出
    return 0; 
}

评论

  • HigHwind
    有限微积分应该是指求和吧,它的逆算子才算差分吧
  • xzzg_qdz
    讲得很好呀...赞这么少呢
  • 学委
    “然后今天有一道毒瘤题”……
  • jyttoby
    求和是所谓有限积分,“微”的话……
  • smy2006
    4ms慢的要死。。。汝听,人言否?
作者: qwaszx 更新时间: 2018-02-24 21:32  在Ta的博客查看 举报    32  

qwq为什么没有差分题解啊

一般区间操作首先要想差分————yql

差分是个啥?

△f=f(x+1)-f(x),就像微积分,但把增量换成了1,也叫有限微积分

这里定义差分f[i]=h[i]-h[i-1],i=1...n+1,h[0]=0,h[n+1]=0.

容易知道f中正值之和等于负值之和的绝对值

Σf[i]=Σh[i]-h[i-1]=h[n+1]-h[0]=0,得证.

于是我们可以猜ans=正值之和

证明?

如果f[i]为正,容易知道我们要往这一摞上搭积木,所以ans+=h[i]-h[i-1]=f[i]

如果f[i]为负,可以在之前搭的时候一起搭上去,所以ans不变

当然这可以通过其他方式省去数组,但差分有更多的用途

考虑区间加

在a(原数组,下同)上表现为i=l...r,a[i]+=w;

而在f数组上的表现则为f[l]+=w,f[r+1]-=w.

证明自己yy一下就好,很容易

于是这东西可以O(1)修改

可以推广到二维和树上,区间乘法应该也可以???适用于多询问少修改的题

然后今天有一道毒瘤题要求区间翻转+区间加+带负值积木大赛+查询历史版本

于是可以差分做


考虑翻转之后的f

对于l+1~r+1,可以取反然后翻转

对于l和r,暴力处理一下即可

丢到平衡树上就好了

历史版本加上一个操作树就好

没有强制在线就不需要持久化


到这是yql原话反正我没怎么听懂orz

最后回到这个题上来233

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int c[110000],n,ans=0;
inline int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
inline int max(int a,int b)
{
    if(a>b)return a;return b;
}
int main()
{
    n=getin();
    for(register int i=1;i<=n;i++)
        c[i+1]=-getin(),c[i]-=c[i+1],ans+=max(c[i],0);
    printf("%d",ans);
}

4ms...慢的要死,可以自己再卡卡常数

区间的话分块O(nsqrt(n))/线段树(nlogn)啥的都能做

我这么菜不会别的233

评论

  • lqhsr
    还没有评论
  • ferrum_cccp
    写下你的评论
  • 圣龙阿布
    妈个。。。
  • zrzluck99
    这人woc
  • 缄默Mutism
    2018NOIP原题留念O(∩_∩)O~~
  • lizitong
    NOIP2018原题留念
  • 羊村你喜哥
    活捉一只野生P党awa
  • hepan
    NOIP2018原题留念
  • ferrum_cccp
    NOIP201$\huge{\text{3}}$原题留念
  • xzlhxc
    # %%%
作者: 缄默Mutism 更新时间: 2018-11-04 17:29  在Ta的博客查看 举报    29  

其实这道题没有那么麻烦(非常简单),只需要计算相邻两堆的高度差就行了。q为左边一堆高度,p为右边一堆高度,s为总摆放次数。

1.q<p,即左边的一堆比右边矮,左边的一堆摆完后,右边的还差一点,那么摆放次数s加上两堆的高度差p-q(相当于摆好了右堆)。

2.q>=p,即左边的一堆比右边矮,说明只要左边的一堆堆好了,那么右边的一堆也肯定堆好了,所以不需要增加摆放次数s。

附上代码(p党):

readln(n); 
for i:=1 to n do
  begin
      read(p);
      if q<p then s:=s+p-q;
      q:=p;
  end;
 writeln(s);

评论

  • ilove5x
    时间复杂度是没有常数的。
  • 陈思齐
    是O(n)
  • hcute
    %%%,2018年NOIP押题大佬
  • lsy263
    ....2018分治被卡了怎么说
  • From
    分治被卡了?我分治A了
  • 地大陈参志
    写常数是为了更好的分析,有时候时间会卡常数,说没常数的那个学了点皮毛就出来装蒜@ilove5x
  • Boring__Zheng
    +1
  • lcyxds
    不是没常数是有没有常数雨女无瓜。。。再说了O(1)都有可能爆T
  • 向北方
    @lcyxds O(1)爆?
  • 新手1833001
    @zmxqs 时间过短
作者: HybridTheory 更新时间: 2017-08-15 17:19  在Ta的博客查看 举报    26  

这道题我用了分治的方法,如果当前要计算搭建区间[l,r]

所需要的操作数,那么它就等于左右两个区间的操作数之和

减去两个区间连接部分的最小值,因为重复了,所以两边可

以连接起来。

f(l,r)=f(l,mid)+f(mid+1,r)-min(h[mid],h[mid+1])

代码:

#include<cstdio>
short h[100000];
int n,i;
short min(short x,short y){return x<y?x:y;}
int f(int l,int r){
    if(l==r)
        return h[l];
    int mid=l+r>>1;
    return f(l,mid)+f(mid+1,r)-min(h[mid],h[mid+1]);
}
int main(){
    scanf("%d",&n);
    for(;i<n;i++)
        scanf("%hd",h+i);
    printf("%d",f(0,n-1));
    return 0;
}
时间复杂度:O(2n)
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。