越笔试越感觉自己菜

1.素数个数 AC

大概就是给个数组，每个数字都可以无限拆分，问数组最多能拆出多少个素数

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int n = sc.nextInt();
        for(int i = 0; i < n; i++) ans += sc.nextInt() >> 1;
        System.out.print(ans);
    }
}

2.排列 AC

给定 n，再给了一个排列 T，扩充成排列 S（数字 1 - n 各使用一次）。问最小字典序的S

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] vis = new boolean[n + 1];
        Queue<Integer> q = new LinkedList();
        for(int i = 0; i < m; i++){
            int num = sc.nextInt();
            vis[num] = true;
            q.offer(num);
        }
        StringBuilder ans =new StringBuilder();
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            while(!q.isEmpty() && q.peek() < i) ans.append(q.poll() + " ");
            ans.append(i + " ");
        }
        while(!q.isEmpty()) ans.append(q.poll() + " ");
        System.out.print(ans.toString().substring(0, ans.length() - 1));
    }
}

3. 平分物品 AC

给了 n 个物品和它对应的价值。可以舍弃一部分物品，要两个人平分这些物品（数量可以不一样，价值总和要一样），问最少舍弃多少价值。
n <= 15，所以直接 dfs

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T > 0) {
            T--;
            int n = sc.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = sc.nextInt();
            //Arrays.sort(a); 这行可以不要，写的时候忘记删去了
            System.out.println(new Solution().value(n, a));
        }
    }
}

class Solution{
    int[] a;
    int n;
    int ans = Integer.MAX_VALUE;
    public int value(int n, int[] a) {
        this.a = a;
        this.n = n;
        dfs(n - 1, 0, 0, 0);
        return ans;
    }

    void dfs(int index, int p1, int p2, int value) {
        if(index == -1) {
            if(p1 == p2 && ans > value) ans = value;
            return;
        }
        dfs(index - 1, p1 + a[index], p2, value);
        dfs(index - 1, p1, p2 + a[index], value);
        dfs(index - 1, p1, p2, value + a[index]);
    }
}

4. 构建生成树 0.1AC

给了 n 个点， m 条边，(u,v,w)，从 m 条边中选 n - 1 条边构建生成树，求最大权值 - 最小权值的最小值
用的 dfs，不知道哪里出问题了……有大佬 AC 的请指教一下。