Rikka with Cake 【多校9 HDU 6681】【欧拉定理+扫描线】

131 阅读 0 评论 87 点赞

我是靠谱客的博主呆萌自行车，这篇文章主要介绍Rikka with Cake 【多校9 HDU 6681】【欧拉定理+扫描线】，现在分享给大家，希望可以做个参考。

题目链接

题目大意

有一个蛋糕是一个矩形，一个顶点在（0,0）另一个顶点在（n，m），现在对这个蛋糕进行切割，上下左右四个方向切，问最后这个蛋糕有多少块

解题思路

首先这个题的一个结论是：块数=交点数+1

结论证明：根据欧拉定理：如果一个联通平面图 G有 v 个顶点、e 条边、 g 个面，那么
v - e + f = 2
那么：接下来贴个官方题解：
在这里插入图片描述
那么就是如果求c的过程了：
我们把每一个竖线都拆成两个点：（x，y，1）和（x，y，-1）分别表示上下点，横线用（l，r，h）表示，我们把横线和竖线都按照y（h）排序，到竖线的点的时候，把该点的贡献赋给x，到横线的时候，统计（l，r）内有多少个点

复制代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int N=1e5+5;
struct node
{
    int x,y,h,v,id;
    node(){}
    node(int X,int Y,int H,int V,int ID)
    {
        x=X;y=Y;h=H;v=V;id=ID;
    }
};
node e[N*4];
int a[N],t[N*4];
int cmp(node a,node b)
{
    if(a.h==b.h)
        return a.id<b.id;
    return a.h<b.h;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int n,int v)
{
    while(x<=n)
    {
        t[x]+=v;
        x+=lowbit(x);
    }
}
int que(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        char s[5];
        int n,m,k,x,y;
        scanf("%d %d %d",&n,&m,&k);
        int cnt=0,cnt1=0;
        for(int i=1;i<=k;i++)
        {
            scanf("%d %d %s",&x,&y,&s);
            a[++cnt1]=x;
            if(s[0]=='L')
            {
                e[++cnt]=node(0,x,y,0,2);
            }
            else if(s[0]=='R')
            {
                e[++cnt]=node(x,n,y,0,2);
            }
            else if(s[0]=='D')//竖线拆点
             {
                 e[++cnt]=node(x,0,0,1,1);
                e[++cnt]=node(x,y,y,-1,1);
             }
            else
            {e[++cnt]=node(x,y,y,1,1);
                e[++cnt]=node(x,m,m,-1,1);
            }
        }
        a[++cnt1]=0;a[++cnt1]=n;
        sort(e+1,e+1+cnt,cmp);
        sort(a+1,a+cnt1);
        int mm=unique(a+1,a+1+cnt1)-a-1;//离散化
        int ans=0;
        for(int i=1;i<=cnt;i++)
        {
            if(e[i].id==2)//横线统计这个线内的点
            {
                int ll=lower_bound(a+1,a+1+mm,e[i].x)-a-1;
                int rr=lower_bound(a+1,a+1+mm,e[i].y)-a;
                ans+=(que(rr)-que(ll));
            }
            else
            {
                int ll=lower_bound(a+1,a+1+mm,e[i].x)-a;
                update(ll,mm,e[i].v);//竖线把这个点的值加到x轴上去
            }
        }
        printf("%dn",ans+1);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int N=1e5+5;
struct node
{
    int x,y,h,v,id;
    node(){}
    node(int X,int Y,int H,int V,int ID)
    {
        x=X;y=Y;h=H;v=V;id=ID;
    }
};
node e[N*4];
int a[N],t[N*4];
int cmp(node a,node b)
{
    if(a.h==b.h)
        return a.id<b.id;
    return a.h<b.h;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int n,int v)
{
    while(x<=n)
    {
        t[x]+=v;
        x+=lowbit(x);
    }
}
int que(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        char s[5];
        int n,m,k,x,y;
        scanf("%d %d %d",&n,&m,&k);
        int cnt=0,cnt1=0;
        for(int i=1;i<=k;i++)
        {
            scanf("%d %d %s",&x,&y,&s);
            a[++cnt1]=x;
            if(s[0]=='L')
            {
                e[++cnt]=node(0,x,y,0,2);
            }
            else if(s[0]=='R')
            {
                e[++cnt]=node(x,n,y,0,2);
            }
            else if(s[0]=='D')//竖线拆点
             {
                 e[++cnt]=node(x,0,0,1,1);
                e[++cnt]=node(x,y,y,-1,1);
             }
            else
            {e[++cnt]=node(x,y,y,1,1);
                e[++cnt]=node(x,m,m,-1,1);
            }
        }
        a[++cnt1]=0;a[++cnt1]=n;
        sort(e+1,e+1+cnt,cmp);
        sort(a+1,a+cnt1);
        int mm=unique(a+1,a+1+cnt1)-a-1;//离散化
        int ans=0;
        for(int i=1;i<=cnt;i++)
        {
            if(e[i].id==2)//横线统计这个线内的点
            {
                int ll=lower_bound(a+1,a+1+mm,e[i].x)-a-1;
                int rr=lower_bound(a+1,a+1+mm,e[i].y)-a;
                ans+=(que(rr)-que(ll));
            }
            else
            {
                int ll=lower_bound(a+1,a+1+mm,e[i].x)-a;
                update(ll,mm,e[i].v);//竖线把这个点的值加到x轴上去
            }
        }
        printf("%dn",ans+1);
    }
    return 0;
}