2019 BUAA Spring Training 1 题解

Solved	A	B	C	D	E
5/5	O	Ø	O	Ø	Ø

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

比赛链接

A

题目描述
给一个括号序列，定义如下

$()$ 是一个括号序列

如果 $A$ 是括号序列，那么 $(A)$ 是括号序列

如果 $A, B$ 是括号序列，那么 $AB$ 是括号序列

括号序列的得分如下

$()$ 的得分是 $1$

如果 $A$ 是括号序列，记其得分为 $S_A$，那么$ (A)$ 是括号序列，其得分为$ 2S_A$

如果 $A, B$ 是括号序列，记其得分分别为 $S_A$ 和 $S_B$，那么 $AB$ 是括号序列，其得分为$ S_A + S_B$
最终求序列的得分，结果对 $12345678910 $取模

解题思路
签到题，用栈模拟即可。

~~考场上傻了没取模还WA了一发~~

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
typedef long long ll;
#define w 12345678910
int n,top;
ll l[100010],ans;
int main(){
    int i,a;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a);
        if(!a)l[++top]=-1;
        else{
            if(l[top]==-1)l[top]=1;
            else{
                ll sc=0;
                while(l[top]!=-1)sc+=l[top--];
                l[top]=sc*2%w;
            }
        }
    }
    for(i=1;i<=top;i++)(ans+=l[i])%=w;
    printf("%lld",ans);
    return 0;
}

B

题目描述
给一个全是正整数的$n\times m$的矩阵，要把上面所有数重新标记，使得新生成的矩阵每一行每一列中，原来相同的元素仍相同，且元素间相对大小不变。求重新标记的矩阵中的最大值。

解题思路
有好多种做法。

贪心地做，可以考虑把所有值从小到大排序，首先放入第一个元素（坐标为$(x_1,y_1)$）必为$ans[1,1]=1$，限制$x_1$所在行、$y_1$所在列的最小可填值为$1$。

假设正在放第$i$个元素，它的坐标为$(x_i,y_i)$，则找到$x_i$所在行的最小可填值$p$及其所在坐标$y_{max}$、$y_i$所在列的最小可填值$q$及其所在坐标$x_{max}$，则$ans[x_i,y_i]=max(ans[x_i,y_{max}]+(a[x_i,y_i]>a[x_i,y_{max}]),ans[x_{max},y_i]+(a[x_i,y_i]>a[x_{max},y_i]))$

这时候我们发现了一个问题：当遇到这组数据

3 5
1 2 3 4 5
1 5 1 1 5
1 6 1 1 1

的时候，因为枚举的时候，右边中间的$5$比左边的$5$更晚枚举到，故显然会输出

5
1 2 3 4 5
1 3 1 1 5
1 4 1 1 1

这样的错误矩阵。

于是我们维护一个并查集，并查集存储的是所有同行或同列中相等的元素。这样在每次寻找答案的时候，必然能够保证最大值是可以被更新的，尽管$ans$数组未必是最后的可行方案。

错误代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
int n,m;
int a[N];
struct point{
    int i,j;
    bool operator<(const point&b)const{return a[(i-1)*m+j]<a[(b.i-1)*m+b.j];}
}p[N];
int linemin[N],colmin[N],ans[N];
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            int x=(i-1)*m+j;
            scanf("%d",&a[x]);
            p[x]=(point){i,j};
        }
    }
    int r=0;
    sort(p+1,p+n*m+1);
    for(i=1;i<=n*m;i++){
        int x=p[i].i,y=p[i].j;
        int p=linemin[x],q=colmin[y];
        int X=(x-1)*m+y;
        ans[X]=max(ans[p]+(a[X]>a[p]),ans[q]+(a[X]>a[q]));
        if(ans[X]>r)r=ans[X];
        linemin[x]=colmin[y]=X;
    }
    printf("%d\n",r);
    /*for(i=1;i<=n*m;i++){
		printf("%d ",ans[i]);
		if(i%m==0)puts("");
	}*/
    return 0;
}
AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
int n,m;
int a[N],f[N];
int find(int x){return x==f[x]?f[x]:f[x]=find(f[x]);}
struct point{
    int i,j;
    bool operator<(const point&b)const{return a[(i-1)*m+j]<a[(b.i-1)*m+b.j];}
}p[N];
int linemin[N],colmin[N],ans[N];
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            int x=(i-1)*m+j;
            scanf("%d",&a[x]);
            p[x]=(point){i,j};
            f[x]=x;
        }
    }
    int r=0;
    sort(p+1,p+n*m+1);
    for(i=1;i<=n*m;i++){
        int x=p[i].i,y=p[i].j;
        int p=find(linemin[x]),q=find(colmin[y]);
        int X=(x-1)*m+y;
        ans[X]=max(ans[p]+(a[X]>a[p]),ans[q]+(a[X]>a[q]));
        if(ans[X]>r)r=ans[X];
        if(a[X]==a[p])f[p]=X;
        if(a[X]==a[q])f[q]=X;
        linemin[x]=colmin[y]=X;
    }
    printf("%d",r);
    return 0;
}

