题解 | 牛客周赛 Round 84 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();
        long sum=0;
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            sum+=Math.abs(u-v);
            path[u].add(v);
            path[v].add(u);
        }
        System.out.println(find(1,0,sum,path)[0]);
    }
    static long[] find(int k,int p,long sum,List<Integer> path[]){
        long ans[]=new long[]{(long)1e18,0};
        for(int a:path[k]){
            if(a!=p){
                long cur[]=find(a,k,sum,path);
                ans[0]=Math.min(ans[0],Math.min(cur[0],Math.abs(cur[1]*2-sum+Math.abs(a-k))));
                ans[1]+=cur[1]+Math.abs(a-k);
            }
        }
        return ans;
    }
}

F 小红的陡峭值（五）（easy） && G 小红的陡峭值（五）（hard）

计算每一对儿数对答案的贡献即可，其他细节略，时间复杂度O(n+log(mod))，mod==1e9+7

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a);
        long ans=0,sum=0;
        for(int i=0;i<n;i++){
            ans+=(long)i*a[i]-sum;
            sum+=a[i];
        }
        System.out.println(ans%mod*2*pow(n,mod-2)%mod);
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}