即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[洛谷P3769][CH弱省胡策R2]TATT-K-D树

编程语言 zlttttt 11℃ 0评论
本文目录
[隐藏]

1.[CH弱省胡策R2]TATT

1.1.1.题目描述

四维空间真是美妙。现在有n个四维空间中的点,请求出一条最长的路径,满足任意一维坐标都是单调不降的。 注意路径起点是任意选择的,并且路径与输入顺序无关(路径顺序不一定要满足在输入中是升序)。

路径的长度是经过的点的数量,任意点只能经过一次。

1.1.2.输入输出格式

1.1.2.1.输入格式:

第一行一个整数n。 接下来n行,每行四个整数ai,bi,ci,di。表示四维坐标

1.1.2.2.输出格式:

一行一个整数,表示最长路径的长度

1.1.3.输入输出样例

1.1.3.1.输入样例#1:

4


2 3 33 2333


2 3 33 2333


2 3 33 2333


2 3 33 2333

1.1.3.2.输出样例#1:

4

1.1.3.3.说明

测试点编号 n m 特殊说明

1 n≤2000 m≤109


2 n≤5104 m≤8


3−4 同上 m≤105 所有点的第三,四维坐标相同


5−6 同上 同上 所有点的第四维坐标相同


7−8 同上 m≤100 无


9−10 同上 m≤109


所以咱就被这题坑了一晚上……


虽然感觉学到了很多但是咱还是要说:

2.(╯‵□′)╯︵┻━┻

所以看咱的程序时可能会出现一些莫名其妙的变量、调试信息之类的不要在意~


另外,这题明明是R1的A题啊……


思路:


这次就讲讲咱的思路过程吧。


首先。这显然是K-D树。


然后,这是个DP,四维的最长不下降子序列。

好,于是有了咱的第一个版本的代码:


版本一


然后发现又T又WA……


很显然,这个版本的剪枝太naive了,而且逻辑还有问题,以至于不仅效率和暴力差不多还会WA…….


本身K-D树就是靠剪枝混饭吃的……

那么我们获得了版本二:


版本二


然后又T成了ZZ……


显然这个版本的剪枝并不见得比上个版本高明了多少(事实上有些情况更慢了),但至少能保证正确率……

于是来到版本三:


版本三


然后事实上这个版本的剪枝和上一个版本已经有了巨大差别,尤其是query部分已经足够快了。


但是,modify操作的调用次数迷之巨大……


所以,依然T成ZZ……

然后我们得到了最终版本一:

#include
#include
#include
#include
#include

using namespace std;

const int N=50009;

int main_d;