C

题目描述

现有一序列$a_i(1\leq i\leq n)$，初始时$a_i=i$。有$m$个操作，每次操作翻转$[l,r]$区间内所有数并输出其和。

$1\leq n,m \leq 10^5$。

解题思路

平衡树，此时用$FHQTreap$。建树不停进行$merge$操作，每次翻转根据子树大小找到$r$的位置并$split$，取左树为$x$，再在$x$中找到$l-1$并$split$，再取右树为$z$。那么$z$的$sum$即为答案。翻转$z$，再$merge$回去即可。

AC代码

点击

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls t[x].s[0]
#define rs t[x].s[1]
struct FHQTreap{
    int s[2],v,k,sz,lazy;
    ll sum;
}t[100010];
int n,m,tot,rt;
void upd(int x){
    t[x].sz=t[ls].sz+t[rs].sz+1;
    t[x].sum=(ls?t[ls].sum:0)+(rs?t[rs].sum:0)+t[x].v;
}
int newnode(int v){
    t[++tot].k=rand();t[tot].sz=1;t[tot].v=t[tot].sum=v;
    return tot;
}
void pushdown(int x){
    if(t[x].lazy){
        if(ls)t[ls].lazy^=1;
        if(rs)t[rs].lazy^=1;
        swap(ls,rs);
        t[x].lazy=0;
    }
    upd(x);
}
void split(int x,int k,int &a,int &b){
    if(!x){a=b=0;return;}
    pushdown(x);
    if(t[ls].sz>=k)b=x,split(ls,k,a,ls),upd(x);
    else a=x,split(rs,k-t[ls].sz-1,rs,b),upd(x);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    pushdown(x);pushdown(y);
    if(t[x].k<t[y].k){rs=merge(rs,y);upd(x);return x;}
    t[y].s[0]=merge(x,t[y].s[0]);upd(y);return y;
}
void rev(int l,int r){
    int x,y,z;
    split(rt,r,x,y);
    split(x,l-1,x,z);
    t[z].lazy=1;
    printf("%lld\n",t[z].sum);
    int p=merge(x,z);
    rt=merge(p,y);
}
void print(int x){
    pushdown(x);
    if(ls)print(ls);
    printf("%d ",t[x].v);
    if(rs)print(rs);
}
int main(){
    int i,l,r;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)rt=merge(rt,newnode(i));
    for(i=0;i<m;i++){
        scanf("%d%d",&l,&r);
        rev(l,r);
    }
    print(rt);
    return 0;
}

D

题目描述

有$k$个长度为$k$的数列，有$k^k$种方式从每个数组中恰取出一个数，每一种方式对应一种和。求这些和中，前$k$小的值分别为多少。

解题思路

每次合并两个数组，每次取前$k$小。

对两个数组$a,b$排序，显然应当取$(0,0)$这个对（对$(x,y)$表示取$a_x,b_y$）。每次取出$(x,y)$对的时候，扩展出$(x+1,y)(x,y+1)$两个对。注意去重。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a[2][1010],temp[1010]={1};
struct nd{
    int x,y;
    bool operator<(const nd&b)const{return a[x][y]>a[b.x][b.y]||(a[x][y]==a[b.x][b.y]&&(x>b.x||x==b.x&&y>b.y));}//这里一大串其实也是为了去重
    bool operator==(const nd&a)const{return x==a.x&&y==a.y;}
}t;
priority_queue<nd>Q;
int main(){
    int i,j,k;
    scanf("%d",&k);
    for(j=0;j<k;j++)scanf("%lld",&a[0][j]);sort(a[0],a[0]+k);
    for(i=1;i<k;i++){
        for(j=0;j<k;j++)scanf("%lld",&a[1][j]);sort(a[1],a[1]+k);
        Q.push((nd){0,0});
        for(j=0;j<k;j++){
            t=Q.top();
            while(!Q.empty()&&Q.top()==t)Q.pop();//去重
            temp[j]=a[t.x][t.y];
            if(t.x+1<k)Q.push((nd){t.x+1,t.y});
            if(t.y+1<k)Q.push((nd){t.x,t.y+1});
        }
        for(j=0;j<k;j++)a[0][j]=temp[j];
        while(!Q.empty())Q.pop();
    }
    for(i=0;i<k;i++)printf("%lld ",temp[i]);
    return 0;
}

