POJ 2482 扫描线+离散化+线段树 (内容最浪漫的题目)

http://162.105.81.212/JudgeOnline/problem?id=2482

题目大意:

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

HINT:

压在矩形的右边框或下边框的星星不算被框住。

其实一开始把w和h分别减1,然后按矩形处理就可以了。

另外要使用INT64

解题分析:

这个题目可以先把y坐标离散化。然后在Y轴建立线段树,再扫描X轴,动态维护一个关于x坐标的极大范围。然后用线段树维护最大值即可。注意,在Y轴上的插入的线段表示的是把这个范围内的点作为最高点,能够覆盖到星星i。

插曲:

这是GDOI之前老姜要求做的一题。当时看到晕掉了没做,在学校调了一周没调出来,老是WA。最后理清思路,在家重打了一遍,一次编译成功,一次AC。

code:

#include #include #include #include #define L(x) (x)<<1
#define R(x) ((x)<<1)|1
#define MAXN 111111
using namespace std;
struct startype{__int64 x,y,w;}a[MAXN];
struct treetype{__int64 l,r,max,sum;}tr[MAXN*20];
__int64 n,xlen,ylen,yl[MAXN],m,tl[MAXN],toy[MAXN];

void DelSame(){
    m=0;
    for (__int64 i=1;i<=n;i++)
      if (m==0 || tl[m]!=yl[i])
        tl[++m]=yl[i];
    for (__int64 i=1;i<=n;i++) yl[i]=0;
    for (__int64 i=1;i<=m;i++) yl[i]=tl[i];
}