inline int minn(int a,int b){if(areturn a;return b;}
inline int maxx(int a,int b){if(a>b)return a;return b;}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || '9'if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

struct point
{
    int coord[4],mn[4],id,l,r,mv,v,f;

    int &operator [](int x)
    {
        return coord[x];
    }

    void init()
    {
        for(int i=0;i<=3;i++)
            mn[i]=coord[i];
        v=mv=f=0;
    }
};

bool operator <(point satori,point koishi)
{
    return satori[main_d]inline bool ecmp(point a,point b)
{
    for(int i=0;i<=3;i++)
        if(a[i]!=b[i])
            return 0;
    return 1;
}

inline bool judge(point satori,point koishi)
{
    for(int i=0;i<=3;i++)
        if(satori[i]>koishi[i])
            return 0;
    return 1;
}

inline bool valid(point satori,point koishi)
{
    for(int i=0;i<=3;i++)
        if(satori.mn[i]>koishi[i])
            return 0;
    return 1;
}

int p[N];
int sumt[5];

struct k_dimensional_tree
{
    int root,maxval;
    point t[N];

    void update(int x)
    {
        for(int i=0;i<=3;i++)
            t[x].mn[i]=minn(t[x].mn[i],minn(t[t[x].l].mn[i],t[t[x].r].mn[i]));
        t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv));
    }

    void push(int x)
    {
        t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv));
    }

    inline int check(int x,point p)
    {
        if(!x)return x;
        int ret=1;
        for(int i=0;i<=3;i++)
            if(p[i]0;
        return ret;
    }

    int biu(int l,int r,int d)
    {
        main_d=d;

        int mid=l+r>>1,nxt;
        nth_element(t+l,t+mid,t+r+1);

        nxt=d+1;
        if(nxt==4)
            nxt=1;
        t[mid].init();

        if(l1,nxt),t[t[mid].l].f=mid;
        if(mid1,r,nxt),t[t[mid].r].f=mid;

        update(mid);
        return mid;
    }

    void query(int x,point p,int d)
    {
        sumt[0]++;
        //printf("now in %d\n",x);
        if(judge(t[x],p) && maxvalint nxt=d+1;
        if(nxt==4)
            nxt=1;
        if(p[d]>=t[x][d])
        {
            int a=t[x].l,b=t[x].r;
            if(t[a].mvif(valid(t[a],p) && t[a].mv>maxval)
                query(a,p,nxt);
            if(valid(t[b],p) && t[b].mv>maxval)
                query(b,p,nxt);
        }
        else
            if(valid(t[t[x].l],p) && t[t[x].l].mv>maxval)
                query(t[x].l,p,nxt);
    }

    void modify(int x,int v)
    {
        t[x].v=v;
        push(x);
        while(x=t[x].f)
            push(x);
    }
}koishi;    

bool pcmp(int a,int b)
{    
    for(int i=0;i<=3;i++)
        if(koishi.t[a][i]!=koishi.t[b][i])
            return koishi.t[a][i]return 0;
}

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        for(int j=0;j<=3;j++)
            koishi.t[i][j]=read();
        koishi.t[i].id=i;
    }

    koishi.root=koishi.biu(1,n,1);
    sort(p+1,p+n+1,pcmp);

    for(int i=1;i<=n;i++)
    {
        koishi.maxval=0;
        int o=p[i];
        //printf("querying %d:%d %d %d %d\n",p[i],koishi.t[o][0],koishi.t[o][1],koishi.t[o][2],koishi.t[o][3]);
        koishi.query(koishi.root,koishi.t[p[i]],1);
        koishi.modify(p[i],koishi.maxval+1);
        //cerr<<(double)clock()/CLOCKS_PER_SEC<
    }

    printf("%d\n",koishi.t[koishi.root].mv);

    //cerr<<"my"<
    return 0;
}

对于随机数据modify操作的次数是之前的二十分之一……

好事实上我们已经完美解决了这题但是……不觉得前两个版本T得很玄学吗?

于是咱又得到了最终版本2:

#include
#include
#include
#include
#include

using namespace std;

const int N=50009;

int main_d;