E

题目描述

给一棵树。对于某个节点$x$，有两种操作，第一种是把节点$x$到树根的路径所有的值赋$1$，并输出这次改变的个数；第二种是把$x$和$x$的子树全部置$0$，并输出这次改变的个数。

解题思路

树链剖分，注意$lazy$的使用。

AC代码

点击

#include<bits/stdc++.h>
#define N 100010
int n;
int count=1,head[N];
struct Edge{
    int end,near;
}edge[N<<1];
void addedge(int begin,int end){
    edge[count].end=end;
    edge[count].near=head[begin];
    head[begin]=count++;
}
struct SegTree{
    int l,r,lazy;
    int sum;
}t[N<<2];
int depth[N],fa[N],size[N],son[N],pos[N],top[N],temp[N];
int cnt;
struct Ret{
    int s,r;
    struct Ret operator+(const Ret&a)const{return {s+a.s,r+a.r};}
};
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].lazy=-1;
    if(l==r)return;
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
}
void pushdown(int p){
    int l=t[p].lazy;
    if(l==-1)return;
    t[p<<1].sum=l*(t[p<<1].r-t[p<<1].l+1);
    t[p<<1|1].sum=l*(t[p<<1|1].r-t[p<<1|1].l+1);
    t[p<<1].lazy=t[p<<1|1].lazy=l;
    t[p].lazy=-1;
}
struct Ret query(int p,int L,int R){
    int l=t[p].l,r=t[p].r;
    if(l>=L&&r<=R)return (Ret){t[p].sum,t[p].r-t[p].l+1-t[p].sum};
    if(r<L||l>R||p>4*n)return (Ret){0,0};
    pushdown(p);
    return query(p<<1,L,R)+query(p<<1|1,L,R);
}
void add(int p,int left,int right,int k){
    int l=t[p].l,r=t[p].r;
    if(l>=left&&r<=right){
        t[p].sum=k*(t[p].r-t[p].l+1);
        t[p].lazy=k;
        return;
    }
    if(r<left||l>right)return;
    pushdown(p);
    add(p<<1,left,right,k);
    add(p<<1|1,left,right,k);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void dfs1(int now,int f,int dep){
    depth[now]=dep;
    fa[now]=f;
    size[now]=1;
    int i,mx=0;
    for(i=head[now];i;i=edge[i].near){
        int p=edge[i].end;
        if(p!=f){
            dfs1(p,now,dep+1);
            size[now]+=size[p];
            if(size[p]>mx){
                mx=size[p];
                son[now]=p;
            }
        }
    }
}
void dfs2(int now,int Top){
    int i;
    pos[now]=++cnt;
    top[now]=Top;
    if(!son[now])return;
    dfs2(son[now],Top);
    for(i=head[now];i;i=edge[i].near){
        int p=edge[i].end;
        if(p!=son[now]&&p!=fa[now])dfs2(p,p);
    }
}
void swap(int *A,int *B){int t=*A;*A=*B;*B=t;}
int rangequery(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]])swap(&x,&y);
        ans+=query(1,pos[top[x]],pos[x]).r;
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])swap(&x,&y);
    return ans+query(1,pos[x],pos[y]).r;
}
void rangeadd(int x,int y,int k){
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]])swap(&x,&y);
        add(1,pos[top[x]],pos[x],k);
        x=fa[top[x]];
    }
    if(depth[x]>depth[y])swap(&x,&y);
    add(1,pos[x],pos[y],k);
}
int main(){
    int i,f;
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d",&f);
        addedge(f,i);addedge(i,f);
    }
    int r=0,q,opt,x;
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n);
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d%d",&opt,&x);
        if(opt==1){
            printf("%d\n",rangequery(0,x));
            rangeadd(0,x,1);
        }else{
            printf("%d\n",query(1,pos[x],pos[x]+size[x]-1).s);
            add(1,pos[x],pos[x]+size[x]-1,0);
        }
    }
    return 0;
}