P1020 导弹拦截 题解


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

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

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

评论

  • owlAlice
    我说,不要总说楼上的大佬怎样,因为洛谷智能排序之后,你楼上的大佬已经不是你楼上的了
  • 渣旺子
    楼上666
  • Ousmane_Dembele
    楼上的楼上666
  • UrJack
    楼上的楼上的楼上666
  • AKA_刀枪不入
    楼上的楼上的楼上的楼上666
  • 诸君拔剑吧
    楼上的楼上的楼上的楼上的楼上666
  • 块根大佬
    楼上的楼上的楼上的楼上的楼上的楼上666
  • HuangBo
    打破阵型~.~
  • 你好啊,再见
    楼上的楼上的楼上的楼上的楼上的楼上的楼上的楼上666(恢复阵型)
  • Resical
    楼上的楼上的楼上的楼上的楼上的楼上的楼上的楼上的楼上666
作者: Matyr 更新时间: 2017-10-12 16:43  在Ta的博客查看    216  

补一发树状数组的题解。

楼上dalao已经说得很清楚了,这道题就是要求一个最长单调不升子序列和一个最长单调上升子序列。

说白了就是二维偏序,所以很容易想到树状数组来维护最优解。详情见代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1000000];
int z[1000000];
int lowbit(int x)
{
    return x&-x;
}
int big;
inline int ask(int x)//这是用来求单调上升子序列的
{
    int r=0;
    for(int i=x;i>0;i-=lowbit(i))
        r=max(r,f[i]);
    return r;
}
inline void add(int x,int v)//这也是用来求单调上升子序列的
{
    for(int i=x;i<=big;i+=lowbit(i))
        f[i]=max(f[i],v);
}
inline int que(int x)//这是用来求最长单调不升子序列的
{
    int r=0;
    for(int i=x;i<=big;i+=lowbit(i))
        r=max(r,f[i]);
    return r;
}
inline void psh(int x,int v)//这也是用来求最长单调不升子序列的
{
    for(int i=x;i>0;i-=lowbit(i))
        f[i]=max(f[i],v);
}
int tot;
int a[1000000];
int ans;
int main()
{
    tot=1;
    while(scanf("%d",&a[tot])!=EOF)
    {
        big=max(big,a[tot]);
        z[tot]=a[tot];
        tot++;
    }
    tot--;//读入并统计个数
    for(int i=1;i<=tot;i++)//求最长单升子序列,树状数组中保存的是0~a[i]的最大值
    {
        int x=ask(a[i])+1;
        ans=max(ans,x);
        add(a[i]+1,x);//因为是严格单升所以这里要+1
    }
    memset(f,0,sizeof(f));//清空树状数组,用来求下面的不降子序列
    int num=0;
    for(int i=1;i<=tot;i++)//求最长不降子序列,树状数组里存的是a[i]~inf的最大值
    {
        int x=que(a[i])+1;
        num=max(num,x);
        psh(a[i],x);//因为是不升而不是严格单降所以不用-1或+1
    }
    printf("%d\n%d",num,ans);
    return 0;
}

评论

  • middle_set
    $O(\frac{n^2}{2})
  • middle_set
    貌似打错了,是$O(\frac{n^2}{2})$
  • Pascal周逸非
    厉害!!!
  • Passer1
    长见识
  • YZHX
    涨姿势了
  • 巫神搞比利
    装得一手好逼
  • ljw2005
    厉害厉害,6666。
  • constructor
    楼上是逗吗O(n^2/2)=O(n^2)好吧……
  • 大螺丝
    6666
  • Resical
    厉害了第一次见到这样的O()
作者: cplusplus 更新时间: 2017-11-09 17:41  在Ta的博客查看    121  

n方200分的题解!

只是加了一个常数优化,最坏1/2 n^2,平均效率较高

在朴素n^2算法中,用f[i]储存以i结尾的最长不上升子序列长度,如样例

i 1 2 3 4 5 6 7 8

a 389 207 155 300 299 170 158 65

f 1 2 3 2 3 4 5 6

发现当f的值相同时,越后面的导弹高度越高

用d[i]维护f值为i的最后一个导弹的位置,t记录当前已经求出最长不升子序列长度

递推求f时枚举a[d[t]],a[d[t-1]],。。。,a[d[1]]是否≥当前求的导弹高度,是就更新f

然后根据某定理求出第二问(楼下大佬们说的很清楚)

