注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

USACO 5.5 Picture (picture)  

2009-10-24 14:56:35|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这道题用线段树来解决
以竖直线举例:算法的主要思想是,先将竖线按照x坐标排序(若x相同则矩形左边的竖线排在前面),每次插入一条竖线,将竖线所能覆盖的线段总和与上次的总和的差的绝对值,加入到最终答案里
线段树中每个节点有四个特征int l,r,m,c;分别表示节点左端点,右端点,覆盖的数目,区域内线段和总长度
算法维护m,当c>0时,m=r-l,当c=0时,若节点是叶子节点m=0,否则m=左节点m+有节点m
时间效率比较高,复杂度为o(nlogn)
Test 1: TEST OK [0.022 secs, 4128 KB]
   Test 2: TEST OK [0.011 secs, 4128 KB]
   Test 3: TEST OK [0.011 secs, 4128 KB]
   Test 4: TEST OK [0.011 secs, 4128 KB]
   Test 5: TEST OK [0.000 secs, 4128 KB]
   Test 6: TEST OK [0.011 secs, 4128 KB]
   Test 7: TEST OK [0.043 secs, 4692 KB]
   Test 8: TEST OK [0.011 secs, 4128 KB]
   Test 9: TEST OK [0.043 secs, 4692 KB]
   Test 10: TEST OK [0.011 secs, 4128 KB]
   Test 11: TEST OK [0.043 secs, 4268 KB]
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
struct aa{
       int l,r,m,c;
       bool leaf;
       aa *lp,*rp;
       };
aa *first;
void creat(aa* &p,int l,int r){
     p=new aa;
     p->l=l;
     p->r=r;
     p->c=0;
     p->m=0;
     if(r!=l+1){
       creat(p->lp,l,(l+r)/2);
       creat(p->rp,(l+r)/2,r);
       p->leaf=false;
     }
     else
       p->leaf=true;
}
void init(){
     int l=-10000,r=10000;
     first=new aa;
     first->l=l;
     first->r=r;
     first->c=0;
     first->m=0;
     first->leaf=false;
     creat(first->lp,l,(l+r)/2);
     creat(first->rp,(l+r)/2,r);
}
void add(aa *p,int l,int r,int t){
     if(l<=p->l&&p->r<=r){
       p->c-=t;
       p->m=p->r-p->l;
     }
     else{
          if(l<p->lp->r)
            add(p->lp,l,r,t);
          if(p->rp->l<r)
            add(p->rp,l,r,t);
          }
     if(p->c==0)
         if(p->leaf)
           p->m=0;
         else
           p->m=p->lp->m+p->rp->m;
}
bool compar(int *a,int *b){
     return (a[0]<b[0])||(a[0]==b[0]&&a[3]<b[3]);
}
int main(){
    freopen("picture.in","r",stdin);
    freopen("picture.out","w",stdout);
    scanf("%d",&n);
    int **v=new int *[2*n];
    int **h=new int *[2*n];
    int x1,y1,x2,y2;
    for(int i=0;i<n;i++){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            v[i]=new int[4];
            h[i]=new int[4];
            v[i+n]=new int[4];
            h[i+n]=new int[4];
            v[i][0]=x1;
            v[i][1]=y1;
            v[i][2]=y2;
            v[i][3]=-1;
            h[i][0]=y1;
            h[i][1]=x1;
            h[i][2]=x2;
            h[i][3]=-1;
            v[i+n][0]=x2;
            v[i+n][1]=y1;
            v[i+n][2]=y2;
            v[i+n][3]=1;
            h[i+n][0]=y2;
            h[i+n][1]=x1;
            h[i+n][2]=x2;
            h[i+n][3]=1;
    }
    init();
    sort(v,v+2*n,compar);
    sort(h,h+2*n,compar);
    int ans=0,old;
    for(int i=0;i<2*n;i++){
      old=first->m;
      add(first,v[i][1],v[i][2],v[i][3]);
      ans+=abs(old-first->m);
    }
    for(int i=0;i<2*n;i++){
      old=first->m;
      add(first,h[i][1],h[i][2],h[i][3]);
      ans+=abs(old-first->m);
    }
    printf("%d\n",ans);
}

  评论这张
 
阅读(316)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017