2011-0012

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这题是POJ2482的加强版(原题内容极度浪漫=_=)。[[BR]]
原题题意是给定一个W*H的矩形，再给出一些在平面直角坐标系里的星星，每个星星有一个亮度，求用这个矩形去框住一些星星，使得框内的星星亮度之和最大。[[BR]]
坐标范围很大，于是先离散化，对y坐标建立线段树，直接枚举矩形的右边框在哪，然后左边框最左可以去到哪里。就已经确定了。而且这两个指针都是单调滑动的。[[BR]]
然后现在的问题转化为找一个长度为H的区间，里面星星的和最大。假如没有离散化之前，我们完全可以令Sum[i]表示纵坐标从i-H ... i的星星的亮度之和，然后在插入和删除点的时候维护这个Sum[i](可以发现插入一个点y以后Sum[y]..Sum[y+H]都变化相应的值，所以可以用线段树来维护).[[BR]]
现在离散化以后要变换一下，但是本质上也是差不多。[[BR]]
回到本题，三维情况的话，直接枚举其中一维，然后套用上面那个模型就行了。本题猛犸学长很厚道地给了非常小的坐标范围([-1000,1000])，所以不用离散化，直接上线段树就行了。[[BR]]
附上巨搓代码：[[BR]]
{{{

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int N=1005;
const int INF=0x7FFFFFFF;
int ans;

struct SGT{
       struct Node{int l,r,Min,delta;}Tr[2048*6];

       void build(int p,int l,int r){
            Tr[p].l=l; Tr[p].r=r; Tr[p].Min=0; Tr[p].delta=0;
            if (l==r) return;
            int mid=(l+r)/2;
            build(p*2,l,mid);
            build(p*2+1,mid+1,r);
       }

       void add(int p,int l,int r,int delta){
            if (l<=Tr[p].l && Tr[p].r<=r){
               Tr[p].delta+=delta;
               return;
            }
            Tr[p*2].delta+=Tr[p].delta;
            Tr[p*2+1].delta+=Tr[p].delta;
            Tr[p].delta=0;
            int mid=(Tr[p].l+Tr[p].r)/2;
            if (l<=mid) add(p*2,l,r,delta);
            if (r> mid) add(p*2+1,l,r,delta);
            Tr[p].Min=min(Tr[p*2].Min+Tr[p*2].delta,Tr[p*2+1].Min+Tr[p*2+1].delta);
       }

       int Get_Min(){ return Tr[1].Min+Tr[1].delta; }
}Tree;

struct Node_2{ int x,y,s; };
bool cmp2(Node_2 A,Node_2 B){
     return A.x<B.x;
}

struct GaoClass{
       int n,m,Lx,Ly;
       Node_2 P[N];
       void add(int x,int y,int s){ n++; P[n].x=x; P[n].y=y; P[n].s=s; }
       void checkmin(int &t,int x){ if (x<t) t=x; }
       void Insert(int i){ Tree.add(1,P[i].y,min(2000,P[i].y+Ly),P[i].s); }
       void Delete(int i){ Tree.add(1,P[i].y,min(2000,P[i].y+Ly),-P[i].s); }

       void gao(){
            sort(P+1,P+n+1,cmp2);
            Tree.build(1,0,2000);
            int j=1;
            for (int i=1;i<=n;i++){
                Insert(i);
                while (P[i].x-P[j].x>Lx) Delete(j++);
                checkmin(ans,Tree.Get_Min());
            }
       }
}Gao;

int n;
int La,Lb,Lc;
struct Node{int a,b,c,s;};
vector <Node> P;

Node make_Node(int a,int b,int c,int s){ Node ret; ret.a=a; ret.b=b; ret.c=c; ret.s=s; return ret; }

bool cmp(Node A,Node B){    return A.a<B.a;     }

int main(){
    while (scanf("%d",&n)!=EOF){
          P.clear();
          for (int i=0;i<n;i++){
              int a,b,c,s;
              scanf("%d%d%d%d",&a,&b,&c,&s);
              a+=1000; b+=1000; c+=1000;
              if (s<0) P.push_back(make_Node(a,b,c,s));
          }
          n=P.size();
          scanf("%d%d%d",&La,&Lb,&Lc);
          Gao.Lx=Lb;
          Gao.Ly=Lc;
          sort(P.begin(),P.end(),cmp);
          ans=0;
          for (int i=0;i<n;i++){
              Gao.n=0;
              for (int j=i;j<n && P[j].a-P[i].a<=La;j++) Gao.add(P[j].b,P[j].c,P[j].s);
              Gao.gao();
          }
          if (ans<0) printf("%d\n",ans);
                else printf("Error 404, mahou shoujo not found!\n");
    }
}

}}}

