hdu6681 Rikka with Cake


题目大意:

给出$k$条射线 求能使$n*m$的矩形分成多少个块

题解:

由于是射线 所以所以每个一个交点都能产生贡献 最后的答案就是总交点数+1

那如何去维护呢 我们可以把$k$条射线按横纵来考虑 对于竖的射线 假如为$U$ 那么$[y,m]$便被覆盖 假如为$D$ 那么$[0,y]$便被覆盖 对于这样的线段可以考虑用树状数组去维护 我们考虑一个扫描线从下到上的扫过去 假如当前扫到了$y$ 那么便执行操作$add(x,val)$ 对于一个向下的射线 我们可以当扫描线在$0$时$add(x,val)$ 当扫描线在$y+1$时 $add(x,-val)$ 其中$val=1$ 假如我们扫描线当前遇到了横线的话 就直接查询从$L-R$覆盖的线段即可 由于$x$范围很大但是$k$很小 所以我们可以对$x$坐标离散化

AC代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=200050;
int T;
int n,m,k;
int c[maxn],h[maxn],num,tot;
struct node{
    int p,l,r,pos,val;
    bool operator<(const node&t) const{
        if(pos==t.pos) return p>t.p; return pos<t.pos;
    }
}a[maxn];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int ha(int x){return lower_bound(h+1,h+tot+1,x)-h;}
int lowbit(int x){return x&-x;}
void add(int x,int p)
{
    while(x<=tot)
    {
        c[x]+=p;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int main()
{
    T=read();
    while(T--)
    {
        memset(c,0,sizeof(c));
        num=0,tot=0;
        n=read(),m=read(),k=read();
        for(int i=1;i<=k;i++)
        {
            int x,y;x=read(),y=read();
            char opt[2];cin>>opt;
            if(opt[0]=='U')
            {
                a[++num]={1,x,y,y,1};
                h[++tot]=x;
            }
            else if(opt[0]=='D')
            {
                a[++num]={1,x,0,0,1};
                a[++num]={1,x,y+1,y+1,-1};
                h[++tot]=x;
            }
            else if(opt[0]=='L')
            {
                a[++num]={0,0,x,y,0};
                h[++tot]=x;
            }
            else
            {
                a[++num]={0,x,n,y,0};
                h[++tot]=x;
            }
            //cout<<x<<" "<<y<<endl;
        }
        h[++tot]=0;h[++tot]=n;
        sort(h+1,h+tot+1);
        tot=unique(h+1,h+tot+1)-(h+1);
        sort(a+1,a+num+1);
        int ans=0;
        for(int i=1;i<=num;i++)
        {
            if(a[i].p==1)
            {
                add(ha(a[i].l),a[i].val);
            }
            else ans+=query(ha(a[i].r))-query(ha(a[i].l)-1);
        }
        cout<<ans+1<<endl;
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1207C Gas Pipeline CF1207C Gas Pipeline
题目大意:给定一个二进制01串 为1代表这个地方需要是高度为2的柱子 为0代表可以为高度为1或者2的柱子。起点和终点柱子高度都为必须1 同时横向走的时候需要管道 柱子的单位花费是b 管道的单位花费是a 从1到2还需要额外的a花费 问怎么安排
2019-08-24
下一篇 
数论基础学习笔记1 数论基础学习笔记1
1. 质数1.1 试除法判定$n$是否为质数int is_prime(int n) { if(n<2) return false; for(int i=2;i<=n/i;i++) if(n%i==0) r
  目录