#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n=0,a[100001],f[100001],d[100001],ans=1,t=0;
int main() {
    while(~scanf("%d",&a[++n]));//读入数据方法
    n--;//n是导弹数,由于某些原因要--
    for(int i=1; i<=n; i++) {
        f[i]=1;
        for(int j=t; j>0; j--)
            if(a[i]<=a[d[j]]) {
                f[i]=f[d[j]]+1;
                break;
            }
        t=max(t,f[i]);
        d[f[i]]=i;//简单的维护过程
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    ans=1;
    t=0;
    for(int i=1; i<=n; i++) {
        f[i]=1;
        for(int j=t; j>0; j--)
            if(a[i]>a[d[j]]) {
                f[i]=f[d[j]]+1;
                break;
            }
        t=max(t,f[i]);
        d[f[i]]=i;
        ans=max(ans,f[i]);
    }
    printf("%d",ans);
}

评论

  • 吹箫童子
    orz orz
  • mobai
    豁然开朗
  • Yubestor
    代码打不开=-=
  • Runewrz
    (3)中有一个小的手误,应该把最后面的 P>=K 改为 P<=K 。
  • 单身贵族1123
    网站打不开怎么办,在线等急
  • 小白1548555
    66666 豁然开朗,膜大佬
  • fluttersunny
    %%%
  • Eric_hoo
    666666
  • Eric_hoo
    大佬
  • ZhYic
    终于明白。Orz
作者: JJPJJ 更新时间: 2017-12-27 13:56  在Ta的博客查看    109  

题目链接:导弹拦截


题意总结:

给出一个长度不超过100000的数列,其中的数每个是不大于50000的正整数,求这个数列的最长不降子序列(问一)以及将这个数列划分为n个不降子序列时,n的最小值(问二)。


思路:

1、对于问一直接用O(n*logn)的方法求最长不升子序列即可。

求不升子序列的方法:

http://https://www.luogu.org/blogAdmin/article/edit/20362

2、对于问二求整个数列的最长上升子序列即可。证明如下:

(1)假设打导弹的方法是这样的:取任意一个导弹,从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组,再在没打下来的导弹中任选一个重复上述步骤,直到打完所有导弹。

(2)假设我们得到了最小划分的K组导弹,从第a(1<=a<=K)组导弹中任取一个导弹,必定可以从a+1组中找到一个导弹的高度比这个导弹高(因为假如找不到,那么它就是比a+1组中任意一个导更高,在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组),同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来,连成一条上升子序列,其长度即为K;

(3)设最长上升子序列长度为P,则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升),则有

P>=K,所以K=P。

评论

  • Wilber
    orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz orz
  • rememberain
    膜拜dalao
  • Okitazero
    这么厉害的吗2333
  • chaos—moon
    膜拜 膜拜
  • futaba
    哈哈哈
  • futaba
    66666666666666
  • futaba
    66666666666666
  • Frozen_land
      ┏┓   ┣┫ ┏┳┫┣┳┓ ┃    ┃
  • futaba
    哥 加油!!! 祝你考试顺利!!
  • futaba
    我这样的渣渣不知到该说什么话呢
作者: H_Bryan 更新时间: 2018-08-05 15:09  在Ta的博客查看    103  

STL大法好!!!

先介绍两个STL函数:lower_bound(), upper_bound()


ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val) 返回的是非降序列的第一个>=key的数的地址(指针)(别问我为什么叫lower_bound,我也不知道);

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val) 返回的是非降序列的第一个>key的数的地址;

详情见下图

lower_bound(),upper_bound()


再来分析这道题,楼上大佬分析的无比清楚,直接维护一个非升序列和一个非降序列,维护的过程就能用上面两个神奇的STL(当然非升序列的upper_bound()要重载cmp)。不多说,上代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],f[100005],l[100005];
struct cmp{bool operator()(int a,int b){return a>b;}};
int main()
{
    int n=1;
    while(cin>>a[n])n++;
    n--;
    int con=1,cont=1;
    l[1]=f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(l[cont]>=a[i])l[++cont]=a[i];
        else l[upper_bound(l+1,l+cont+1,a[i],cmp())-l]=a[i];
        if(f[con]<a[i])f[++con]=a[i];
        else f[lower_bound(f+1,f+con+1,a[i])-f]=a[i];
    }
    cout<<cont<<" "<<con;
    return 0;
}

