题解 | 牛客小白月赛112 DEF Java题解

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

D 智乃的“K”叉树

换根动态规划，记录每个节点子树的最大叉数，以及子节点的前二大叉数，两次深搜即可，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),max[][]=new int[n+5][3];
        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();
            path[u].add(v);
            path[v].add(u);
        }
        find(1,0,path,max);
        int ans[]=find(1,0,0,path,max);
        System.out.println(ans[0]+" "+ans[1]);
    }
    static int[] find(int k,int p,int pre,List<Integer> path[],int max[][]){
        int ans[]=new int[]{Math.max(pre,Math.max(max[k][0],path[k].size())),k};
        for(int a:path[k]){
            if(a!=p){
                int cur[]=find(a,k,Math.max(Math.max(pre,path[k].size()-1),max[a][0]==max[k][1]?max[k][2]:max[k][1]),path,max);
                if(cur[0]<ans[0]||cur[0]==ans[0]&&cur[1]<ans[1]){
                    ans=cur;
                }
            }
        }
        return ans;
    }
    static void find(int k,int p,List<Integer> path[],int max[][]){
        int count=0;
        for(int a:path[k]){
            if(a!=p){
                count++;
                find(a,k,path,max);
                max[k][0]=Math.max(max[k][0],max[a][0]);
                int arr[]=new int[]{max[k][1],max[k][2],max[a][0]};
                Arrays.sort(arr);
                max[k][1]=arr[2];
                max[k][2]=arr[1];
            }
        }
        max[k][0]=Math.max(max[k][0],count);
    }
}

根据出题人的解答，无需建树，可以大大简化思路：

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[]=new int[n+5],max=0;
        for(int i=0;i<n-1;i++){
            count[sc.nextInt()]++;
            count[sc.nextInt()]++;
        }
        for(int a:count){
            max=Math.max(max,a);
        }
        for(int i=1;i<=n;i++){
            if(count[i]!=max){
                System.out.println(max-1+" "+i);
                return;
            }
        }
        System.out.println("1 1");
    }
}

E 智乃的“凑数”题（Easy Version） && F 智乃的“凑数”题（Hard Version）

类似于01背包的思路，需要分别记录两部分分别的和，只需要记录乘积在10000以下的状态即可，总共最多10000log10000个不同状态，同时记录每个可达状态的来源即可，时间复杂度(nClogC+m(n+sqrt(x))，C==10000

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),pre[][][]=new int[10005][][];
        boolean has[][]=new boolean[10005][];
        for(int i=0;i<=10000;i++){
            has[i]=new boolean[10000/Math.max(1,i)+5];
            pre[i]=new int[10000/Math.max(1,i)+5][];
        }
        has[0][0]=true;
        for(int i=0;i<n;i++){
            int k=sc.nextInt();
            boolean temp[][]=new boolean[10005][];
            for(int j=0;j<=10000;j++){
                temp[j]=has[j].clone();
            }
            for(int j=0;j<=10000;j++){
                for(int p=10000/Math.max(j,1);p>=0;p--){
                    if(j>=k&&!temp[j][p]&&has[j-k][p]){
                        temp[j][p]=true;
                        pre[j][p]=new int[]{j-k,p};
                    }
                    if(p>=k&&!temp[j][p]&&has[j][p-k]){
                        temp[j][p]=true;
                        pre[j][p]=new int[]{j,p-k};
                    }
                }
            }
            has=temp;
        }
        for(int i=0;i<m;i++){
            find(sc.nextInt(),has,pre);
        }
    }
    static void find(int x,boolean has[][],int pre[][][]){
        for(int i=1;i*i<=x;i++){
            if(x%i==0&&has[i][x/i]){
                System.out.println("Yes");
                List<Integer> list1=new ArrayList<>(),list2=new ArrayList<>();
                for(int j=i,k=x/i;j>0||k>0;){
                    int p[]=pre[j][k];
                    if(p[0]!=j){
                        list1.add(j-p[0]);
                        j=p[0];
                    }
                    else{
                        list2.add(k-p[1]);
                        k=p[1];
                    }
                }
                System.out.println(list1.size()+" "+list2.size());
                StringBuilder sb1=new StringBuilder(),sb2=new StringBuilder();
                for(int a:list1){
                    sb1.append(a+" ");
                }
                for(int a:list2){
                    sb2.append(a+" ");
                }
                System.out.println(sb1+"\n"+sb2);
                return;
            }
        }
        System.out.println("No");
    }
}