【考前冲刺Day1】天神下凡

题面

我们先来看看样例：

首先一开始就有一个区域；
一般来说，一个圆对答案的贡献为1，无论它是在外面还是在其他圆的里面。
但是，如果一个圆它的一条直径上所有的点都被覆盖了的话，它对答案的贡献就为2了
由于只能在x轴上安放，覆盖的情况我们也只要考虑x轴上的，所以就可以把这个问题抽象为一个线段覆盖问题。
首先将所有的线段离散化一下，再根据长度排序，对于每条线段，先查询它是不是被全部覆盖了，再用它来更新覆盖的区域，可以用线段树来维护。

考试的时候思路完全一致，就是线段树空间没有开够一定要开八倍空间！！！！，建树的时候也要从1到2*n

这种想法虽然很自然，但是代码又长，空间又大，时间又长，还容易写挂，先膜一波考试时A的大佬@Enstein用的是神奇的栈，@千柰用的是搜索……代码比我短，空间比我小，还更快，tql

代码

#include<bits/stdc++.h> 
#define lt p<<1
#define rt p<<1|1
using namespace std;
const int MAXN =300005;
struct seg{
    int l,r;
    int len;
}s[MAXN];
int n,cnt,ans=1;
struct node{
    int pos,id;
}point[MAXN<<1];

struct segtree{
    int l,r;
    int data,tag;
}t[MAXN<<3];//8倍空间！！！

bool cmp(node a,node b){
    return a.pos<b.pos;
}

bool cmp2(node a,node b){
    if(a.id==b.id)return a.pos<b.pos;
    return a.id<b.id;
}

bool cmp3(seg a,seg b){
    if(a.len==b.len)return a.l<b.l;
    return a.len<b.len;
}

void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    build(lt,l,mid);
    build(rt,mid+1,r);
}

void spread(int p){//加了并不会快多少
    if(t[p].tag){
        t[lt].data=t[lt].r-t[lt].l+1;
        t[rt].data=t[rt].r-t[rt].l+1;
        t[lt].tag=1;
        t[rt].tag=1;
        t[p].tag=0;
    }
}

void change(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].data=t[p].r-t[p].l+1;
        t[p].tag=1;
        return;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(mid>=l)change(lt,l,r);
    if(mid<r)change(rt,l,r);
    t[p].data=t[lt].data+t[rt].data;
}

int ask(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].data;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    int sum=0;
    if(mid>=l)sum+=ask(lt,l,r);
    if(mid<r)sum+=ask(rt,l,r);
    return sum;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x,r;scanf("%d%d",&x,&r);
        point[++cnt].pos=x-r;point[cnt].id=cnt;
        point[++cnt].pos=x+r;point[cnt].id=cnt;
    }
    sort(point+1,point+1+cnt,cmp);
    for(int i=1,j=1,last=-1;i<=cnt;i++){
        if(i!=1&&point[i].pos!=last)j++;
        last=point[i].pos;
        point[i].pos=j;
    }
    sort(point+1,point+1+cnt,cmp2);
    cnt=0;
    for(int i=1;i<=n;i++){
        s[i].l=point[++cnt].pos;
        s[i].r=point[++cnt].pos;
        s[i].len=s[i].r-s[i].l+1;
    }
    sort(s+1,s+1+n,cmp3);
    build(1,1,n*2); //从1到2n
    for(int i=1;i<=n;i++){
        ans++;
        if(ask(1,s[i].l,s[i].r)==s[i].len)ans++;
        change(1,s[i].l,s[i].r);
    }
    cout<<ans<<endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

#include<bits/stdc++.h>

#define lt p<<1

#define rt p<<1|1

using namespace std;

const int MAXN =300005;

struct seg{

int l,r;

int len;

}s[MAXN];

int n,cnt,ans=1;

struct node{

int pos,id;

}point[MAXN<<1];

struct segtree{

int l,r;

int data,tag;

}t[MAXN<<3];//8倍空间！！！

bool cmp(node a,node b){

return a.pos<b.pos;

}

bool cmp2(node a,node b){

if(a.id==b.id)return a.pos<b.pos;

return a.id<b.id;

}

bool cmp3(seg a,seg b){

if(a.len==b.len)return a.l<b.l;

return a.len<b.len;

}

void build(int p,int l,int r){

t[p].l=l,t[p].r=r;

if(l==r){

return;

}

int mid=(l+r)>>1;

build(lt,l,mid);

build(rt,mid+1,r);

}

