POI 2001 Glodmine 金矿

This post is written in Chinese. Please consider using Google Translate

发现坐标的范围很大,而点并不是很多,首先想到了离散化的方法。然后横向扫描每个带状的区间,对于每个带状区间,再纵向扫描其中点的个数。这种方法是最容易想到的,但是时间复杂度却高达O(N^2logN)。关键在于优化每次确定带状区间的纵向扫描。

显然对于确定的带状区间,我们扫描时只需考虑它们的纵坐标。如果我们把一个纵坐标为y的点描述成两个事件(y,1)和 (y+h+1,-1),然后把所有事件按照第一关键字排序,定义S[i]为前i项事件的第二关键字之和,那么Max{S[i]}就是确定的带状区间内高度 为w的矩形最多覆盖到的点数。为什么是这样,我们可以想象有两个挡板,分别是y=A-h-1(下板)和y=A(上板),从下向上移动挡板,从而确定一个矩 形。某个点的第一个事件为(y,1),当上板A=y时,该点被覆盖,若A继续增大,使得A-h-1=y,该点就恰好离开了覆盖区域,反过来我们可以以为是 A=y+h+1,所以定义第二个事件为(y+h+1,-1)。这样,前i个事件的第二关键字和S[i],就代表了矩形在某个位置时覆盖的点数。S[i]的 最大值就是确定的带状区间内最大的覆盖点数。

带状区间的左右扫描,也可以考虑成两个挡板之间的问题,首先确定挡板的初始位置在最左端,依次向右移动左右两个挡板。确定一个区间后,统 计点事件的最大前缀和成了最关键的问题。由于左右挡板是移动的,我们需要动态统计一个排序结构。于是我们想到了用平衡树,维护每个点事件的第一关键字(y 坐标)升序,并记录权。移动右挡板时,把右挡边新位置所在线上的所有点对应的两个点事件加入平衡树;移动左挡板时,把左挡板时,把左挡边所在线上的所有点 事件从平衡树中删除。

为了快速统计出最大的前缀和,在此基础上,我们还需要对于平衡树中每个节点维护其子树所有节点权值和,以及子树中最大的前缀和。定义p的权值为p.w,以节点p为根的子树的权值和为p.s,以节点p为根的子树的最大的前缀和为p.m,我们可以递推算出p.m的值。

p.m=Max{
    p.left.m; //最大前缀和的尾元素在左子树
    p.left.s+p.w; //最大前缀和的尾元素就是p
    p.left.s+p.w+p.right.m; //最大前缀和的尾元素在右子树
}

于是全部序列的最大前缀和就是根节点root.m。

于是得到的算法如下:

  1. 建立离散化坐标系;
  2. 左右扫描,确定带状区间,维护平衡树中节点;
  3. 统计对于确定带状区间,平衡树中元素最大的前缀和;
算法总的时间复杂度为O(NlogN),可以解决问题了。编程中细节要注意,尤其是在于平衡树维护平衡性时要对节点m值重新计算。我用了 Treap,在插入一个点要旋转时,注意要先重新计算旋转到子树的点的m值,再计算子树根节点的m值。而删除仅仅懒惰删除即可,重要的是维护m值。