By edward_mj

这题是POJ2482的加强版(原题内容极度浪漫=_=)。

原题题意是给定一个W*H的矩形，再给出一些在平面直角坐标系里的星星，每个星星有一个亮度，求用这个矩形去框住一些星星，使得框内的星星亮度之和最大。

坐标范围很大，于是先离散化，对y坐标建立线段树，直接枚举矩形的右边框在哪，然后左边框最左可以去到哪里。就已经确定了。而且这两个指针都是单调滑动的。

然后现在的问题转化为找一个长度为H的区间，里面星星的和最大。假如没有离散化之前，我们完全可以令Sum[i]表示纵坐标从i-H ... i的星星的亮度之和，然后在插入和删除点的时候维护这个Sum[i](可以发现插入一个点y以后Sum[y]..Sum[y+H]都变化相应的值，所以可以用线段树来维护).

现在离散化以后要变换一下，但是本质上也是差不多。

回到本题，三维情况的话，直接枚举其中一维，然后套用上面那个模型就行了。本题猛犸学长很厚道地给了非常小的坐标范围([-1000,1000])，所以不用离散化，直接上线段树就行了。

附上巨搓代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int N=1005;
const int INF=0x7FFFFFFF;
int ans;
struct SGT{
       struct Node{int l,r,Min,delta;}Tr[2048*6];
       void build(int p,int l,int r){
            Tr[p].l=l; Tr[p].r=r; Tr[p].Min=0; Tr[p].delta=0;
            if (l==r) return;
            int mid=(l+r)/2;
            build(p*2,l,mid);
            build(p*2+1,mid+1,r);
       }
       void add(int p,int l,int r,int delta){
            if (l<=Tr[p].l && Tr[p].r<=r){
               Tr[p].delta+=delta;
               return;
            }
            Tr[p*2].delta+=Tr[p].delta;
            Tr[p*2+1].delta+=Tr[p].delta;
            Tr[p].delta=0;
            int mid=(Tr[p].l+Tr[p].r)/2;
            if (l<=mid) add(p*2,l,r,delta);
            if (r> mid) add(p*2+1,l,r,delta);
            Tr[p].Min=min(Tr[p*2].Min+Tr[p*2].delta,Tr[p*2+1].Min+Tr[p*2+1].delta);
       }
       int Get_Min(){ return Tr[1].Min+Tr[1].delta; }
}Tree;
struct Node_2{ int x,y,s; };
bool cmp2(Node_2 A,Node_2 B){
     return A.x<B.x;
}
struct GaoClass{
       int n,m,Lx,Ly;
       Node_2 P[N];
       void add(int x,int y,int s){ n++; P[n].x=x; P[n].y=y; P[n].s=s; }
       void checkmin(int &t,int x){ if (x<t) t=x; }
       void Insert(int i){ Tree.add(1,P[i].y,min(2000,P[i].y+Ly),P[i].s); }
       void Delete(int i){ Tree.add(1,P[i].y,min(2000,P[i].y+Ly),-P[i].s); }
       void gao(){
            sort(P+1,P+n+1,cmp2);
            Tree.build(1,0,2000);
            int j=1;
            for (int i=1;i<=n;i++){
                Insert(i);
                while (P[i].x-P[j].x>Lx) Delete(j++);
                checkmin(ans,Tree.Get_Min());
            }
       }
}Gao;
int n;
int La,Lb,Lc;
struct Node{int a,b,c,s;};
vector <Node> P;
Node make_Node(int a,int b,int c,int s){ Node ret; ret.a=a; ret.b=b; ret.c=c; ret.s=s; return ret; }
bool cmp(Node A,Node B){    return A.a<B.a;     }
int main(){
    while (scanf("%d",&n)!=EOF){
          P.clear();
          for (int i=0;i<n;i++){
              int a,b,c,s;
              scanf("%d%d%d%d",&a,&b,&c,&s);
              a+=1000; b+=1000; c+=1000;
              if (s<0) P.push_back(make_Node(a,b,c,s));
          }
          n=P.size();
          scanf("%d%d%d",&La,&Lb,&Lc);
          Gao.Lx=Lb;
          Gao.Ly=Lc;
          sort(P.begin(),P.end(),cmp);
          ans=0;
          for (int i=0;i<n;i++){
              Gao.n=0;
              for (int j=i;j<n && P[j].a-P[i].a<=La;j++) Gao.add(P[j].b,P[j].c,P[j].s);
              Gao.gao();
          }
          if (ans<0) printf("%d\n",ans);
                else printf("Error 404, mahou shoujo not found!\n");
    }
}

By edward_mj