题解 | 牛客周赛 Round 68 DEF Java题解

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

D 红魔馆的馆主（二）

筛出495所有的约数，以及a中每个数相对于每一个约数的前缀和，数组a中每一个数字的贡献是，它自己需要乘的最小的495的余数的个数，，再次遍历数组a，计算该位置的数字加一后的贡献变化即可，时间复杂度(O(495+n*12))，其中12代表495的约数个数

import java.util.*;
public class Main{
    static List<Integer> divisor=new ArrayList<>();
    static{
        for(int i=1;i<500;i++){
            if(495%i==0){
                divisor.add(i);
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n+5],pre[][]=new int[n+5][12];
        long ans,sum=0;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            pre[i]=pre[i-1].clone();
            for(int j=0;j<12;j++){
                if(a[i]%divisor.get(j)==0){
                    pre[i][j]++;
                }
            }
            for(int j=0;j<12;j++){
                if(a[i]*divisor.get(j)%495==0){
                    sum+=pre[i-1][j];
                    break;
                }
            }
        }
        ans=sum;
        for(int i=1;i<=n;i++){
            long cur=sum;
            for(int j=0;j<12;j++){
                if(a[i]*divisor.get(j)%495==0){
                    cur-=pre[n][j]-pre[i][j]+pre[i-1][j];
                    break;
                }
            }
            for(int j=0;j<12;j++){
                if((a[i]+1)*divisor.get(j)%495==0){
                    cur+=pre[n][j]-pre[i][j]+pre[i-1][j];
                    break;
                }
            }
            ans=Math.max(cur,ans);
        }
        System.out.println(ans);
    }
}

E 博丽神社的巫女（二）

分组背包问题，需要提前判断总和与1e5的关系，之后多出的部分再分组背包判断，并记录回溯路径，时间复杂度O(能过)

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],sum=-100000;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            sum+=a[i];
        }
        if(sum<0){
            System.out.println("-1");
        }
        else{
            int act[][]=new int[sum+5][],ans[]=new int[n];
            boolean has[]=new boolean[sum+5];
            has[0]=true;
            for(int i=0;i<n;i++){
                for(int p=sum;p>=0;p--){
                    if(has[p]){
                        continue;
                    }
                    for(int j=0;;j++){
                        int d=a[i]-(a[i]>>j);
                        if(d>p){
                            break;
                        }
                        if(has[p-d]){
                            has[p]=true;
                            act[p]=new int[]{p-d,i,j};
                            break;
                        }
                        if(d==a[i]){
                            break;
                        }
                    }
                }
            }
            if(!has[sum]){
                System.out.println("-1");
            }
            else{
                for(int j=sum;j!=0;j=act[j][0]){
                    ans[act[j][1]]=act[j][2];
                }
                for(int b:ans){
                    System.out.print(b+" ");
                }
            }
        }
    }
}

F 雾之湖的冰精（三）

利用树上前缀和递归，每个节点只需要考虑最多10种子节点前缀和的值，时间复杂度O(n*10)

import java.util.*;
public class Main{
    static long ans=0;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[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=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        find(1,0,path,a,new boolean[n+5]);
        System.out.println(ans);
    }
    static int[] find(int k,int p,List<Integer> path[],int a[],boolean has[]){
        has[k]=true;
        int count[]=new int[10];//以a[p]为基准的计数
        for(int b:path[k]){
            if(!has[b]){
                a[b]+=a[k];
                int cur[]=find(b,k,path,a,has);
                long sum=0;
                for(int i=0;i<=9;i++){
                    sum+=count[i];
                }
                for(int i=0;i<=9;i++){
                    ans+=cur[i]*sum;
                    if(i+a[k]-a[p]<=9){
                        ans+=cur[i];
                    }
                    sum-=count[9-i];
                }
                for(int i=0;i+a[k]-a[p]<=9;i++){
                    count[i+a[k]-a[p]]+=cur[i];
                }
            }
        }
        count[a[k]-a[p]]++;
        return count;
    }
}