@zzzc18 2017-10-23T08:11:04.000000Z 字数 3038 阅读 1007

# 2017.10.23 NOIP 模拟赛

TEST

## Problem

problem.pdf276.9kB

## Solution

### T1

#### 法一：

$x_j-w_j \geq x_i+w_i(j>i)$此时，又可以发现$x_j+w_j > x_i+w_i(j>i)$

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN = 400000+9;int n;struct PAIR{    int loc,val;}num[MAXN];int b[MAXN];int len;int ans=1;struct T{    int ls,rs,left_range,right_range;    int val;}tree[MAXN*4];int cnt;int lazy[MAXN*4];bool cmp(const PAIR &A,const PAIR &B){    return A.loc<B.loc;}void update(int x){    tree[x].val=max(tree[tree[x].ls].val,tree[tree[x].rs].val);}void pushdown(int x){    if(lazy[x]==0)return;    if(tree[x].ls){        tree[tree[x].ls].val=max(tree[tree[x].ls].val,lazy[x]);        lazy[tree[x].ls]=max(lazy[tree[x].ls],lazy[x]);    }    if(tree[x].rs){        tree[tree[x].rs].val=max(tree[tree[x].rs].val,lazy[x]);        lazy[tree[x].rs]=max(lazy[tree[x].rs],lazy[x]);    }    lazy[x]=0;}int Build(int l,int r){    int now=++cnt;    tree[now].left_range=l;    tree[now].right_range=r;    if(l==r){        tree[now].val=0;        return now;    }    int mid=(l+r)>>1;    tree[now].ls=Build(l,mid);    tree[now].rs=Build(mid+1,r);    update(now);    return now;}int getmax(int k,int l,int r){    pushdown(k);    if(l<=tree[k].left_range && tree[k].right_range<=r){        return tree[k].val;    }    int mid=tree[k].left_range + tree[k].right_range >> 1;    int re=0;    if(l<=mid)re=max(re,getmax(tree[k].ls,l,r));    if(r>=mid+1)re=max(re,getmax(tree[k].rs,l,r));    update(k);    return re;}void modify(int k,int pos,int val){    pushdown(k);    if(tree[k].left_range==tree[k].right_range){        tree[k].val=val;        lazy[k]=val;        return;    }    int mid=tree[k].left_range + tree[k].right_range >> 1;    if(pos<=mid)modify(tree[k].ls,pos,val);    else modify(tree[k].rs,pos,val);    update(k);}void solve(){    Build(1,len);    for(int i=1;i<=n;i++){        int pos=lower_bound(b+1,b+len+1,num[i].loc-num[i].val)-b;        int tmp=getmax(1,1,pos);        ans=max(ans,tmp+1);        pos=lower_bound(b+1,b+len+1,num[i].loc+num[i].val)-b;        modify(1,pos,tmp+1);    }    printf("%d\n",ans);}int main(){    freopen("clique.in","r",stdin);    freopen("clique.out","w",stdout);    scanf("%d",&n);    int i;    for(i=1;i<=n;i++){        scanf("%d%d",&num[i].loc,&num[i].val);    }    sort(num+1,num+n+1,cmp);    int tmp=0;    for(i=1;i<=n;i++){        b[++tmp]=num[i].loc-num[i].val;        b[++tmp]=num[i].loc+num[i].val;    }    sort(b+1,b+tmp+1);    len=unique(b+1,b+tmp+1)-(b+1);    solve();    return 0;}

#### 法二：

#include<cstdio>#include<algorithm>using namespace std;int n,x[200100],w[200100],ans,to;struct MU{    int l,r;}a[200100];bool cmp(MU u,MU v){    if(u.r==v.r)        return u.l<v.l;    return u.r<v.r;}int main(){    freopen("clique.in","r",stdin);    freopen("clique.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++) {        scanf("%d%d",&x[i],&w[i]);        a[i].l=x[i]-w[i];a[i].r=x[i]+w[i];    }    sort(a+1,a+n+1,cmp);    ans=1;to=a[1].r;    for(int i=2;i<=n;i++){        if(a[i].l>=to){            ans++;to=a[i].r;        }    }    printf("%d\n",ans);    fclose(stdin);fclose(stdout);return 0;}

### T2

$O(n\ log^2n)$

• 私有
• 公开
• 删除