LOJ白金元首与克劳德斯

题面

思路

本题偏向思维吧,需要注意一点,开始时所有云都是没有重叠面积且速度相同的,所以往同一方向的云都是相对静止的,并且云的速度方向只有向右和向上,这样就给了我们一个十分优秀的性质–只有向上与向右的云才会重叠,并且最多一个位置只能被两朵云覆盖,最少一朵云,所以只需要判断任意一朵的向右的云是否将会与向上的相交即可,设向右的云有$n$朵,向上的云有$m$朵,那么$n*m$的做法已经不难想出了,但明显是无法拿满分的,需要优化。这时我们或许会想起初中科学老师的教导相对运动这一概念,我们把向上的云固定住,向右的云就变成了向右下$45度$角运动,这样它的右上角和左下角会与$x$轴有交点,然后我们对于一种方向的云他的右上角和左下角的连线映射到$x$轴上,然后对另一种方向的云判断是否有一条线段会与它重叠即可,可以用差分,线段树,排序,二分做。在这里我用的是标记永久化线段树。

细节

因为边缘不算,所以要对一种运动的矩形的对角线在$x$轴上左开右开,对另一种运动的矩形的对角线的查询要左闭右闭,然后离散化。

代码

个人觉得这篇题解写得不大好,还望各位通过代码理解。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
struct node{int l,r,opt;}seg[100005];
int tmp[200005],top=0,T,n;
void Read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
struct Tree
{
    int tree[800005],mark[800005];
    void add(int rt,int l,int r,int ql,int qr)
    {
        if (l>=ql&&r<=qr) {mark[rt]+=1;return;}
        tree[rt]+=min(qr,r)-max(ql,l)+1;
        int mid=l+r>>1;
        if (ql<=mid) add(rt<<1,l,mid,ql,qr);
        if (qr>mid) add(rt<<1|1,mid+1,r,ql,qr);
    }   
    int ask(int rt,int l,int r,int ql,int qr)
    {
        if (l>qr||r<ql) return 0;
        if(l>=ql&&r<=qr) return tree[rt]+(r-l+1)*mark[rt];
        int mid=l+r>>1;
        int res=(min(qr,r)-max(ql,l)+1)*mark[rt];
        if (ql<=mid) res+=ask(rt<<1,l,mid,ql,qr);
        if (qr>mid) res+=ask(rt<<1|1,mid+1,r,ql,qr);
        return res;
    }
}S;
int main()
{
    Read(T);
    while(T--)
    {
        top=0;
        memset(seg,0,sizeof(seg));
        memset(tmp,0,sizeof(tmp));
        memset(S.tree,0,sizeof(S.tree));
        memset(S.mark,0,sizeof(S.mark));
        Read(n);
        for (int i=1;i<=n;i++)
        {
            int x,y,w,h,d;
            Read(x),Read(y),Read(w),Read(h),Read(d);
            if (d==1) seg[i].l=x+y+1,seg[i].r=x+y+w+h-1;
            if (d==0) seg[i].l=x+y,seg[i].r=x+y+w+h;
            seg[i].opt=d;
            if (d==1) tmp[++top]=x+y+1,tmp[++top]=x+y+w+h-1;
            if (d==0) tmp[++top]=x+y,tmp[++top]=x+y+w+h;
        }
        sort(tmp+1,tmp+top+1);
        int cnt=unique(tmp+1,tmp+top+1)-tmp-1;
        for (int i=1;i<=n;i++)
        {
            seg[i].l=lower_bound(tmp+1,tmp+cnt+1,seg[i].l)-tmp;
            seg[i].r=lower_bound(tmp+1,tmp+cnt+1,seg[i].r)-tmp;
            if (seg[i].opt==0) S.add(1,1,cnt,seg[i].l,seg[i].r);
        }
        bool flag=0;
        for (int i=1;i<=n;i++) 
        if (seg[i].opt==1) 
        if (S.ask(1,1,cnt,seg[i].l,seg[i].r)>0) 
        {
            cout<<2<<endl;
            flag=1;
            break;
        } 
        if (!flag) cout<<1<<endl;
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