HDU 1828 && POJ 1177 Picture(线段树+扫描线+离散化） - c++编程基础

TOP

HDU 1828 && POJ 1177 Picture(线段树+扫描线+离散化）

2015-07-20 17:55:48 来源: 作者: 【大中小】浏览:8次

HDU题目地址：HDU 1828 POJ题目地址：POJ 1177

这题是求周长并，我用的方法可能有点麻烦。。是先求横着的线，再求竖着的线。每次只要求出每次的总区间覆盖长度，然后每次累加这次的总区间覆盖与上次的总区间覆盖长度的差的绝对值。因为只有长度发生变化时，才会产生一段新的周长。

待会再试试只扫描一次的方法。此博客有待更新。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 int sum[50000], c[50000], cnt, a[6000], b[5000], d1[6000], d2[6000], lazy[50000]; struct node { int l, r, h, f; } edge[100000]; void add(int l, int r, int h, int f) { edge[cnt].l=l; edge[cnt].r=r; edge[cnt].h=h; edge[cnt++].f=f; } int cmp(node x, node y) { return x.h
             
              =r) { lazy[rt]+=x; PushUp(rt,l,r); return ; } int mid=l+r>>1; if(ll<=mid) update(ll,rr,x,lson); if(rr>mid) update(ll,rr,x,rson); PushUp(rt,l,r); } int erfen(int x, int high) { int low=0, mid; while(low<=high) { mid=low+high>>1; if(c[mid]==x) return mid; else if(c[mid]>x) high=mid-1; else low=mid+1; } } int main() { int n, i, j, last, ans, tmp, k; while(scanf("%d",&n)!=EOF) { cnt=0; k=0; memset(sum,0,sizeof(sum)); memset(lazy,0,sizeof(lazy)); for(i=0; i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1231 最大连续子序列 DP题解	下一篇：hdu1828 Picture(线段树+离散化+..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: