携程0313 笔试 总共80分？

第三 1，质数因子个数+最小子数组和

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static int[] b = new int[10001];

    static {
        /**计算出1-10000所有的质数 埃氏筛 */
        boolean[]isP = new boolean[10001];
        Arrays.fill(isP, true);

        //取出下一个质数，所有该质数的倍数去掉

        for (int i = 2; i <= 10000; i++) {
            if (!isP[i])continue;
            /**质数 i*/
            for (int k = 2; k * i <= 10000; k++)isP[k * i] = false;
        }
        isP[1] = false;
        isP[0] = false;

        /**所有的数字的权值（质因子个数） */
        for (int j = 2; j <= 10000; j++) {
            if (isP[j])
                for (int p = 1; p * j <= 10000; p++)b[p * j]++;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[]a = new int[n];
        for (int i = 0; i < n; i++)a[i] = in.nextInt();
        /**
          删除权值和最小的子数组 ===>前缀和
          计算出前缀 权值和
         */
        int[]pre = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + b[a[i]];
        }

        int mn = pre[n];

        for (int st = 0; st + k - 1 <= n - 1; st++) {
            int o = pre[st + k] - pre[st];
            mn = Math.min(mn, o);
        }
        System.out.print(pre[n] - mn);
    }
}

第四 0.94偶尔0.87，偶数路径个数，真的找不到哪里还能再快了

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

/**
               求全为偶数的路径
        12
      /  \
    16    3
    /
  4

  long dfs(i):  i节点为终点的 偶数路径 个数
      
	  无论当前a[i]是奇数还是偶数，都需要往下继续dfs

  1.   如果i节点为奇数直接返回0,

  2.   如果i节点为偶数
          同时 ans+=  1 + sum(子节点) + sum(j1*j2,j2*j3,....)
          返回的是 1+sum(子节点)

 */

public class Main {

    public static long ans = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();


        boolean[]a = new boolean[n + 1];

        for (int i = 0; i < n; i++)a[i + 1] = in.nextInt() % 2 == 0;
        
        List<Integer>[]g = new List[n + 1];
        Arrays.setAll(g, i->new ArrayList());
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt(), v = in.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        dfs(1, 0, g, a);
        System.out.print(ans);
    }

    public static long dfs(int i, int fa, List<Integer>[]g, boolean[]a) {
        if (g[i].size() == 1 && fa != 0) { //叶子节点直接返回
            int c = a[i] ? 1 : 0;
            ans += c;
            return c;
        }
        long res = 0;   //这个节点的返回个数
        long a1 = 0;  //用于组合计数的

        // 子节点j, 无论当前节点是否为奇数都需要往下dfs
        for (int j : g[i]) {
            if (j == fa)continue;
            long rj = dfs(j, i, g, a);
            a1 += res * rj;
            res += rj;
        }
        ans += a[i] ? 1 + res + a1 : 0;
        return a[i] ? res + 1 : 0;
    }
}