南昌邀请赛网络赛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

题目描述

输出前五个完全数。

解题思路

打表。

AC代码

复制

#include<bits/stdc++.h>
int main(){
    printf("6\n28\n496\n8128\n33550336");
    return 0;
}

B

题目描述

解题思路

AC代码

复制

C

题目描述

解题思路

AC代码

复制

D

题目描述

解题思路

AC代码

复制

E

题目描述

解题思路

AC代码

复制

F

题目描述

解题思路

AC代码

复制

G

题目描述

解题思路

AC代码

复制

H

题目描述

给定一个$2\times N$的格点图，从左上角走到右下角，可以向上、下、左、右、左上、左下、右上、右下走，走过的点的集合为$S$，求$S$的种数对$1000000007$取模的值。$0<n\leq 10^9$。

解题思路

最左一列只能有两种选择：只经过上面、两块都经过

最右一列只能有两种选择：只经过下面、两块都经过

其他列每一列至少需要有一个经过的点，故有三种选择：只经过上面、只经过下面、两块都经过。

于是，答案为$4\times 3^{N-2}$。注意特判$N=1$。

AC代码

复制

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int w=1000000007,n;
ll qpow(ll a,ll b){
    ll ans=1;
    int i;
    for(i=b;i;i>>=1,a=a*a%w)if(i&1)ans=ans*a%w;
    return ans;
}
int main(){
    scanf("%d",&n);
    if(n==1)printf("1");
    else printf("%d",1LL*4*qpow(3,n-2)%w);
    return 0;
}

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

---

输出结果：

$1$
$1 1$
$0 1 0$
$0 0 0 0$
$1 0 0 0 1$
$1 1 0 0 1 1$
$0 1 0 0 0 1 0$
$0 0 0 0 0 0 0 0$
$1 0 0 0 1 0 0 0 1$
$1 1 0 0 1 1 0 0 1 1$
$0 1 0 0 0 1 0 0 0 1 0$
$0 0 0 0 0 0 0 0 0 0 0 0$
$1 0 0 0 1 0 0 0 1 0 0 0 1$
$1 1 0 0 1 1 0 0 1 1 0 0 1 1$
$0 1 0 0 0 1 0 0 0 1 0 0 0 1 0$
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0$
$1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1$
$1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1$
$0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0$
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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

题目描述

有一棵树，第一年是一个杆，每年每个叶子节点伸出三个长度为当前树枝长度四分之一的树枝，分别与当前树枝方向呈$0°,60°,-60°$。给一个方程为$y=k(x-x_0)+y_0$的直线去砍这棵树，问最后根节点连带的一段没被砍掉的有多么长。

解题思路

？？这么水一题当时怎么没做

根据深度找搜索方向，深搜一遍，$3^{14}$甚至不需要剪枝（什么，最后只跑了14ms）。

AC代码

复制

#include<bits/stdc++.h>
#define delta (k*(a-x)+y-b)
using namespace std;
int n,l;
double x,y,k;
int OnLine(double a,double b){
    if(fabs(delta)<1e-8)return 0;
    if(delta<0)return -1;
    return 1;
}
double dir[6][2]={{0,1},{-sqrt(3)/2,0.5},{-sqrt(3)/2,-0.5},{0,-1},{sqrt(3)/2,-0.5},{sqrt(3)/2,0.5}};
double dfs(int dep,int di,double a,double b,double len){
    if(dep==n||!OnLine(a,b))return 0;
    double dis=delta/(dir[di][1]-k*dir[di][0]);
    if(dis>=0&&dis<=len)return dis;
    return len+
    dfs(dep+1,(di+1)%6,a+len*dir[di][0],b+len*dir[di][1],len/4)+
    dfs(dep+1,di,a+len*dir[di][0],b+len*dir[di][1],len/4)+
    dfs(dep+1,(di+5)%6,a+len*dir[di][0],b+len*dir[di][1],len/4);
}
int main(){
    int i,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%lf%lf%lf",&l,&n,&x,&y,&k);
        printf("%.6f\n",dfs(0,0,0,0,l));
    }
    return 0;
}

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