Nowcoder 模拟

https://www.nowcoder.com/test/9439037/summary
[编程题] 寻宝
最小生成树，Python TLE

package nowcoder1;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        Set<int[]>[] ss  =new HashSet[1+n];
        for(int i=1;i<=n;i++) ss[i]=new HashSet<int[]>();
        for(int i=0;i<m;i++) {
            int t1=sc.nextInt(),t2=sc.nextInt(),t3=sc.nextInt();
            ss[t1].add(new int[]{t3,t2});
            ss[t2].add(new int[]{t3,t1});
        }
        
        boolean[]vs=new boolean[1+n];
        int res=-1,cnt=1;
        vs[1]=true;
        PriorityQueue<int[]> pq=new PriorityQueue<int[]>(n,new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        
        for(int[] i:ss[1]) 
            if(!vs[i[1]])  pq.add(i);
        while(cnt<n) {
            int[] tmp=new int[]{-1,-1};
            while(!pq.isEmpty()) {
                tmp=pq.remove();
                if(!vs[tmp[1]]) break;
            }
            
//          if(tmp[0]==-1||!vs[tmp[1]]) {
//              System.out.println(-1);
//              return;
//          }
            vs[tmp[1]]=true;
            cnt++;
            res=Math.max(res,tmp[0]);
            for(int[] i : ss[tmp[1]])
                if(!vs[i[1]]) pq.add(i);
        }
            
        System.out.println(res);
            
    }
}

[编程题] 美丽的项链
直接DP

package niuke3;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        int[][]a=new int[n][2];
        for(int i=0;i<n;i++){
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
        }
        long[][]dp=new long[n][m+1];
        for(int i=a[0][0];i<=a[0][1];i++) dp[0][i]=1;
        for(int i=1;i<n;i++)
            for(int j=0;j<=m;j++) {
                for(int k=a[i][0];k<=a[i][1];k++) {
                    if(j-k>=0)
                        dp[i][j] += dp[i-1][j-k];
                }
            }
        
        System.out.println(dp[n-1][m]);
    }
}

[编程题] 排列
直接交换，最后一个不满足，直接和前面任意一个交换即可，

package niuke4;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]a=new int[1+n];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        
        int res=0;
        for(int i=1;i<=n;i++) {
            if(i!=a[i]) continue;
            if(i==n) {
                res++;
                break;
            }
            a[i]=a[i+1];
            a[i+1]=i;
            res++;
        }
        System.out.println(res);
    }
}

[编程题] 勇敢的妞妞
直接DFS肯定不行，大于5直接输出单个属性的最大值，
那小于5个能不能DFS呢？也不行，因为有1000个数，直接DFS会爆栈，考虑到只有5种属性，对每件装备，求出2^5种可能，也就是维护一个大小为32 的数组A，A[1]=A[00001]表示只利用第一个属性的情况下，所有装备可以得到的最大值

package niuke5;

import java.util.Scanner;

public class Main {
    
    static int res2=-1;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        int[][]a=new int[1+n][5];
        int[] max=new int[5];
        int[] helper = new int[32];
        
        for(int i=1;i<=n;i++){
            for(int j=0;j<5;j++) {
                a[i][j]=sc.nextInt();
                max[j]=Math.max(max[j], a[i][j]);
            }
            
            for(int p=0;p<32;p++) {
                int s=0;
                for(int q=0;q<5;q++)
                    if((p&(1<<q))!=0) s+=a[i][q];
                helper[p]=Math.max(helper[p], s);
            }
        }
        
        if(k>=5) {
            int sum=0;
            for(int i:max) sum+=i;
            System.out.println(sum);
        } else {
            dfs(helper,a,n,k,0,0,0);
            System.out.println(res2);
        }
    }

    private static void dfs(int[] helper, int[][] a, int n, int k, int i, int stat, int sum) {
        if(k==0) res2=Math.max(res2, sum);
        if(i==32) return;
        dfs(helper, a, n, k, i+1, stat, sum);
        if((stat&i)==0) dfs(helper, a, n, k-1, i+1, stat|i, sum+helper[i]);
    }
}