南昌邀请赛网络赛2019.04.20 题解

Solved	A	B	C	D	E	F	G	H	I	J	K	L	M
7/13	O	.	.	.	.	.	.	O	O	Ø	O	Ø	O

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

比赛链接

官方题解

A

B

C

D

E

F

G

H

I

题目描述

给定一个序列，求其中一个子序列，其中元素$a[i]∈[-10^5,10^5]$，使得其区间最小值乘区间和最大，求出最大值。

解题思路

代码&思路 by Nikkukun

对于每一个值作为区间最小值，求出最大的左端与右端，求出其和的最大值，复杂度$O(n^2)$。

考虑最小值的正负，当最小值为正时，向左右分别延伸到最大值且不含比该值小的数的区间；否则延伸到最小值且不含比该值小的数的区间。

用线段树维护区间最大值，乘以$-1$后也可维护区间最小值（用$ST$表会$MLE$）。

再用含偏移的树状数组（处理负数）维护距离$a[i]$最近的、比$a[i]$小的下标$j$。从左端往右、从右端往左分别维护一个树状数组，树状数组的下标表示$a[i]$，其值表示下标$j$。

AC代码-BIT+线段树 By Nikkukun-223ms

点击

#include<bits/stdc++.h>
using namespace std;

#define lson (o<<1)
#define rson ((o<<1)|1)

typedef long long ll;
const int N=500000+5,BIAS=100000+5,T=BIAS*2,LEN=18+2;
const ll INF=0x3f3f3f3f3f3f3f3f;

struct BITree{
    int t[T];
    BITree(){
        memset(t,0,sizeof(t));
    }
    int Lowbit(int x){
        return x&(-x);
    }
    void Add(int x,int v){
        for(;x<T;x+=Lowbit(x))
            t[x]=v;
    }
    int Query(int x){
        int ret=0;
        for(;x;x-=Lowbit(x))
            ret=max(ret,t[x]);
        return ret;
    }
};

struct ST{
    ll t[N*4];
    void Build(int o,int L,int R,ll a[],int f){
        if(L==R){
            t[o]=f*a[L];
            return;
        }
        int M=(L+R)/2;
        Build(lson,L,M,a,f);
        Build(rson,M+1,R,a,f);
        t[o]=max(t[lson],t[rson]);
    }
    ll Query(int o,int L,int R,int qL,int qR){
        if(qL<=L&&R<=qR)return t[o];
        ll ret=-INF;
        int M=(L+R)/2;
        if(qL<=M)ret=max(ret,Query(lson,L,M,qL,qR));
        if(M+1<=qR)ret=max(ret,Query(rson,M+1,R,qL,qR));
        return ret;
    }
};

int a[N];

int l[N],r[N];
ll suml[N],sumr[N];
BITree bitl,bitr;
ST stl[2],str[2];

int main(){
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=1;i<=n;i++){
        l[i]=bitl.Query(a[i]+BIAS);
        bitl.Add(a[i]+BIAS+1,i);
        suml[i]=suml[i-1]+a[i];
    }
    for(int i=n;i>0;i--){
        r[i]=bitr.Query(a[i]+BIAS);
        bitr.Add(a[i]+BIAS+1,n-i+1);
        sumr[i]=sumr[i+1]+a[i];
    }

    stl[0].Build(1,1,n,suml,1); stl[1].Build(1,1,n,suml,-1);
    str[0].Build(1,1,n,sumr,1); str[1].Build(1,1,n,sumr,-1);

    ll ans=0;
    for(int i=1;i<=n;i++){
        int j=(a[i]>0)?0:1;
        int f=(a[i]>0)?1:-1;
        ll L=f*str[j].Query(1,1,n,l[i]+1,i)-sumr[i];
        ll R=f*stl[j].Query(1,1,n,i,n-r[i]+1-1)-suml[i];
        ans=max(ans,(L+R+a[i])*a[i]);
    }
    printf("%lld",ans);

    return 0;
}

赛后突然发现维护一个单调增的单调栈亦可以找出左右端的最大伸展区间。

AC代码-单调栈+线段树 By Potassium-514ms

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 500002
#define mid ((l+r)>>1)
#define inf 9e18
int sta[N],n,top,l[N],r[N];
ll a[N],s[N];
struct SegTree{
    ll mn,mx;
    int l,r;
}t[N<<2];
void build(int l,int r,int p){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].mn=t[p].mx=s[l];
        return;
    }
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    t[p].mn=min(t[p<<1].mn,t[p<<1|1].mn);
    t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}
