算法笔试—美团20260314春招实习笔试

T1 小美的因子数量

一个正整数的因子个数为奇数，当且仅当它是完全平方数

因数通常是成对出现的，只有当 d = n/d 时，这一对因子才会合并为一个，从而使总数变成奇数。而 d = n/d 意味着 n = d²，即 n 是一个完全平方数（如 1, 4, 9, 16…）。

因此，题目要求的区间 [l, r] 内因子数量为奇数的数的个数，等价于问：区间 [l, r] 内有多少个完全平方数？

那么，计算区间 [l, r] 内完全平方数的个数，可以用前缀和的思想：

1 到 r 之间有多少完全平方数
计算 1 到 l−1 之间有多少个完全平方数
相减

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        long l = in.nextLong();
        long r = in.nextLong();

        long countR = (long) Math.floor(Math.sqrt(r));
        long countL = (long) Math.floor(Math.sqrt(l - 1));

        System.out.println(countR - countL);
}

T2 超级斐波那契数列

这题不会

当查询次数 q 很大，且每次查询的范围固定，千万不要在查询循环里写复杂的逻辑。应该先花 O(N) 时间把所有可能的答案算出来存进数组，查询时直接 O(1) 读取。
在进行 (A - B) % MOD 时，如果 A < B，结果会变成负数。在 Java/C++ 中，必须写成 (A - B + MOD) % MOD 来保证结果落在 [0,MOD−1] 之间。

public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int k = sc.nextInt();
       int q = sc.nextInt();

       long MOD = 1000000007L;
       int MAX_X = 1000000; // 根据题目数据范围，x最大为10^6

       long[] s = new long[MAX_X + 1];
       long[] sum = new long[MAX_X + 1];

       // 预处理
       for (int i = 0; i <= MAX_X; i++){
           if (i <= k){
               s[i] = 1;
           }else{
               // s[n] = sum[n - 1] - sum[n - k - 1]
               long sum_c = sum[i - 1];
               long sum_kc = sum[i - k - 1];

               s[i] = (sum_c - sum_kc + MOD) % MOD;
           }

           sum[i] = (sum[i - 1] + s[i]) % MOD;
       }

       StringBuilder sb = new StringBuilder();
       for (int i = 0; i < q; i++) {
           int x = sc.nextInt();
           sb.append(s[x]).append("\n");
       }
       System.out.print(sb.toString());
   }

T3 最大节点权值

不会

逆向并查集

从所有操作结束后的最终状态开始，倒着向前处理操作，并查集擅长加边，随着加边，节点的度数会增加，权值也会随之增加。

步骤：

记录初始状态： 读入所有的边和所有的操作。
确定最终度数： 计算出所有操作执行完毕后，每个节点剩余的度数。
初始化权值： 计算最终状态下每个节点的权值：Valuei=最终度数i+i。
建立初始并查集：
- 将那些在整个过程中从未被删除的边加入并查集。
- 在并查集的根节点维护一个 maxVal 数组，表示该连通块内最大的 Value。
逆向处理操作： 从最后一个操作 q 开始向前遍历：
- 如果是操作二（查询）： 直接通过并查集找到 x 所属的根，返回其 maxVal。
- 如果是操作一（加边 u−v）：
  - 首先，增加 u 和 v 的度数，即 Valueu 和 Valuev 各加 1。
  - 更新 u 和 v 所在连通块根节点的 maxVal（因为节点权值变大了）。
  - 然后，在并查集中合并 u 和 v 所在的连通块，并更新合并后根节点的 maxVal。
最后将结果逆序输出。

package 笔试面试题.美团.t3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.security.interfaces.EdECKey;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static class Edge {
        int u, v;
        boolean deleted = false;
        Edge(int u, int v) { this.u = u; this.v = v; }
    }

    static class Op {
        int type, x;
        Op(int type, int x) { this.type = type; this.x = x; }
    }

    static int[] parent;
    static long[] maxVal; // 连通块最大权值
    static long[] currentVal; // 单个节点的当前权值
    static int[] degree;

    static int find(int i){
        if(parent[i] == i){
            return i;
        }

        return parent[i] = find(parent[i]);
    }

    static void union(int i, int j){
        int p1 = find(i);
        int p2 = find(j);
        if(p1 != p2){
            parent[p1] = p2;
            maxVal[p2] = Math.max(maxVal[p2], maxVal[p1]);
        }
    }

    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader();
        PrintWriter out = new PrintWriter(System.out);

        int n = fr.nextInt();
        int m = fr.nextInt();
        int q = fr.nextInt();

        Edge[] e = new Edge[m + 1];
        int[] initDegree = new int[n + 1];

        for(int i = 1; i <= m; i++){
            e[i] = new Edge(i, fr.nextInt());
            initDegree[e[i].u]++;
            initDegree[e[i].v]++;
        }

        Op[] ops = new Op[q];
        for (int i = 0; i < q; i++) {
            ops[i] = new Op(fr.nextInt(), fr.nextInt());
            // 删边，也就是加边操作的逆向
            if (ops[i].type == 1) {
                e[ops[i].x].deleted = true;
                // 模拟删边后的度数变化
                initDegree[e[ops[i].x].u]--;
                initDegree[e[ops[i].x].v]--;
            }
        }

        // 初始化并查集
        parent = new int[n + 1];
        maxVal = new long[n + 1];
        currentVal = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            currentVal[i] = (long)initDegree[i] + i;
            maxVal[i] = currentVal[i];
        }

        // 先把从未删除的边连起来
        for (int i = 1; i <= m; i++) {
            if(!e[i].deleted){
                union(e[i].u, e[i].v);
            }
        }

        // 逆向处理
        List<Long> results = new ArrayList<>();
        for (int i = q - 1; i >= 0; i--) {
            if(ops[i].type == 2){
                results.add(maxVal[find(ops[i].x)]);
            }else{
                Edge edge = e[ops[i].x];
                // 恢复边，度数增加
                currentVal[edge.u]++;
                currentVal[edge.v]--;

                // 更新节点所在连通块的最大值
                int rootU = find(edge.u);
                maxVal[rootU] = Math.max(maxVal[rootU], currentVal[edge.u]);
                int rootV = find(edge.v);
                maxVal[rootV] = Math.max(maxVal[rootV], currentVal[edge.v);
                // 合并
                union(edge.u, edge.v);
            }
        }

        // 逆序输出结果
        for (int i = results.size() - 1; i >= 0; i--) {
            out.println(results.get(i));
        }
        out.flush();
    }



    static class FastReader {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try { st = new StringTokenizer(br.readLine()); }
                catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
    }
}