题解 | 牛客周赛 Round 88 EFG Java题解

E~G Java题解，代码已去除冗余~~~

E 秘藏

类似于状态机类型的动态规划，此处对于每一步，只有两种状态，且转移是线性，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        long ab[][]=new long[n][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<n;j++){
                ab[j][i]=sc.nextInt();
            }
        }
        ab[0][1]=-(long)1e18;
        for(int i=1;i<n;i++){
            long cur[]=ab[i].clone();
            for(int j=0;j<2;j++){
                ab[i][j]+=ab[i-1][j];
                if(ab[i-1][j^1]>=k){
                    ab[i][j]=Math.max(ab[i][j],ab[i-1][j^1]-k+cur[j]);
                }
            }
        }
        System.out.println(Math.max(ab[n-1][0],ab[n-1][1]));
    }
}

F 回响

对于每一对儿非0之间的数，从小的一侧往大的一次递增填充数字，直到大于较大一侧，开始上下震荡填充，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n+5];
        a[0]=a[n+1]=(int)1e6;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0,j=1;i<=n;i=j,j++){
            while(j<=n+1&&a[j]==0){
                j++;
            }
            if(a[i]<=a[j]){
                for(int k=i+1;k<j;k++){
                    a[k]=a[k-1]<=a[j]?a[k-1]+1:a[k-1]-1;
                }
            }
            else{
                for(int k=j-1;k>i;k--){
                    a[k]=a[k+1]<=a[i]?a[k+1]+1:a[k+1]-1;
                }
            }
        }
        for(int i=2;i<=n;i++){
            if(Math.abs(a[i]-a[i-1])!=1){
                System.out.println("-1");
                return;
            }
        }
        for(int i=1;i<=n;i++){
            System.out.print(a[i]+" ");
        }
    }
}

G 升！龙！

以“根左右”的方式深搜重新排列树节点，同时记录子节点路径的最大路径和，再将新的排列计算排列计算前缀和后缀最大值，对于每一个询问，可以单位时间计算答案，时间复杂度O(n+q)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),q=sc.nextInt(),p[]=new int[n+5],l[]=new int[n+5],r[]=new int[n+5];
        long a[]=new long[n+5],max[]=new long[n+5],pre[]=new long[n+5],suf[]=new long[n+5];
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
            a[i]=sc.nextInt();
        }
        for(int i=2;i<=n;i++){
            p[i]=sc.nextInt();
            path[p[i]].add(i);
        }
        find(1,1,path,a,max,pre,suf,l,r);
        for(int i=1;i<=n;i++){
            pre[i]=Math.max(pre[i],pre[i-1]);
            suf[n+1-i]=Math.max(suf[n+1-i],suf[n+2-i]);
        }
        for(int i=0;i<q;i++){
            int x=sc.nextInt(),y=sc.nextInt();
            System.out.println(Math.max(Math.max(pre[l[x]-1],suf[r[x]+1]),max[x]-a[p[x]]+a[y]));
        }
    }
    static int find(int k,int idx,List<Integer> path[],long a[],long max[],long pre[],long suf[],int l[],int r[]){
        r[k]=l[k]=idx;
        max[k]=pre[idx]=suf[idx]=a[k];
        for(int b:path[k]){
            a[b]+=a[k];
            r[k]=find(b,r[k]+1,path,a,max,pre,suf,l,r);
            max[k]=Math.max(max[k],max[b]);
        }
        return r[k];
    }
}

另外可用线段树维护区间最大值，时间复杂度O((n+q)logn)，参考代码