/* 
 * Problem: POI2001 kop
 * Author: Guo Jiabao
 * Time: 2009.2.7 16:16
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAXN=15001;
struct point{int x,y;};
struct linknode{int s;linknode *next;};
class Treap_node
{
    public:
        Treap_node *left,*right;
        int fix,weight,sum,m,key;
        Treap_node(int tk,int w):key(tk),weight(w),sum(w),m(w){fix=rand();left=right=0;}
        inline int leftsum (){return left ?left ->sum:0;}
        inline int rightsum(){return right?right->sum:0;}
};

int H,W;//区域高度 宽度
int N,L,Lc=-1,MaxAns;
int D[MAXN];
point P[MAXN];
linknode LS[MAXN],*Line[MAXN];
Treap_node *Treap_root;

void Treap_Rotate_Right(Treap_node *&p)
{
    Treap_node *q=p->left;
    q->sum+=p->rightsum()+p->weight;
    p->sum=q->rightsum()+p->rightsum()+p->weight;
    p->left=q->right;
    q->right=p;
    p=q;
}

void Treap_Rotate_Left(Treap_node *&p)
{
    Treap_node *q=p->right;
    q->sum+=p->leftsum()+p->weight;
    p->sum=q->leftsum()+p->leftsum()+p->weight;
    p->right=q->left;
    q->left=p;
    p=q;
}

void Treap_maintain(Treap_node *&p)
{
    int lm,ls,rm;
    lm=ls=rm=0;
    if (p->left)
        lm=p->left->m,ls=p->left->sum;
    if (p->right)
        rm=p->right->m;
    p->m=lm;
    if (ls + p->weight > p->m)    p->m = ls + p->weight;
    if (ls + p->weight + rm > p->m) p->m=ls + p->weight + rm;
}

void Treap_edit(Treap_node *&p,int v,int delta)
{
    if (!p)
        p=new Treap_node(v,delta);
    else
    {
        if ( v < p->key )
        {
            p->sum+=delta;
            Treap_edit(p->left,v,delta);
            if (p->left && p->left->fix < p->fix)
            {
                Treap_Rotate_Right(p);
                Treap_maintain(p->right);
            }
            Treap_maintain(p);
        }
        else if ( v > p->key )
        {
            p->sum+=delta;
            Treap_edit(p->right,v,delta);
            if (p->right && p->right->fix < p->fix)
            {
                Treap_Rotate_Left(p);
                Treap_maintain(p->left);
            }
            Treap_maintain(p);
        }
        else
        {
            p->weight+=delta;
            p->sum+=delta;
            Treap_maintain(p);
        }
    }
}

void linktable_ins(linknode *&p,int v)
{
    if (p)
    {
        linknode *t=p;
        p=&LS[++Lc];
        p->next=t;
    }
    else
        p=&LS[++Lc];
    LS[Lc].s=v;
}

void init()
{
    freopen("kop.in","r",stdin);
    freopen("kop.out","w",stdout);
    scanf("%d%d%d",&W,&H,&N);
    for (int i=1;i<=N;i++)
        scanf("%d%d",&P[i].x,&P[i].y);
}

inline int cmp(const void *a,const void *b)
{
    return ((point *)a)->x - ((point *)b)->x;
}

void discrete() //离散化横坐标 建立链表
{
    int i,lastv=-1;
    qsort(P+1,N,sizeof(P[0]),cmp);
    L=0;
    for (i=1;i<=N;i++)
    {
        if (P[i].x!=lastv)
        {
            lastv=P[i].x;
            D[++L]=P[i].x;
            linktable_ins(Line[L],P[i].y);
        }
        else
            linktable_ins(Line[L],P[i].y);
    }
}

void RemoveLine(int p)
{
    for (linknode *k=Line[p];k;k=k->next)
    {
        Treap_edit(Treap_root,k->s,-1);
        Treap_edit(Treap_root,k->s+H+1,1);
    }
}

void AddLine(int p)
{
    for (linknode *k=Line[p];k;k=k->next)
    {
        Treap_edit(Treap_root,k->s,1);
        Treap_edit(Treap_root,k->s+H+1,-1);
    }
}


void scanx() //横向扫描 确定区间
{
    int Lb,Rb;
    AddLine(1);
    for (Lb=Rb=1;Rb<L && Lb<=L;)
    {
        while (Rb+1<=L && D[Rb+1]-D[Lb]<=W)
            AddLine(++Rb);
        if (Treap_root->m>MaxAns)
            MaxAns=Treap_root->m;
        RemoveLine(Lb++);
    }
}

void solve()
{
    discrete();
    scanx();
    printf("%d",MaxAns);
}

int main()
{
    init();
    solve();
    return 0;
}
<h2><span class="mw-headline">金矿 </span></h2>

问题描述

金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作,决定在一块包含 n(n ≤ 15000) 个采金点的长方形土地中划出一块长度为 S ,宽度为 W 的区域奖励给他(1 ≤ s , w ≤ 10 000)。老师傅可以自己选择这块地的位置,显然其 中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上,它也应当被计算在内。

输入格式

输入文件的第一行有两个整数,中间用一个空格隔开,表示长方形土地的长和宽即s和w(1&lt;=s,w&lt;=10 000)。第二行有一个整数n(1&lt;=n&lt;=15 000),表示金矿数量。下面的n行与金矿相对应,每行两个整数x和y (-30 000&lt;=x,y&lt;=30 000),中间用一个空格隔开,表示金矿的坐标。

输出格式

输出文件只有一个整数,表示选择的最大金矿的数。

输入样例
1 2
12
0 0
1 1
2 2
3 3
4 5
5 5
4 2
1 4
0 5
5 0
2 3
3 2
输出样例
4

Related posts