2017.10.23 NOIP 模拟赛

TEST

Problem

problem.pdf276.9kB

好久没动博客了。。。

Solution

T1

两种做法

法一：

先按出现的位置排序然后连边的条件就可以改为$x_j-x_i \geq w_j+w_i(j>i)$
即$x_j-w_j \geq x_i+w_i(j>i)$此时，又可以发现$x_j+w_j > x_i+w_i(j>i)$
所以每次我们查询对于$x_j-w_j$满足$x_j-w_j \geq x_i+w_i(j>i)$的所有 $i$ 里的最大团大小(最大团最后加入的点应该是 $i$)
由于$x_j+w_j > x_i+w_i(j>i)$可知，这个满足条件的 $i$ 对应的最大团可以把 $j$ 加进去，最大团大小变大
具体怎么实现，就是一个权值线段树，存团的大小

#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;
}

法二：

好了，以上方法说明我弱智
将点$x_i,w_i$看成区间$xi-wi,xi+w_i$(因为 $w_i>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

其实，因为 $a\ mod\ b <\large{\frac{a}{2}}$
可以直接用线段树进行暴力修改，维护区间最值与区间和，区间取模时，线段树内操作时，如果当区间的最大值为 $0$ 、$1$ 或 小于取模的值时，可以直接$return$
考试的时候觉得这太坑没写，直接交了个40pts暴力
$O(n\ log^2n)$

T3

坑