NOIP2017提高组 模拟赛20(总结)

时间:2022-07-02 19:19:17

NOIP2017提高组 模拟赛20(总结)

第一题 配对 (边双连通分量)

【题目描述】

【解题思路】

NOIP2017提高组 模拟赛20(总结)
  边双我还没写好,用LCT水过的(数据太弱,其实是WA的方法,会被卡)

【代码】

#include<cstdio>
#include<algorithm>

using namespace std;

const int N=100500;
int n,m,Q,cnt;
struct tree
{
    tree *f,*c[2],*pp;
    int siz;
    bool lz,val,isn,bl;
    bool flip;
    int d() { return (f->c[1]==this); }
    void sc(tree *x,int d) { (c[d]=x)->f=this; }
} nil[N<<1],*ro[N<<1],*stack[N<<1];
int A[N],B[N],dc;
bool vis[N];
int f[N];

void down(tree *x)
{
    if(x==nil) return;
    if(x->flip)
    {
        x->flip=0;
        swap(x->c[0],x->c[1]);
        if(x->c[0]!=nil) x->c[0]->flip^=1;
        if(x->c[1]!=nil) x->c[1]->flip^=1;
    }
    if(x->lz)
    {
        if(x->c[0]!=nil)
        {
            x->c[0]->lz=1;
            if(x->c[0]-nil>n) x->c[0]->val=1;
            if(x->bl) x->c[0]->isn=1;
        }
        if(x->c[1]!=nil)
        {
            x->c[1]->lz=1;
            if(x->c[1]-nil>n) x->c[1]->val=1;
            if(x->bl) x->c[1]->isn=1;
        }
        x->lz=0;
    }
}

void up(tree *x)
{
    if(x==nil) return;
    x->siz=1; x->isn=x->val; x->bl=(x-nil)>n;
    if(x->c[0]!=nil) x->siz+=x->c[0]->siz,x->isn|=x->c[0]->isn,x->bl|=x->c[0]->bl;
    if(x->c[1]!=nil) x->siz+=x->c[1]->siz,x->isn|=x->c[1]->isn,x->bl|=x->c[1]->bl;
}

tree *newtree()
{
    nil->pp=nil->c[0]=nil->c[1]=nil->f=nil;
    nil->lz=nil->isn=nil->val=nil->flip=nil->bl=0;
    nil->siz=0;
    nil[++cnt]=nil[0];
    return nil+cnt;
}

void rotate(tree *x)
{
    int d=x->d();
    tree *y=x->f;
    y->sc(x->c[!d],d);
    if(y->f==nil) x->f=nil; else y->f->sc(x,y->d());
    x->sc(y,!d);
    x->pp=y->pp;
    y->pp=nil;
    up(y); up(x);
}

void splay(tree *x)
{
    int hy=1; stack[hy]=x;
    for(;stack[hy]->f!=nil;hy++) stack[hy+1]=stack[hy]->f;
    for(int i=hy;i>=1;i--) down(stack[i]);
    for(tree *y;x->f!=nil;)
    {
        y=x->f;
        if(y->f!=nil)
        (y->d()^x->d())?rotate(x):rotate(y);
        rotate(x);
    }
}

void access(tree *x) 
{
    tree *y=nil;
    while(x!=nil)
    {
        splay(x);
        if(x->c[1]!=nil)
        {
            x->c[1]->f=nil;
            x->c[1]->pp=x;
        }
        x->c[1]=y;
        if(y!=nil)
        {
            y->f=x;
            y->pp=nil;
        }
        up(x);
        y=x;
        x=x->pp;
    }
}

void evert(tree *x)
{
    access(x);
    splay(x);
    x->flip^=1;
}

void link(tree *x,tree *y)  
{
    evert(y);
    splay(y);
    y->pp=x;
}

int find(int x) { return (f[x]<0)?(x):(f[x]=find(f[x])); }