ll querymin(int l,int r,int p){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r)return t[p].mn;
    if(L>r||R<l)return inf;
    return min(querymin(l,r,p<<1),querymin(l,r,p<<1|1));
}
ll querymax(int l,int r,int p){
    int L=t[p].l,R=t[p].r;
    if(L>=l&&R<=r)return t[p].mx;
    if(L>r||R<l)return -inf;
    return max(querymax(l,r,p<<1),querymax(l,r,p<<1|1));
}
int main(){
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    for(i=1;i<=n;i++){
        while(top&&a[sta[top]]>=a[i])top--;
        l[i]=top?sta[top]+1:1;
        sta[++top]=i;
    }
    top=0;
    for(i=n;i;i--){
        while(top&&a[sta[top]]>=a[i])top--;
        r[i]=top?sta[top]-1:n;
        sta[++top]=i;
    }
    ll ans=0;
    build(0,n,1);
    for(i=1;i<=n;i++){
        ll lmn=querymin(l[i]-1,i,1),rmn=querymin(i,r[i],1);
        ll lmx=querymax(l[i]-1,i,1),rmx=querymax(i,r[i],1);
        ans=max(ans,a[i]*(rmn-lmx));
        ans=max(ans,a[i]*(rmx-lmn));
    }
    printf("%lld",ans);
    return 0;
}

J

题目描述

给定一棵含$n$个节点的树，有$m$个询问，每个询问$(u,v,k)$求给定两点$(u,v)$之间路径长度不大于$k$的路径数。

$2\leq n \leq 10^5,1\leq m\leq 10^5,1\leq u,v\leq n,0\leq k \leq 10^9$。

解题思路

如果求区间小于$k$的个数，可以用主席树；而在树上路径，则可以用在树上建主席树。设$f(b)$表示从根$(1)$到$b$的路径中小于等于$k$的路径个数，则$ans(u,v,k)=f(u)+f(v)-2f(lca(u,v))$。

注意离散化。

主席树早忘光了，赛场上没写出来……

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100005
#define mid ((l+r)>>1)
struct Edge{
    int e,n,l;
}e[N<<1];
int d[N],fa[22][N],lg[N],hd[N],cnt;
void add(int a,int b,int l){
    e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;e[cnt].l=l;
}
void dfs2(int now,int f){
    d[now]=d[f]+1;
    fa[0][now]=f;
    int i;
    for(i=1;(1<<i)<=d[now];i++)
        fa[i][now]=fa[i-1][fa[i-1][now]];
    for(i=hd[now];i;i=e[i].n){
        int p=e[i].e;
        if(p!=f)dfs2(p,now);
    }
}
int lca(int x,int y){
    int i;
    if(d[x]<d[y]){int t=x;x=y;y=t;}
    while(d[x]>d[y])
        x=fa[lg[d[x]-d[y]]][x];
    if(x==y)return x;
    for(i=lg[d[x]];~i;i--)
        if(fa[i][x]!=fa[i][y])
            x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
int A[N],B[N];
int root[N],L[N<<5],R[N<<5],sum[N<<5];
int build(int l,int r){
    int now=++cnt;
    sum[now]=0;
    if(l<r){
        L[now]=build(l,mid);
        R[now]=build(mid+1,r);
    }
    return now;
}
int update(int root,int l,int r,int x){
    int now=++cnt;
    L[now]=L[root];
    R[now]=R[root];
    sum[now]=sum[root]+1;
    if(l<r){
        if(x<=mid)L[now]=update(L[root],l,mid,x);
        else R[now]=update(R[root],mid+1,r,x);
    }
    return now;
}
int query(int lt,int rt,int l,int r,int x){
    if(l>=r){
        if(B[l]<=x)return sum[rt]-sum[lt];
        else return 0;
    }
    if(B[mid]<=x)return sum[L[rt]]-sum[L[lt]]+query(R[lt],R[rt],mid+1,r,x);
    return query(L[lt],L[rt],l,mid,x);
}
int mx;
int quer(int x,int z){
    return query(root[1],root[x],1,mx,z);
}
void dfs(int r,int f,int len){
    int i;
    root[r]=update(root[f],1,mx,lower_bound(B+1,B+mx+1,len)-B);
    for(i=hd[r];i;i=e[i].n){
        int q=e[i].e;
        if(q!=f)dfs(q,r,e[i].l);
    }
}
int main(){
    int i,n,m,a,b,l;
    scanf("%d%d",&n,&m);
    for(i=1;i<n;i++)scanf("%d%d%d",&a,&b,&l),add(a,b,l),add(b,a,l),A[i]=B[i]=l;
    cnt=0;
    sort(B+1,B+n);
    mx=unique(B+1,B+n)-B-1;
    root[0]=build(1,mx);
    dfs(1,0,0);
    dfs2(1,0);
    for(i=2;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&l);
        printf("%d\n",quer(a,l)+quer(b,l)-2*quer(lca(a,b),l));
    }
    return 0;
}

K

题目描述

给定一个序列${a_n}$，定义三个函数$f,g,w$，$f(l,r)=\oplus a[x] (l\leq x\leq r)$，$g(l,r)=\oplus f(x) (l\leq x\leq r)$，$w(l,r)=\oplus g(x) (l\leq x\leq r)$。