void spread(int p){//加了并不会快多少

if(t[p].tag){

t[lt].data=t[lt].r-t[lt].l+1;

t[rt].data=t[rt].r-t[rt].l+1;

t[lt].tag=1;

t[rt].tag=1;

t[p].tag=0;

}

void change(int p,int l,int r){

if(t[p].l>=l&&t[p].r<=r){

t[p].data=t[p].r-t[p].l+1;

t[p].tag=1;

return;

}

spread(p);

int mid=(t[p].l+t[p].r)>>1;

if(mid>=l)change(lt,l,r);

if(mid<r)change(rt,l,r);

t[p].data=t[lt].data+t[rt].data;

}

int ask(int p,int l,int r){

if(t[p].l>=l&&t[p].r<=r){

return t[p].data;

}

spread(p);

int mid=(t[p].l+t[p].r)>>1;

int sum=0;

if(mid>=l)sum+=ask(lt,l,r);

if(mid<r)sum+=ask(rt,l,r);

return sum;

}

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++){

int x,r;scanf("%d%d",&x,&r);

point[++cnt].pos=x-r;point[cnt].id=cnt;

point[++cnt].pos=x+r;point[cnt].id=cnt;

}

sort(point+1,point+1+cnt,cmp);

for(int i=1,j=1,last=-1;i<=cnt;i++){

if(i!=1&&point[i].pos!=last)j++;

last=point[i].pos;

point[i].pos=j;

}

sort(point+1,point+1+cnt,cmp2);

cnt=0;

for(int i=1;i<=n;i++){

s[i].l=point[++cnt].pos;

s[i].r=point[++cnt].pos;

s[i].len=s[i].r-s[i].l+1;

}

sort(s+1,s+1+n,cmp3);

build(1,1,n*2); //从1到2n

for(int i=1;i<=n;i++){

ans++;

if(ask(1,s[i].l,s[i].r)==s[i].len)ans++;

change(1,s[i].l,s[i].r);

}

cout<<ans<<endl;

return 0;

}

Naoh

6年前

2018-11-03 19:02:17

吧吧吧哩吧

千奈

6年前

2018-11-03 16:32:31

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n, v[300001];
struct node{
    long long l, r;
}a[300001];
long long cnt=1;

void dfs(int x,int y,int num){
    v[x]=1;
    cnt+=1;
    if(num==1){
        if(a[x].l!=a[x+1].l)return;
        dfs(x+1,x,2);
    }
    else{
        if(a[x].r==a[y].r){
            cnt+=1;
            return;
        }
        if(a[x].r==a[x+1].l){
            dfs(x+1,y,2);
            return;
        }
        else{
            if(a[x].l==a[x+1].l){
                cnt-=1;
                dfs(x,0,1);
                int t=x+1;
                while(a[t].l<a[x].r)t++;
                if(a[t].l==a[x].r)dfs(t,y,2);
                else return;
            }
            else return;
        }
    }

}

bool cmp(node a,node b){
    if(a.l==b.l)return a.r>b.r;
    return a.l<b.l;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long x,ri;
        scanf("%lld%lld",&x,&ri);
        a[i].l=x-ri,a[i].r=x+ri;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(!v[i])dfs(i,0,1);
    }
    printf("%lld",cnt);
    return 0;
}

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

int n, v[300001];

struct node{

long long l, r;

}a[300001];

long long cnt=1;

void dfs(int x,int y,int num){

v[x]=1;

cnt+=1;

if(num==1){

if(a[x].l!=a[x+1].l)return;

dfs(x+1,x,2);

}

else{

if(a[x].r==a[y].r){

cnt+=1;

return;

}

if(a[x].r==a[x+1].l){

dfs(x+1,y,2);

return;

}

else{

if(a[x].l==a[x+1].l){

cnt-=1;

dfs(x,0,1);

int t=x+1;

while(a[t].l<a[x].r)t++;

if(a[t].l==a[x].r)dfs(t,y,2);

else return;

}

else return;

}

bool cmp(node a,node b){

if(a.l==b.l)return a.r>b.r;

return a.l<b.l;

}

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++){

long long x,ri;

scanf("%lld%lld",&x,&ri);

a[i].l=x-ri,a[i].r=x+ri;

}

sort(a+1,a+1+n,cmp);

for(int i=1;i<=n;i++){

if(!v[i])dfs(i,0,1);

}

printf("%lld",cnt);

return 0;

}

冒泡ioa 博主

6年前
2018-11-03 16:36:15

%%% tql

发送评论编辑评论

代码

评论

发送评论 编辑评论

发送评论编辑评论