inline int minn(int a,int b){if(areturn a;return b;}
inline int maxx(int a,int b){if(a>b)return a;return b;}

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || '9'if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

struct point
{
    int coord[4],mn[4],mx[4],l,r,mv,v,ll,rr;

    int &operator [](int x)
    {
        return coord[x];
    }

    void init()
    {
        for(int i=0;i<=3;i++)
            mn[i]=mx[i]=coord[i];
        v=mv=0;
    }
};

bool operator <(point satori,point koishi)
{
    return satori[main_d]inline bool ecmp(point a,point b)
{
    for(int i=0;i<=3;i++)
        if(a[i]!=b[i])
            return 0;
    return 1;
}

inline bool valid(point satori,point koishi)
{
    for(int i=1;i<=3;i++)
        if(satori.mn[i]>koishi[i])
            return 0;
    return 1;
}

inline bool judge(point satori,point koishi)
{
    for(int i=0;i<=3;i++)
        if(satori[i]>koishi[i])
            return 0;
    return 1;
}

int p[N];

struct k_dimensional_tree
{
    int root,maxval;
    point t[N];

    void update(int x)
    {
        for(int i=0;i<=3;i++)
        {
            t[x].mn[i]=minn(t[x].mn[i],minn(t[t[x].l].mn[i],t[t[x].r].mn[i]));
            t[x].mx[i]=maxx(t[x].mx[i],maxx(t[t[x].l].mx[i],t[t[x].r].mx[i]));
        }
        t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv));
    }

    void push(int x)
    {
        t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv));
    }

    int biu(int l,int r,int d)
    {
        main_d=d;

        int mid=l+r>>1,nxt;
        nth_element(t+l,t+mid,t+r+1);

        nxt=d+1;
        if(nxt>3)
            nxt=1;
        t[mid].init();
        t[mid].ll=l;
        t[mid].rr=r;

        if(l1,nxt);
        if(mid1,r,nxt);

        update(mid);
        return mid;
    }

    void query(int x,point p,int d)
    {
        if(judge(t[x],p) && maxvalint nxt=d+1;
        if(nxt==4)
            nxt=1;
        if(p[d]>=t[x][d])
        {
            int a=t[x].l,b=t[x].r;
            if(t[a].mvif(valid(t[a],p) && t[a].mv>maxval)
                query(a,p,nxt);
            if(valid(t[b],p) && t[b].mv>maxval)
                query(b,p,nxt);
        }
        else
            if(valid(t[t[x].l],p) && t[t[x].l].mv>maxval)
                query(t[x].l,p,nxt);
    }

    inline bool in(point satori,point koishi)
    {
        for(int i=0;i<4;i++)
            if(koishi[i]return 0;
        return 1;
    }

    bool inr(int satori,int koishi)
    {
        if(t[satori].ll<=koishi && koishi<=t[satori].rr)
            return 1;
        return 0;
    }

    void modify(int x,int p,int v)
    {
        if(x==p)
        {
            t[x].v=v;
            push(x);
            return;
        }

        if(t[x].l && inr(x,p) && in(t[x],t[p]))
            modify(t[x].l,p,v);
        if(t[x].r && inr(x,p) && in(t[x],t[p]))
            modify(t[x].r,p,v);

        push(x);
    }
}koishi;

bool pcmp(int a,int b)
{
    for(int i=0;i<=3;i++)
        if(koishi.t[a][i]!=koishi.t[b][i])
            return koishi.t[a][i]return 0;
}

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        for(int j=0;j<=3;j++)
            koishi.t[i][j]=read();
    }

    koishi.root=koishi.biu(1,n,1);
    sort(p+1,p+n+1,pcmp);

    for(int i=1;i<=n;i++)
    {
        koishi.maxval=0;
        koishi.query(koishi.root,koishi.t[p[i]],1);
        koishi.modify(koishi.root,p[i],koishi.maxval+1);
    }

    printf("%d\n",koishi.t[koishi.root].mv);

    return 0;
}

虽然没有上一个版本优(各种意义上),但是能稳过~

可以看到咱只是在modify函数里加了一个判断目标节点编号是否在当前节点区间内就过掉了~


为什么呢?


因为,在前几个版本里,如果出现了目标点与当前查询节点共线的情况,就会同时递归左儿子和右儿子(因为目标节点同时处于左儿子和右儿子所表示的区间内),只要被这么卡上哪怕一次都是很疼的……

不过只是被卡几次的话还是很稳的。


但是,不要忘了这题有4维,任一维共线都会出事,而且虽然根据样例的坐标范围共线的概率还不算大(0~10000的范围几乎无影响),但如果坐标范围很小的话,比如咱造数据时开的0~10……比!暴!力!还!慢!很!多!!!

所以卡一卡这样的情况就可以过了~


另外有个小插曲:标程,采用了一个个插入+替罪羊树重构。洛谷上82分T了……


原因很显然是跟咱的程序一样的……要不是靠替罪羊续秒咱还真不知道标程君怎么A的……


换句话说……如果替罪羊能给咱的程序也续上一秒的话……


神奇的标程君

转载请注明:CodingBlog » [洛谷P3769][CH弱省胡策R2]TATT-K-D树

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情