2021牛客暑期多校训练营6 H.Hopping Rabbit (矩阵分割,扫描线)

2021牛客暑期多校训练营6 H.Hopping Rabbit (矩阵分割,扫描线)

  • 题意:在二维平面上,分布着很多矩阵,这些矩阵是陷阱,有一只兔子每次固定向四周四个方向跳\(d\)个单位,问你是否存在一个起点,使得兔子无论怎么跳都不跳到陷阱中。

  • 题解:因为兔子固定跳\(d\)个单位,因此具有周期性,也就是说,假如它的起点是\(d\)x\(d\)的矩阵的某一点,那么它无论跳到什么位置,该位置都能和初始矩形平移\(d\)个单位的起点重合.因此对于所有陷阱,我们可以将它们移到\(d\)x\(d\)的矩阵内,然后判断这个矩阵中有没有空的单位即可.问题进而转换成求矩形的面积并,然后就是一个裸的扫描线了。

    2021牛客暑期多校训练营6 H.Hopping Rabbit (矩阵分割,扫描线)

  • 代码:

    #include <bits/stdc++.h>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    #define rep(a,b,c) for(int a=b;a<=c;++a)
    #define per(a,b,c) for(int a=b;a>=c;--a)
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
    
    int n,d;
    struct Segment{
        ll y1,y2;
        int k;
    };
    vector<Segment> seg[N];
    struct Node{
        ll l,r;
        ll cnt;
        ll len;
    }tr[N<<4];
    
    void add(int x1,int y1,int x2,int y2){
        seg[x1].pb({y1,y2,1});
        seg[x2+1].pb({y1,y2,-1});
    }
    
    void push_up(int u){
        if(tr[u].cnt) tr[u].len=tr[u].r-tr[u].l+1;
        else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
        else tr[u].len=0;
    }
    
    void build(int u,int l,int r){
        tr[u].l=l;
        tr[u].r=r;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
    
    void modify(int u,int l,int r,int k){
        if(tr[u].l>=l && tr[u].r<=r){
            tr[u].cnt+=k;
            push_up(u);
            return;
        }
        int mid=(tr[u].l+tr[u].r)>>1;
        if(l<=mid) modify(u<<1,l,r,k);
        if(r>mid) modify(u<<1|1,l,r,k);
        push_up(u);
    }
    
    int query(int u){
        if(tr[u].l==tr[u].r) return tr[u].l;
        int mid=(tr[u].l+tr[u].r)>>1;
        int l_len=mid-tr[u].l+1;
        if(tr[u<<1].len<l_len) return query(u<<1);
        else return query(u<<1|1);    
    }
    
    int main() {
        scanf("%d %d",&n,&d);
        for(int i=1;i<=n;++i){
            int x1,y1,x2,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            x2--,y2--;
            if(x2-x1+1>=d) x1=0,x2=d-1;
            if(y2-y1+1>=d) y1=0,y2=d-1;
            x1=(x1%d+d)%d,x2=(x2%d+d)%d,y1=(y1%d+d)%d,y2=(y2%d+d)%d;
            if(x1<=x2){
                if(y1<=y2){
                    add(x1,y1,x2,y2);
                }
                else{
                    add(x1,0,x2,y2);
                    add(x1,y1,x2,d-1);
                }
            }
            else{
                if(y1<=y2){
                    add(0,y1,x2,y2);
                    add(x1,y1,d-1,y2);
                }
                else{
                    add(0,0,x2,y2);
                    add(x1,y1,d-1,d-1);
                    add(0,y1,x2,d-1);
                    add(x1,0,d-1,y2); 
                }
            }
        }
        build(1,0,d-1);
        for(int i=0;i<d;++i){
            for(auto it:seg[i]){
                modify(1,it.y1,it.y2,it.k);
            }
            if(tr[1].len<d){
                puts("YES");
                printf("%d %d\n",i,query(1));
                return 0;
            }
        }
        puts("NO");
        return 0;
    }
    
    
上一篇:11.盛水最多的容器


下一篇:P1825 玉米田迷宫题解