__int64 Find(__int64 k){
    __int64 l=1,r=m,mid;
    while (l        mid=l+r>>1;
        if (yl[mid]                  else r=mid;
    }
    return l;
}

void LiSan(){
    for (__int64 i=1;i<=n;i++)
      yl[i]=a[i].y;
    sort(&yl[1],&yl[n+1]);
    DelSame();
    for (__int64 i=1;i<=n;i++)
      a[i].y=Find(a[i].y);
}

void Build(__int64 p,__int64 l,__int64 r){
    tr[p].l=l; tr[p].r=r; tr[p].max=0; tr[p].sum=0;
    if (l        __int64 mid=l+r>>1;
        Build(L(p),l,mid);
        Build(R(p),mid+1,r);
    }
}

bool cmp(startype t1,startype t2){
    if (t1.x    return false;
}

void Toy(){
    __int64 i,j=0;
    for (i=1;i<=m;i++){
        while (j        toy[i]=j;
    }
}

void ins(__int64 p,__int64 l,__int64 r,__int64 w){
    if (r    if (l<=tr[p].l && tr[p].r<=r){
        tr[p].sum+=w;
        tr[p].max+=w;
        return;
    }
    if (tr[p].sum!=0){
        ins(L(p),0,m,tr[p].sum);
        ins(R(p),0,m,tr[p].sum);
        tr[p].sum=0;
    }
    ins(L(p),l,r,w);
    ins(R(p),l,r,w);
    tr[p].max=max(tr[L(p)].max,tr[R(p)].max);
}

void Work(){
    sort(&a[1],&a[n+1],cmp);
    __int64 i,j=0,ans=0;
    for (i=1;i<=n;i++){
        while (j            j++;
            ins(1,a[j].y,toy[a[j].y],a[j].w);
        }
        ans=max(ans,tr[1].max);
        ins(1,a[i].y,toy[a[i].y],-a[i].w);
    }
    cout << ans << endl;
}

int main(){
    while (cin >> n >> xlen >> ylen){
        xlen–; ylen–;
        for (__int64 i=1;i<=n;i++)
          scanf("%I64d %I64d %I64d",&a[i].x,&a[i].y,&a[i].w);
        LiSan();
        Build(1,1,m);
        Toy();
        Work();
    }
    return 0;
}

POJ 2823 单调队列

题意:

有N个数,每次从左至右选M个数,即[1..M],[2..M+1],…,[M-N+1..N],选取每个区间的最大值和最小值。

解题分析:

明显的单调队列解决,复杂度O(N)

但是却跑了6000+MS。不知道那些500MS的怎么跑出来的。

code:

#include #define N 1000001
using namespace std;

int n,m,a[N],qf[N],qn[N];

void init(){
     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++)
       scanf("%d",&a[i]);
}

void work1(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;
}

void work2(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;

}

int main(){
    init();
    work1();
    work2();
    return 0;
}

HDOJ 1823 二维线段树

http://acm.hdu.edu.cn/showproblem.php?pid=1823 题目是中文的。

题意:

给定一些点对(x,y),和这些点对的权值。求满足(x1<=x<=x2 && y1<=y<=y2)的点里权值最大的一个。

由于小数点只有一个,所以把他*10就可以当整数处理。

解题思路:

标准的二维线段树的应用。建立二维线段树动态维护即可。

收获:

学会了二维线段树,但TLE了好几次。

究其原因,是我以为在#define里定义的max函数和真正的函数是一样的,但实际上是替换而已。

直接调用max(solve(xxxx),solve(xxxx))这样C++会计算两次。导致超时。以后max里不要调用函数。

要调用先用变量存起来。

code:

#include #define L(x) (x)<<1
#define R(x) ((x)<<1)|1
#define round(x) (int)((x)+0.5)
#define max(x,y) (x)>(y)?(x):(y)
struct atype{int l,r;} a[300];
struct btype{int l,r,max;} b[300][3000];

int m;

void swap(double &x,double &y){
     double t;
     t=x; x=y; y=t;
}

void buildy(int p,int x,int l,int r){
     b[x][p].l=l; b[x][p].r=r; b[x][p].max=-1;
     if (l       int mid=l+r>>1;
       buildy(L(p),x,l,mid);
       buildy(R(p),x,mid+1,r);
     }
}

void buildx(int p,int l,int r){
     a[p].l=l; a[p].r=r;
     buildy(1,p,0,1000);
     if (l       int mid=l+r>>1;
       buildx(L(p),l,mid);
       buildx(R(p),mid+1,r);
     }
}

void inserty(int p,int x,int y,int data){
     if (b[x][p].l==b[x][p].r){
       b[x][p].max=max(b[x][p].max,data);
       return;
     }
     if (b[x][p].max==-1){
       b[x][L(p)].max=-1;
       b[x][R(p)].max=-1;
     }
     int mid=b[x][p].l+b[x][p].r>>1;
     if (y<=mid) inserty(L(p),x,y,data);
            else inserty(R(p),x,y,data);
     b[x][p].max=max(b[x][p].max,data);
}

void insertx(int p,int x,int y,int data){
     inserty(1,p,y,data);
     if (a[p].l==a[p].r) return;
     int mid=a[p].l+a[p].r>>1;
     if (x<=mid) insertx(L(p),x,y,data);
            else insertx(R(p),x,y,data);
}

int solvey(int p,int x,int y1,int y2){
    if (y2    if (b[x][p].l>=y1 && y2>=b[x][p].r) return b[x][p].max;
    int t1=solvey(L(p),x,y1,y2),t2=solvey(R(p),x,y1,y2);
    return max(t1,t2);
}

int solvex(int p,int x1,int x2,int y1,int y2){
    if (x1>a[p].r || x2    if (a[p].l>=x1 && x2>=a[p].r) return solvey(1,p,y1,y2);
    int t1=solvex(L(p),x1,x2,y1,y2),t2=solvex(R(p),x1,x2,y1,y2);
    return max(t1,t2);
}

void work(){
     for (int i=1;i<=m;i++){
         char operate;
         scanf("%c",&operate);
         if (operate==’I’){
           int height;
           double A,L;
           scanf("%d %lf %lfn",&height,&A,&L);
           insertx(1,height,round(A*10),round(L*10));
         }
         else{
           double h1,h2,a1,a2;
           scanf("%lf %lf %lf %lfn",&h1,&h2,&a1,&a2);
           if (h1>h2) swap(h1,h2);
           if (a1>a2) swap(a1,a2);
           int ans=solvex(1,round(h1),round(h2),round(a1*10),round(a2*10));
           if (ans==-1) printf("-1n");
                   else printf("%d.%dn",ans/10,ans%10);
         }
     }
}

void init(){
     for (int i=0;i<300;i++) b[i][1].max=-1;
}

int main(){
    buildx(1,100,200);
    for (;;){
        scanf("%dn",&m);
        if (m==0) break;
        init();
        work();
    }
    return 0;
}