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;
}
标签：

相关文章