/ Vijos / 题库 / Fish && kitty /

题解

36 条题解

  • 2
    @ 2018-08-16 17:51:17

    本题考查很全面 线段树(单点修改+区间查询+区间最大值)+离散化+DP+二分查找

    线段树方面：对于每一个在s[i]+t与s[i]-t之间的高度(离散化)进行累加 最大值与sum值分开计算

    离散化：用了Rank来记录第1个元素的编号(从小到大)

    DP： 对于i 最大的方案长度={距离不超过t的所有人中最大的方案长度}+1 i的方案={i之前不超过t的所有人的总方案}+1

    这题BT...狂打120ROW
    话不多说，代码上：
    #include<cstdio>
    #include<algorithm>
    const int MAXN=100100;
    const int MOD=198964;
    using namespace std;
    struct Tree {
    int l,r,maxv,sum,add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define maxv(x) tree[x].maxv
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
    #define lch (o<<1)
    #define rch (o<<1|1)
    } tree[MAXN<<2];
    inline int max(int a,int b) {
    return a>b?a:b;
    }
    inline int read(){
    int x=0;
    char ch=getchar(),w=1;
    while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;
    ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';
    ch=getchar();
    }
    return x*w;
    }
    void build(int o,int l,int r) {
    l(o)=l,r(o)=r,maxv(o)=sum(o)=add(o)=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(l<=mid)build(lch,l,mid);
    if(r>mid)build(rch,mid+1,r);
    return;
    }
    int ask_max(int o,int l,int r) {
    if(l(o)>=l&&r(o)<=r)return maxv(o);
    if(l(o)==r(o))return maxv(o);
    int mid=(l(o)+r(o))>>1,val=0;
    if(l<=mid)val=ask_max(lch,l,r)%MOD;
    if(r>mid)val=max(val,ask_max(rch,l,r))%MOD;
    return val;
    }
    int ask_sum(int o,int l,int r) {
    if(l(o)>=l&&r(o)<=r)return sum(o);
    int mid=(l(o)+r(o))>>1,val=0;
    if(l<=mid)val=ask_sum(lch,l,r)%MOD;
    if(r>mid)val=(val+ask_sum(rch,l,r))%MOD;
    return val;
    }
    int wl,wr;
    void change(int o,int pos,int v) {
    if(l(o)==r(o)) {
    add(o)=(add(o)+v)%MOD;
    sum(o)=(sum(o)+v)%MOD;
    maxv(o)=ask_max(1,wl,wr)+1;
    return;
    }
    int mid=(l(o)+r(o))>>1;
    if(pos<=mid)change(lch,pos,v);
    if(pos>mid)change(rch,pos,v);
    sum(o)=(sum(o)+v)%MOD;
    maxv(o)=max(maxv(lch),maxv(rch));
    }
    int Rank[MAXN],s[MAXN],a[MAXN],m=0,h[MAXN],n,t,tot=0;
    bool cmp(int x,int y) {
    return s[x]<s[y];
    }
    int findl(int x) {
    int l=0,r=n;
    while(r-l>1) {
    int mid=(l+r)>>1;
    if(a[mid]>=x)r=mid;
    else l=mid;
    }
    return h[Rank[r]];
    }
    int findr(int x) {
    int l=1,r=n+1;
    while(r-l>1) {
    int mid=(l+r)>>1;
    if(a[mid]<=x)l=mid;
    else r=mid;
    }
    return h[Rank[l]];
    }
    int main() {

    n=read();t=read();
    for(int i=1; i<=n; i++) {
    s[i]=read();
    a[i]=s[i];
    Rank[i]=i;
    }
    sort(Rank+1,Rank+1+n,cmp);
    sort(a+1,a+1+n);
    a[0]=-1;
    for(int i=1; i<=n; i++) {
    if(a[i]!=a[i-1])m++;
    h[Rank[i]]=m;
    }
    build(1,1,m);
    for(int i=1; i<=n; i++) {
    wl=findl(s[i]-t);
    wr=findr(s[i]+t);
    int ret=ask_sum(1,wl,wr);
    tot=(tot+ret)%MOD;
    change(1,h[i],ret+1);
    }
    printf("%d\n",tot);
    if(maxv(1)!=1)printf("%d\n",maxv(1));
    else puts("0");
    return 0;
    }
    注意，已经AC了

    • @ 2021-01-08 12:34:05

      幫你整理一下代碼

      #include<cstdio>