有$q$个询问，每次询问一个区间$[l,r]$，输出$w(l,r)$。

解题思路

比赛的时候模拟一下$fgw$打了个表找出来规律，~~然后就过了。~~

最后的结果是一个有规律的平行四边形，用线段树很容易维护。（用前缀和也可，~~但打线段树打上瘾了~~）

打表代码

点击

#include<stdio.h>
#include<string.h>
int ans[1000];
void f(int x,int y){
    int i;
    for(i=x;i<=y;i++)ans[i]^=1;
}
void g(int x,int y){
    int i,j;
    for(i=x;i<=y;i++)for(j=i;j<=y;j++)f(i,j);
}
void w(int x,int y){
    int i,j;
    for(i=x;i<=y;i++)for(j=i;j<=y;j++)g(i,j);
}
int main(){
    int i,j;
    for(i=1;i<=20;i++){
        memset(ans,0,sizeof(ans));
        w(1,i);
        for(j=1;j<=i;j++)printf("%d ",ans[j]);
        puts("");
    }
    return 0;
}

输出结果：

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int read(){
    char c=getchar();int now=0,f=1;
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        now=(now<<3)+(now<<1)+c-'0';
        c=getchar();
    }
    return now*f;
}
#define N 100010
struct Tree{
    int l,r,dat;
}t[4][N<<2];
int a[N],n;
void build(int R,int p,int l,int r){
    t[R][p].l=l;t[R][p].r=r;
    if(l==r){
        t[R][p].dat=(l%4==R)?a[l]:0;
        return;
    }
    build(R,p<<1,l,(l+r)>>1);
    build(R,p<<1|1,(l+r>>1)+1,r);
    t[R][p].dat=t[R][p<<1].dat^t[R][p<<1|1].dat;
}
int query(int R,int p,int l,int r){
    int L=t[R][p].l,Rr=t[R][p].r;
    if(l<=L&&Rr<=r)return t[R][p].dat;
    if(L>r||Rr<l)return 0;
    return query(R,p<<1,l,r)^query(R,p<<1|1,l,r);
}
int main(){
    int T,i,q;
    T=read();
    while(T--){
        n=read();
        for(i=1;i<=n;i++)a[i]=read();
        for(i=0;i<4;i++)build(i,1,1,n);
        q=read();
        while(q--){
            int l=read(),r=read();
            int R=l%4;
            if((r-l+1)%4==0)printf("0\n");
            else if((r-l+1)%4==1)printf("%d\n",query(R,1,l,r));
            else if((r-l+1)%4==3)printf("%d\n",query((R+1)%4,1,l+1,r));
            else printf("%d\n",query(R,1,l,r)^query((R+1)%4,1,l+1,r));
        }
    }
    return 0;
}

L

M

题目描述

给一个只含小写字母的字符串$S$，$n$个字符串$T$，判断每一个$T$是否是$S$的子串。$0< |S|,|T|\leq 1e5$。

解题思路

代码&思路 by Nikkukun

预处理出$nxt[i][j]$表示第$i$位字符之后最接近的字符$j+’a’$的下一个位置，$O(\sum_{i=1}^n len(T_i))$处理。

AC代码-By Nikkukun-1783ms

点击

#include<bits/stdc++.h>
const int N=100000+5,C=26+2;
char s[N],t[N];
int nxt[N][C];
int main(){
    scanf("%s",s);
    int i,j,n=strlen(s),q;
    memset(nxt,-1,sizeof(nxt));
    for(i=0;i<n;i++)nxt[i][s[i]-'a']=i;
    for(j=0;j<C;j++)nxt[n][j]=n;
    for(i=n-1;i>=0;i--)
        for(j=0;j<C;j++)
            if(~nxt[i][j])nxt[i][j]=nxt[i+1][j];
    scanf("%d",&q);
    while(q--){
        scanf("%s",t);
        int m=strlen(t);
        int p=0,cnt=0;
        while(cnt<m&&nxt[p][t[cnt]-'a']<n){
            p=nxt[p][t[cnt]-'a']+1;
            cnt++;
        }
        printf((cnt==m)?"YES\n":"NO\n");
    }
    return 0;
}

赛后发现，原来暴力也能过，而且竟然只是$1700ms$和$2000ms$的差别。。。

AC代码-By Potassium-2093ms

点击

#include<bits/stdc++.h>
char a[100002],b[100002];
int main(){
    int n,x,y,la,lb,flag;
    scanf("%s%d",a,&n);
    while(n--){
        scanf("%s",b);
        if((lb=strlen(b))>(la=strlen(a)))printf("NO\n");
        else{
            x=y=flag=0;
            while(x<la&&y<lb){
                if(a[x]==b[y])x++,y++;
                else{
                    x++;
                    if(!a[x]){
                        flag=1;
                        break;
                    }
                }
            }
            if(!b[y]&&!flag)printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}