int main()
{
    freopen("2008.in","r",stdin);
    freopen("2008.out","w",stdout);
    scanf("%d%d",&n,&m); cnt=0; dc=0;
    for(int i=1;i<=n;i++) { ro[i]=newtree(); f[i]=-1; }
    for(int i=1;i<=m;i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        int xa=find(a),xb=find(b);
        if(xa!=xb)
        {
            if(f[xa]>f[xb]) swap(xa,xb);
            f[xa]+=f[xb]; f[xb]=xa;
            ro[n+i]=newtree(); ro[n+i]->bl=1;
            link(ro[a],ro[n+i]);
            link(ro[b],ro[n+i]);
        } else A[++dc]=a,B[dc]=b,vis[dc]=1;
    }
    for(int i=1;i<=dc;i++)
    {
        int a=A[i],b=B[i];
        evert(ro[a]); access(ro[b]); splay(ro[b]);
        if(!((ro[b]->siz>>1)&1))
        {
            if(ro[b]->bl) ro[b]->isn=1;
            ro[b]->lz=1;
            vis[i]=0;
        }
    }
    for(int i=1;i<=dc;i++)
    if(vis[i])
    {
        int a=A[i],b=B[i];
        evert(ro[a]); access(ro[b]); splay(ro[b]);
        if(ro[b]->isn)
        {
            if(ro[b]->bl) ro[b]->isn=1;
            ro[b]->lz=1;
            vis[i]=0;
        }
    }
    scanf("%d",&Q);
    while(Q--)
    {
        int a,b; scanf("%d%d",&a,&b);
        if(find(a)!=find(b)) printf("No\n"); else
        {
            evert(ro[a]); access(ro[b]); splay(ro[b]);
            if(((ro[b]->siz>>1)&1) || (ro[b]->isn)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

第二题 石子合并 (贪心)

【题目描述】

【解题思路】

  假设每一堆最多只能被合并一次,那么对于初始的堆来算,一共需要累加1+2+3+……(n-1)次,把最大的次数分给最小的堆。即A1(n-1)+A2(n-2)+……+An-1(A[]是从小到大排序的)
  推广到每一堆最多只能被合并k次,那么最优的合并的次数是呈现出一棵完全k叉树的。
NOIP2017提高组 模拟赛20(总结)
  A[i]的合并次数就是它在树上的深度(根节点的深度为0),可以用贪心来证明(对于固定的k,最优的合并次数是固定的,那么把最小的A乘最大的次数,最大的A乘最小的次数就是最优解)
  排个序,做个前缀和sum[]。
  求出在第H层的范围【L,R】,ans+=sum[R]-sum[L-1]*H。
  每一次的时间复杂度为 logkn
  总时间复杂度最大为 nlog2n
  记得k=1要特判(先算出答案,遇到k=1的情况就输出)。
  或者记忆化……

【代码】

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N=100010;
int n,Q;
int d[N];
ll sum[N],ans,kw1;

bool cmp(int a,int b) { return (a>b); }

int main()
{
    freopen("2015.in","r",stdin);
    freopen("2015.out","w",stdout);
    scanf("%d",&n); kw1=0ll;
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    sort(d+1,d+1+n,cmp); sum[0]=0ll;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+d[i],kw1+=(ll)d[i]*(i-1);
    scanf("%d",&Q);
    while(Q--)
    {
        int k;
        scanf("%d",&k);
        if(k==1)
        {
            printf("%lld\n",kw1);
            continue;
        }
        int rt=0;
        ll last=0ll,yu=1ll; ans=0ll;
        for(;;)
        {
            ans+=(sum[yu+last]-sum[last])*rt;
            last+=yu;
            if(last+yu*k>n) break;
            yu*=k; rt++;
        }
        rt++;
        ans+=(sum[n]-sum[last])*rt;
        printf("%lld\n",ans);
    }
    return 0;
}

第三题 黑白树 (树链剖分+bit/LCT 只需access)

【题目描述】

【解题思路】

  一个点的同色联通块的ans一定等于它最远的同色祖先的ans。
  对于一个节点,只需考虑它的子树对它答案的影响,若求它的答案就找到它的最远同色祖先(最远同色祖先ance的父亲ance_father不会影响到ance的答案,因为它们是不同色的)。
  对于一个节点i,维护假如它是黑色的答案和假如它是白色的答案(子树对它的贡献,包括假设的节点i)。
  那么,当节点i变色的时候,影响的就是同色的祖先到i的父亲的那一段以及祖先的父亲(如下图)。
NOIP2017提高组 模拟赛20(总结)
  用LCT维护路径加问题。
  用二叉查找,找出最远的同色祖先。(对于点i,维护子树是否全是白色,是否全是黑色。)
  若x的右儿子全是与i同色(或是没有右儿子),且x也与i同色,则往左儿子去找。
   否则往右儿子去找。(左儿子是点x的祖先,右儿子是点x的后代)
  先access出那一段,splay,然后打lazy标记,down。
  答案就是对于点i的最远同色祖先的sum。

【代码】

#include<cstdio>
#include<algorithm>

#define F(x,y) (y==1)?(x->ab):(x->aw);

using namespace std;

const int N=100100;
struct tree
{
    tree *f,*c[2],*pp;
    int s[2],l[2];
    bool a[2],col;
    int d() { return (f->c[1]==this); }
    void sc(tree *x,int d) { (c[d]=x)->f=this; }
} nil[N<<2],*ro[N<<2],*stack[N<<2],*pre;
int to[N<<1],ne[N<<1],h[N],tt;
int g[N],n,m,fu[N];

void add(int a,int b) { to[++tt]=b; ne[tt]=h[a]; h[a]=tt; }

void down(tree *x)
{
    if(x==nil) return;
    for(int i=0;i<2;i++)
    if(x->l[i]!=0)
    {
        if(x->c[0]!=nil) x->c[0]->l[i]+=x->l[i],x->c[0]->s[i]+=x->l[i];
        if(x->c[1]!=nil) x->c[1]->l[i]+=x->l[i],x->c[1]->s[i]+=x->l[i];
        x->l[i]=0;
    }
}

void up(tree *x)
{
    if(x==nil) return;
    x->a[0]=x->a[1]=x->col;
    if(x->c[0]!=nil) x->a[0]|=x->c[0]->a[0],x->a[1]&=x->c[0]->a[1];
    if(x->c[1]!=nil) x->a[0]|=x->c[1]->a[0],x->a[1]&=x->c[1]->a[1];
}

void rotate(tree *x)
{
    int d=x->d();
    tree *y=x->f;
    y->sc(x->c[!d],d);
    if(y->f==nil) x->f=nil; else y->f->sc(x,y->d());
    x->sc(y,!d);
    x->pp=y->pp;
    y->pp=nil;
    up(y); up(x);
}

void splay(tree *x)
{
    int hy=1; stack[hy]=x;
    for(;stack[hy]->f!=nil;hy++) stack[hy+1]=stack[hy]->f;
    for(int i=hy;i>=1;i--) down(stack[i]);
    for(tree *y;x->f!=nil;)
    {
        y=x->f;
        if(y->f!=nil)
        (y->d()^x->d())?rotate(x):rotate(y);
        rotate(x);
    }
}

void access(tree *x) 
{
    tree *y=nil;
    while(x!=nil)
    {
        splay(x);
        if(x->c[1]!=nil)
        {
            x->c[1]->f=nil;
            x->c[1]->pp=x;
        }
        x->c[1]=y;
        if(y!=nil)
        {
            y->f=x;
            y->pp=nil;
        }
        up(x);
        y=x;
        x=x->pp;
    }
}

tree *ance(tree *x)
{
    access(x); splay(x);
    int co=x->col;
    tree *y;
    while(x!=nil)
    {
        if((x->c[1]->a[co]==co || x->c[1]==nil)&& x->col==co)
        {
            y=x;
            x=x->c[0];
        } else x=x->c[1];
    }
    splay(y);
    return y;
}

void dfs(int x,int fa)
{
    g[x]=1;
    for(int p=h[x];p;p=ne[p])
    {
        int v=to[p];
        if(v==fa) continue;
        dfs(v,x);
        g[x]+=g[v]; fu[v]=x;
    }
}

int main()
{
    freopen("2017.in","r",stdin);
    freopen("2017.out","w",stdout);
    scanf("%d",&n); tt=1;
    nil->pp=nil->c[0]=nil->c[1]=nil->f=nil;
    nil->s[0]=nil->s[1]=nil->l[0]=nil->l[1]=0;
    nil->a[0]=nil->a[1]=nil->col=0;
    for(int i=1;i<n;i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        add(a,b); add(b,a);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        nil[i]=nil[0]; ro[i]=&nil[i];
        ro[i]->a[0]=0; ro[i]->a[1]=1;
        ro[i]->s[0]=g[i]; ro[i]->s[1]=1;
        ro[i]->col=0;
    }
    for(int i=2;i<=n;i++) ro[i]->pp=ro[fu[i]];
    int Q; scanf("%d",&Q);
    for(;Q--;)
    {
        int a,b; scanf("%d%d",&b,&a);
        tree *anx=ance(ro[a]);
        int co=ro[a]->col;
        if(b==1)
        {
            int si=ro[a]->s[co];
            ro[a]->s[co]+=si;
            anx->s[co]-=si;
            anx->c[1]->l[co]-=si;
            anx->c[1]->s[co]-=si;
            if(anx!=ro[1]) ro[fu[anx-nil]]->s[co]-=si;

            co^=1;
            si=ro[a]->s[co];
            splay(ro[a]);
            ro[a]->col^=1;
            up(ro[a]);
            ro[a]->s[co]=0;

            anx=ance(ro[a]);
            anx->s[co]+=si;
            anx->c[1]->s[co]+=si;
            anx->c[1]->l[co]+=si;
            if(anx!=ro[1]) ro[fu[anx-nil]]->s[co]+=si;
        } else
        if(b==0) printf("%d\n",anx->s[co]);
    }
    return 0;
}