评论

  • 大芝士球
    很不错的题解
  • 千华缭乱
    zhx好评(
  • 基地A_I
    哈哈
  • 北冥、流风
    zhx囍hja……
  • 海阔天空818
    这题解不上首页可惜了
  • Sunbread
    西江月·证明 即得易见平凡,仿照上例显然。留作习题答案略,读者自证不难。 反之亦然同理,推论自然成立,略去过程QED,由上可知证毕。
  • ApocalypseOne
    改革春风吹满地
  • 信赖滴星辰
    应该上首页
  • 桑一鸣
    不错不错
  • flash666
    66666
作者: w1049344862 更新时间: 2019-02-02 23:09  在Ta的博客查看    90  

做这道题的时候看了很多题解,也没看懂,各种查终于弄明白了O(nlogn)的方法,自己来写一篇,试试能不能让更多人知道QwQ

这道题的做法很多,别的dalao题解里都有

dalao们也说了,根据"xxxx定理",这题只需要求一个不上升序列长度和一个上升序列长度

我只说说如何找出它们的长度

写给萌新看,求dalao们轻喷(>﹏<)

(如果有锅请dalao们指出)

一、lower_bound与upper_bound

zhx曾经曰过,STL很慢

hja曾经曰过,觉得STL慢是以zhx为首的一批oi选手的偏见

我们不管他们曰过什么,只来看看这两个函数

1.作用

这两个是STL中的函数,作用很相似:

假设我们查找x,那么:

lower_bound会找出序列中第一个大于等于x的数

upper_bound会找出序列中第一个大于x的数

没错这俩就差个等于号╮(╯▽╰)╭

2.用法

以下都以lower_bound做栗子 (因为upper_bound做出的栗子不好吃)

(其实就是我懒得打两遍)

它们俩使用的前提是一样的:序列是有序

对于一个数组a,在[1,n)的区间内查找大于等于x的数(假设那个数是y),函数就写成:

lower_bound(a + 1, a + 1 + n, x);

函数返回一个指向y的指针

看着是不是很熟悉?回想sort使用的时候:

sort(a, a + 1 + n, cmp);

这里a+1,a+1+n的写法是不是很像?

STL里面的函数写区间一般都这个尿性

同样的,lower_bound和upper_bound也是可以加比较函数cmp的:

lower_bound(a + 1, a + 1 + n, x, cmp);

到这里不得不说说前面的"有序序列",这里的"有序"是对什么有序?

你可能已经猜到了,它是对于比较器有序,并且必须是升序

(为什么不是降序?这个你可能要去问问写STL的人)

一旦对降序序列使用lower_bound,就会出现神奇的错误,具体原因可以看这篇:

https://blog.csdn.net/qq1337715208/article/details/81072709

当然比较器默认也是""

如果要在一个下降序列里寻找一个小于x的数呢?

根据我们之前说的,lower_bound只能对上升序列使用,那我假装下降序列是个上升序列就行了嘛~

(lower_bound:你当我傻吗)(w1049:没错我就当你傻)

只需要把比较器改成">":

lower_bound(a + 1, a + 1 + n, x, cmp);

同时需要写一个函数cmp:

bool cmp(const int& a,const int& b){return a > b;}

当然,你也可以这样:

lower_bound(a + 1, a + 1 + n, x, greater <int> () );

这里的greater<int>()就是c++友情提供的方便的大于函数,这样就不用自己动手写一个cmp函数了(其实就是懒)

它们的实现方式是二分查找 ,存在的意义就是让我们写代码更方便地偷懒(一行lower_bound比写二分查找方便多了)

3.返回值

众所周知,小葱非常擅长计算组合数返回的是个指针

对于返回值我们有两种处理方式:

第一种:

许多人讨厌指针,那么我们用这个指针减去数组开头的指针(即数组名),得到两个指针的差,就是数组下标,即:

int p = lower_bound(懒得写) - a;

那么a[p]就是要找的y

(如果不知道为什么就记着好了)

第二种:

指针好!指针秒!

改革春风吹满地,用指针的oier真争气!

(以上两行你可以当做什么都没看见)

int *p = lower_bound(还是懒得写);

那么*p就是要找的y

可以看出指针多么直接,不像数组下标还要倒腾一遍

总结一下:

好像没什么可总结的QwQ

对一个下降序列a

int p = lower_bound(a + 1, a + 1 + n, x, greater <int> () ) - a;

a[p]即a[1]到a[n]中第一个小于等于x的数

(被遗忘的upper_bound表示不服)

二、O(nlogn)求出最长不上升子序列的长度

(即一套系统最多拦截数)(终于到二了)

1.实现方式

首先我们需要一个数组a,存储从第1个到第n个导弹的高度

然后一个数组d(其实是个栈),存储不上升序列

把a中的每个元素挨个加到d里面:

(a中第i个元素为a[i],d长度为len,d中最后一个(也是最小的一个)为d[len])

如果a[i] <= d[len],说明a[i]可以接在d后面(而整个d还是有序的),那就简单粗暴地把a[i]丟进d:

d[ ++len ] = a[i]

如果a[i] > d[len],说明a[i]接不上

但是我们发扬瞎搞精神接的上要接,接不上创造条件也要接!

强行把a[i]塞进去:

在d中找到第一个小于a[i]的数,把它踹了,用a[i]代替它!(为什么正确在下面)

假设这个数是y,怎样踹掉它呢?

很明显,我们需要使用lower_bound和upper_bound来查找

第一步,找一个听起来无比正确的理由,比如它占着位置不干活啦,干起活来还不如a[i]啦,naive啦,它too young啦,too simple啦......反正能骗过lower_bound和upper_bound就行

(lower_bound&&upper_bound:你当我们傻)(w1049:真聪明)

接下来,特别有正义感的lower_bound和upper_bound就会去把y给拎出来

第二步,考虑使用什么

我们知道,要求的是最大不上升子序列长度,也就是如果两个元素相等也是可以

所以我们踹人就不用踹等于a[i]的

结合上面,应该使用upper_bound(终于想起来它了)并且使用>作为比较器(这是个下降序列)

第三步,直接开搞

int p = upper_bound(d + 1, d + 1 + len, a[i], greater <int> () ) - d;

d[p] = a[i];

成功把a[i]塞了进去

2.为什么正确

显然成立

如果y末尾,由于y < a[i],所以y后面能接的不如a[i]多,y让位给a[i]可以让序列更长

如果y不在末尾,那y有生之年都不会再被用到了,直接踹了y就行,y咋样,who care?

注意到lower_bound只能在有序序列中使用,此时d还有序吗?

当然有序。(本文第一个句号)

假设y前一个y1,y后一个是y2,则

y1 > y > y2

因为y是第一个小于a[i]的,所以

y1 > a[i]

又因为

a[i] > y > y2

所以

y1 > a[i] > y2

对比下原来的式子

y1 > y > y2

a[i]可以完美代替y,至于y以后咋办,who care?

对于最长上升子序列,只需要把上面的过程通通换一下符号

可以用以下方法证明:

反之亦然同理,推论自然成立,略去过程QED,由上可知证毕(多么美妙的证明)

3.代码:

for(int i=2;i<=n;i++)
    if(d[len]>=a[i])d[++len]=a[i];
    else {
        int p=upper_bound(d+1,d+1+len,a[i],greater<int>())-d;
        d[p]=a[i];
    }

最后len就是要求的最大不上升子序列长度

但要注意的是,d中存储的并不是最大不上升子序列!

原因如下:

即得易见平凡,仿照上例显然,留作习题答案略,读者自证不难

4.对样例模拟:

在这里推荐一下DevC++的调试器(不用DevC++的当我没说)

1.我们把a[i](389)加入d:

1

2.i=2,此时a[i](207)<=d[len](389),把a[2]加入d:

2

3.i=3,此时a[i](155)<=d[len](207),把a[3]加入d:

3

4.i=4,此时a[i](300)>d[len](155),不能直接加入,所以准备踹人

4

5.找出d中第一个小于a[i](300)的(即207),用a[i]换掉

5

6.i=5,此时a[i](299)>d[len](155),不能直接加入,所以准备踹人

6

7.找出d中第一个小于a[i](299)的(即155),用a[i]换掉

7

8.i=6,此时a[i](170)<=d[len](299),把a[6]加入d:

8

9.i=7,此时a[i](158)<=d[len](170),把a[7]加入d:

9

10.i=8,此时a[i](65)<=d[len](158),把a[8]加入d:

10

至此,得到最大不上升子序列长度len=6

三、AC代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],d1[N],d2[N],n;
int main() {
    while(cin>>a[++n]);n--;     //输入
    int len1=1,len2=1;      //初始长度为1
    d1[1]=a[1];     //用于求不上升序列长度
    d2[1]=a[1];     //用于求上升序列长度
    for(int i=2; i<=n; i++) {       //从a[2]开始枚举每个数(a[1]已经加进去了)
        if(d1[len1]>=a[i])d1[++len1]=a[i];      //如果满足要求(不上升)就加入d1
        else {      //否则用a[i]替换d1中的一个数
            int p1=upper_bound(d1+1,d1+1+len1,a[i],greater<int>())-d1;
            d1[p1]=a[i]; 
        }
        if(d2[len2]<a[i])d2[++len2]=a[i];       //同上
        else {
            int p2=lower_bound(d2+1,d2+1+len2,a[i])-d2;
            d2[p2]=a[i];
        }
    }
    cout<<len1<<endl<<len2;     //输出
    return 0;       //结束
}

更快速的版本:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register
using namespace std;
const int N=100010;
int a[N],d1[N],d2[N],n;
inline bool read(int &x) {
    char c=getchar();
    if(c==EOF)return false;
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9') {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return true;
}
int main() {
    while(read(a[++n]));n--;
    R int len1=1,len2=1;
    d1[1]=d2[1]=a[1];
    for(R int i=2; i<=n; i++) {
        if(d1[len1]>=a[i])d1[++len1]=a[i];
        else *upper_bound(d1+1,d1+1+len1,a[i],greater<int>())=a[i];
        if(d2[len2]<a[i])d2[++len2]=a[i];
        else *lower_bound(d2+1,d2+1+len2,a[i])=a[i];
    }
    printf("%d\n%d",len1,len2);
    return 0;
}

萌新第一次发题解,求通过~~~ (如果代码CE了,原因你们懂的)