#include<algorithm>
const int MAXN=100100;
const int MOD=198964;
using namespace std;
struct Tree{
    int l,r,maxv,sum,add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define maxv(x) tree[x].maxv
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
    #define lch (o<<1)
    #define rch (o<<1|1)
}tree[MAXN<<2];
inline int max(int a,int b)
{
    return a>b?a:b;
}
inline int read()
{
    int x=0;
    char ch=getchar(),w=1;
    while (ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*w;
}
void build (int o,int l,int r)
{
    l(o)=l,r(o)=r,maxv(o)=sum(o)=add(o)=0;
    if (l==r)
        return;
    int mid=(l+r)>>1;
    if (l<=mid)
        build(lch,l,mid);
    if (r>mid)
        build(rch,mid+1,r);
    return;
}
int ask_max(int o,int l,int r)
{
    if (l(o)>=l&&r(o)<=r)
        return maxv(o);
    if (l(o)==r(o))
        return maxv(o);
    int mid=(l(o)+r(o))>>1,val=0;
    if (l<=mid)
        val=ask_max(lch,l,r)%MOD;
    if (r>mid)
        val=max(val,ask_max(rch,l,r))%MOD;
    return val;
}
int ask_sum(int o,int l,int r)
{
    if (l(o)>=l&&r(o)<=r)
        return sum(o);
    int mid=(l(o)+r(o))>>1,val=0;
    if (l<=mid)
        val=ask_sum(lch,l,r)%MOD;
    if (r>mid)
        val=(val+ask_sum(rch,l,r))%MOD;
    return val;
}
int wl,wr;
void change(int o,int pos,int v)
{
    if (l(o)==r(o))
    {
        add(o)=(add(o)+v)%MOD;
        sum(o)=(sum(o)+v)%MOD;
        maxv(o)=ask_max(1,wl,wr)+1;
        return;
    }
    int mid=(l(o)+r(o))>>1;
    if (pos<=mid)
        change(lch,pos,v);
    if (pos>mid)
        change(rch,pos,v);
    sum(o)=(sum(o)+v)%MOD;
    maxv(o)=max(maxv(lch),maxv(rch));
}
int Rank[MAXN],s[MAXN],a[MAXN],m=0,h[MAXN],n,t,tot=0;
bool cmp(int x,int y)
{
    return s[x]<s[y];
}
int findl(int x)
{
    int l=0,r=n;
    while (r-l>1)
    {
        int mid=(l+r)>>1;
        if (a[mid]>=x)
            r=mid;
        else
            l=mid;
    }
    return h[Rank[r]];
}
int findr(int x)
{
    int l=1,r=n+1;
    while (r-l>1)
    {
        int mid=(l+r)>>1;
        if (a[mid]<=x)
            l=mid;
        else
            r=mid;
    }
    return h[Rank[l]];
}
int main()
{
    n=read();
    t=read();
    for (int i=1; i<=n; i++)
    {
        s[i]=read();
        a[i]=s[i];
        Rank[i]=i;
    }
    sort(Rank+1,Rank+1+n,cmp);
    sort(a+1,a+1+n);
    a[0]=-1;
    for (int i=1; i<=n; i++)
    {
        if (a[i]!=a[i-1])
            m++;
        h[Rank[i]]=m;
    }
    build(1,1,m);
    for (int i=1; i<=n; i++)
    {
        wl=findl(s[i]-t);
        wr=findr(s[i]+t);
        int ret=ask_sum(1,wl,wr);
        tot=(tot+ret)%MOD;
        change(1,h[i],ret+1);
    }
    printf("%d\n",tot);
    if (maxv(1)!=1)
        printf("%d\n",maxv(1));
    else
        puts("0");
    return 0;
}
  • 0
    @ 2017-04-28 07:10:31

    DP的时候f[i]最开始设计成1~i中最长序列，但是转移的时候f[i]=max(f[i-1],pre[i]?(f[pre[i]]+1):0);
    pre[i]为i之前第一个与其相邻差小于等于h的数的位置。
    这样的话因为第i个数可以不取的（决策1）所以决策2中的f[pre[i]]也可能是从i之前与其差大于h的数开始取的。。就出现了问题。
    所以要改成固定序列最后一位取什么的状态。

  • 0
    @ 2016-05-07 11:21:01

    用treap写的，比较慢。。。。
    话说为啥要模198964。。。。

    测试数据 #0: Accepted, time = 15 ms, mem = 15440 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 15444 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 15444 KiB, score = 10
    测试数据 #3: Accepted, time = 46 ms, mem = 15444 KiB, score = 10
    测试数据 #4: Accepted, time = 93 ms, mem = 15444 KiB, score = 10
    测试数据 #5: Accepted, time = 109 ms, mem = 15440 KiB, score = 10
    测试数据 #6: Accepted, time = 171 ms, mem = 15444 KiB, score = 10
    测试数据 #7: Accepted, time = 359 ms, mem = 15444 KiB, score = 10
    测试数据 #8: Accepted, time = 421 ms, mem = 15448 KiB, score = 10
    测试数据 #9: Accepted, time = 406 ms, mem = 15444 KiB, score = 10
    Accepted, time = 1635 ms, mem = 15448 KiB, score = 100

    • @ 2016-08-31 17:44:19

      198964...一个特殊的日子

  • 0
    @ 2014-04-17 19:42:12

    千万记住最大的方案也要模……

  • 0
    @ 2012-09-15 16:10:43

    编译通过...

    ├ 测试数据 01：答案正确... (3ms, 8400KB)

    ├ 测试数据 02：答案正确... (0ms, 8400KB)

    ├ 测试数据 03：答案正确... (0ms, 8400KB)

    ├ 测试数据 04：答案正确... (0ms, 8400KB)

    ├ 测试数据 05：答案正确... (14ms, 8400KB)

    ├ 测试数据 06：答案正确... (18ms, 8400KB)

    ├ 测试数据 07：答案正确... (10ms, 8400KB)

    ├ 测试数据 08：答案正确... (190ms, 8400KB)

    ├ 测试数据 09：答案正确... (175ms, 8400KB)

    ├ 测试数据 10：答案正确... (175ms, 8400KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 588ms / 8400KB

    真是辛苦，前面百度博客的题解全挂了，费了好多功夫才自己想出来，另外此题细节非常恶心！

    我们很容易写出两个简单的DP方程，然后用线段树维护最值，和。

    一个关键的问题就是离散化，但是有h太大，使得离散化受到了约束。

    方法如下：

    离散化之后，因为每个数扫描的范围就不是a[i]正负H了，

    所以我们可以把每个数的扫描范围重新更新（关键）

    范围的确定，可以预处理出来，把离散化后的排序再二分查找。

    把上下边界算出来后，

    在DP中加入线段树的查找即可

    下面是注意的细节：

    1.题意，长度为1的情况输出0，模198964（这个数字很和谐。。）

    2.二分查找下边界是大于或等于v的数，上边界是小于或等于v的数

    3.线段树的每个节点的sum值都要取模!

  • 0
    @ 2010-07-03 18:18:05

    第100人通过- -

  • 0
    @ 2010-03-03 22:41:57

    Accepted 有效得分：100 有效耗时：372ms

    蛮好玩的题啊``不过我比较悲剧,第一次提交没取模,第二次每输出无解.....第三次才过.....线段树乱搞啦,,,不用二分吧...

    写了点题解额,,

    http://hi.baidu.com/darin7/blog/item/578592af6a3fa8024a36d634.html

  • 0
    @ 2009-11-01 22:57:04

    198964

    看成了198946

    难道我真的跟一次AC线段树无缘？

  • 0
    @ 2009-11-01 21:58:04

    评测机太神奇了

    自己机子上将近2S的

    交上来只用了400MS

    AC了就好

    AC经典题了

    强大的离散线段树

    兴奋把

  • 0
    @ 2009-10-22 19:52:21

    少有的一遍AC

    我的blog有代码和稍微的提示;(copy无意义）

    http://hi.baidu.com/think%5Fexist/blog/item/6308a9d4e3c5f22506088b2f.html

  • 0
    @ 2009-10-01 17:07:00

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 72ms

    ├ 测试数据 06：答案正确... 103ms

    ├ 测试数据 07：答案正确... 181ms

    ├ 测试数据 08：答案正确... 524ms

    ├ 测试数据 09：答案正确... 586ms

    ├ 测试数据 10：答案正确... 571ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：2037ms

    哇蛤蛤 竟然一次AC 太神奇啦！！！！！！！！

  • 0
    @ 2009-09-27 14:05:34

    要判断 长度为 0 的情况的说...

  • 0
    @ 2009-09-19 15:40:22

    线段树+离散化

  • 0
    @ 2009-08-05 14:43:24

    1A,线段树啊，中间用了很多二分查找，速度慢到867MS dragon;607ms puppy

  • 0
    @ 2009-07-31 13:08:12

    http://hi.baidu.com/%CB%D5%CC%DAsauterne

  • 0
    @ 2009-07-26 19:00:43

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 9ms

    ├ 测试数据 07：答案正确... 41ms

    ├ 测试数据 08：答案正确... 338ms

    ├ 测试数据 09：答案正确... 338ms

    ├ 测试数据 10：答案正确... 275ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：1001ms

    把Splay注释掉...

    boyzkk...你失算了

    哈哈哈哈哈哈...

  • 0
    @ 2009-07-26 18:46:36

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 41ms

    ├ 测试数据 06：答案正确... 119ms

    ├ 测试数据 07：答案正确... 212ms

    ├ 测试数据 08：答案正确... 666ms

    ├ 测试数据 09：答案正确... 697ms

    ├ 测试数据 10：答案正确... 588ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：2323ms

    Orz fengdieqiao!!!

    Splay 太慢了,有空写线段树。

    注意在旋转的时候也要mod。

  • 0
    @ 2009-07-08 13:47:55

    Accepted 有效得分：100 有效耗时：1866ms

    话说我写的线段树从来就比大家的慢半拍,估计是用了结构体的缘故吧.

    注意那个mod..

    如果出个数据,方案数正好是那个不和谐的数的倍数的话,还得判断是真的零还是假的零了..

  • 0
    @ 2009-06-18 14:42:08

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 9ms

    ├ 测试数据 07：答案正确... 41ms

    ├ 测试数据 08：答案正确... 244ms

    ├ 测试数据 09：答案正确... 259ms

    ├ 测试数据 10：答案正确... 259ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：812ms

    对与第三次写线段树的我来说，能一次AC简直是奇迹！

  • 0
    @ 2009-05-25 10:39:05

    终于AC了，提醒一句：

    线段树插入点的时候要从上往下，不能从下往上，不然mod就是不对，至于为什么我也不知道……囧……

    Orz...

Fish && kitty

信息

ID
1183
难度
7
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
568
已通过
118
通过率
21%
被复制
6
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1