K-D Tree在信息学竞赛中的应用

n+e posted @ 2015年7月22日 07:55 in Interesting with tags kd-tree , 6264 阅读

K-D Tree在信息学竞赛中的应用

福州一中 n+e

0. Update in 20160731:施工完毕 

---------------------------------------->>>戳这里

1. 简介

  Q:kdtree是啥我怎么没听说过?

  A:kdtree不仅是一个大模板,还是通用的骗分神器呢

  Q:我要学找哪里学?

  A:看下面的讲解吧...

2. 基本用法

2.1. 节点

2.2. 估价

2.3. 构树

2.4. 查询

2.5. k近点的实现

3. 从我的一道原创题说起

3.1. Bzoj-4066 简单题(kdtree的重构)

  简要题解

3.2. Bzoj-4154 [Ipsc2015]Generating Synergy(kdtree替代树套树)

  简要题解

3.3. Bzoj-3489 A Simple Rmq Problem(kdtree替代可持久化树套树)

  简要题解

3.4. Ctsc2015 Shallot || Uoj Round 8 决战圆锥曲线(kdtree替代重量平衡树套线段树维护凸包)

  简要题解

3.5. Xj Noi2015训练19 不可视境界线(kdtree优化dp)

    题目在这里

    3.5.1. 题目大意

      给定N,A[],B[],分析题目以后会得到如下的Dp方程:$$f_i=\min(\sqrt{f_j^2+(A_i-A_j)^2})(0\le j\lt i,\ A_i\ge B_j)$$

      $N\le 10^5,\ 1\le A_i\le 10^6,\ 0\le B_i\le 10^6$

    3.5.2 好像直接kdtree优化一下Dp就好了并不需要套什么数据结构啊...我错了我会补的

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100010
#define T 1<<18
int n,x[N],b[N],dx[N];long long f[N];
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define sqr(x) (1LL*(x)*(x))
#define mt(o) x0[o]=min(x0[o<<1],x0[o<<1|1]),x1[o]=max(x1[o<<1],x1[o<<1|1]),y0[o]=min(y0[o<<1],y0[o<<1|1]),vis[o]=vis[o<<1]|vis[o<<1|1]
class KDTree{public:
    long long ans,tmp,sf,y0[T];
    int pos,lim,x,vis[T],x0[T],x1[T],id[N],L[T],R[T],i;
    void bt(int o,int l,int r){
        if(l==r){
            L[o]=R[o]=dx[l];
            if(l==0)vis[o]=1,y0[o]=x0[o]=x1[o]=0;
            else y0[o]=1LL<<60,x0[o]=1<<20;
        }else{
            int mid=l+r>>1;
            bt(o<<1,l,mid),bt(o<<1|1,mid+1,r);mt(o);
            L[o]=L[o<<1],R[o]=R[o<<1|1];
        }
    }
    void _ins(int o,int l,int r){
        if(l==r)y0[o]=sf,x0[o]=x1[o]=pos,vis[o]=1,id[l]=i;
        else{
            int mid=l+r>>1;
            if(pos<=R[o<<1])_ins(o<<1,l,mid);
            else _ins(o<<1|1,mid+1,r);mt(o);
        }
    }
    void ins(int idt,int xi,long long fi){
        i=idt,pos=xi,sf=fi,_ins(1,0,n);
    }
#define dis(o) y0[o]+sqr(max(max(x-x1[o],x0[o]-x),0))
    void _query(int o,int l,int r){
        if(!vis[o]||dis(o)>=ans)return;
        if(l==r){
            if(tmp=y0[o]+sqr(x0[o]-x),tmp<ans)ans=tmp,pos=id[l];return;
        }
        int mid=l+r>>1,d0=dis(o<<1),d1=dis(o<<1|1);
        if(d1<=d0){
            _query(o<<1|1,mid+1,r);
            if(lim<=R[o<<1])_query(o<<1,l,mid);
        }else{
            if(lim<=R[o<<1])_query(o<<1,l,mid);
            _query(o<<1|1,mid+1,r);
        }
    }
    int query(int x0,int l){
        return pos=-1,ans=1LL<<60,lim=l,x=x0,_query(1,0,n),pos;
    }
}kdt;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",x+i,b+i),dx[i]=x[i];
    std::sort(dx,dx+1+n);
    kdt.bt(1,0,n);
    for(int i=1,j;i<=n;i++)
    if(j=kdt.query(x[i],b[i]),j!=-1)
    kdt.ins(i,x[i],f[i]=f[j]+sqr(x[i]-x[j]));
    printf("%.4lf\n",sqrt(f[n]));
}
---By n+e
boardmodelpaper.com 说:
2024年1月20日 01:37

A sample or model question paper created by educational boards or other institutions for a variety of exams is commonly referred to as the Board model paper. These practice papers give students a sense of the format, degree of difficulty, and kind of material that may be covered in the real exam, helping them get ready for exams. Typically, model papers are written for particular courses or subjects. They cover boardmodelpaper.com a variety of subjects and chapters that are anticipated to have been studied by students during the course of the semester.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter