电信笔试题整理（Java ACM 模式）

根据提供的三张题目截图整理。以下题名为便于复习拟定，题意作等价转述；截图未显示的考试批次、原题标题和时空限制不作补充。三份 Java 代码分别提交，类名均为 Main，不添加 package。

一、整体难度：放在蓝桥杯里是什么水平？

以下以蓝桥杯大学 B 组省赛的编程题为主要参照，是根据考点和实现量作出的经验估计，并非官方定级。不同年份、组别、语言赛道的难度有差异，不能用这三题直接判断获奖等级。

题目	核心考点	难度估计	在蓝桥杯中的大致位置
1. 记录修改统计	哈希表、模拟、历史状态、整数溢出	入门到简单	省赛靠前的基础模拟题
2. 字符串三等分	前缀计数、整除条件、贪心、字典序	简单到中等偏易	省赛前中段的思维题
3. 树的深度统计与查询	邻接表、BFS、按层预处理、多次查询	简单到中等偏易	省赛前中段的基础图论题，代码量稍大

整体判断：这套题偏基础，主要考查能否熟练、准确地实现常见算法。 对掌握哈希表、前缀统计和 BFS 的同学，三题都有直接的线性或期望线性解法；尚未涉及树形 DP、复杂动态规划、线段树等进阶内容。

第一题最容易，重点是读清“记录是否存在”和“历史修改次数”的区别。
第二题通常最考察推导：如何把“三段相等”转成两个前缀条件，并保证字典序最小。
第三题通常实现量最大，但熟悉 BFS 后属于标准应用题。

若按蓝桥杯大学 A 组省赛的题目定位看，这些考点总体更偏基础；没有必要将它们按国赛难题来准备。能独立写出、解释并处理这些边界，说明已经具备一部分省赛基础编程题的解题能力，但比赛总分还取决于其他题型与现场发挥。

二、第一题：记录修改统计

1. 题意

每个编号初始都不存在记录，取值时视为 0。按顺序执行 q 次操作：

SET id v：将编号 id 的数值设置为 v，不存在时创建记录。
ADD id d：将编号 id 的数值增加 d，不存在时从 0 开始创建记录。
CLEAR id：若记录存在则删除，否则拒绝此次操作。

每次成功的 SET、ADD、CLEAR 都算一次成功修改。每个编号的历史成功修改次数独立累计，删除后再次创建也不清零。

最终输出三个整数：

成功修改的总次数。
被拒绝的 CLEAR 次数。
最终仍存在、最终数值不为 0，且历史成功修改次数恰好为 1 的编号数量。

2. 输入输出

输入第一行是 q，之后 q 行分别是一条操作。输出一行三个整数。

数据范围：1 ≤ q ≤ 2 × 10^5，-10^9 ≤ id, v, d ≤ 10^9。

样例输入：

3
SET 1 5
ADD 2 3
CLEAR 1

样例输出：

3 0 1

解释：三次操作均成功，最后只有编号 2 符合第三项统计条件。

3. 解题思路

维护两个哈希表：

哈希表	含义	成功 CLEAR 后如何处理
`values`	当前存在的编号及其数值	删除对应记录
`changes`	每个编号的历史成功修改次数	保留并增加一次

逐条模拟操作。若 CLEAR 的编号不存在，只增加拒绝次数；其余操作执行后，都增加成功次数和该编号的历史成功修改次数。

最后遍历 values，统计数值非零且历史成功修改次数为 1 的编号。

正确性依据：每次操作后，values 都与实际存在的记录一致，changes 都等于历史成功修改次数。因此最终遍历时，三个要求可以逐一准确判断。

4. 易错点

值为 0 的记录也可能存在。 不能用值是否为零判断能否删除。
SET 设置相同值、ADD 0 都算成功修改。
对不存在的编号执行 ADD 0，仍会创建记录。
删除后不能清空历史成功修改次数；被拒绝的 CLEAR 不计入该次数。
累计数值的绝对值可能达到约 2 × 10^14，必须使用 long。
编号可为负数，且范围大，适合使用哈希表。

5. 复杂度

时间：期望 O(q)。
空间：O(q)。

6. Java 参考代码

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner in = new FastScanner();
        int q = in.nextInt();
        Map<Integer, Long> values = new HashMap<>();
        Map<Integer, Integer> changes = new HashMap<>();
        int success = 0, rejected = 0;

        for (int i = 0; i < q; i++) {
            String op = in.next();
            int id = in.nextInt();
            if (op.equals("SET")) {
                long v = in.nextInt();
                values.put(id, v);
            } else if (op.equals("ADD")) {
                long d = in.nextInt();
                values.put(id, values.getOrDefault(id, 0L) + d);
            } else {
                if (values.remove(id) == null) {
                    rejected++;
                    continue;
                }
            }
            success++;
            changes.put(id, changes.getOrDefault(id, 0) + 1);
        }

        int answer = 0;
        for (Map.Entry<Integer, Long> entry : values.entrySet()) {
            if (entry.getValue() != 0L && changes.get(entry.getKey()) == 1) {
                answer++;
            }
        }
        System.out.println(success + " " + rejected + " " + answer);
    }
}

三、第二题：字符串三等分

1. 题意

给定一个仅包含 A、B、C 的字符串 s，长度为 n。选择切点 x, y，分成三个非空连续段：

[1, x]、[x + 1, y]、[y + 1, n]

要求三段中 A 的数量相同，且 B 的数量也相同，C 的数量不受限制。

输出字典序最小的合法 (x, y)：先让 x 最小，在此基础上让 y 最小。无解时输出 -1 -1。

2. 输入输出

第一行输入 n，第二行输入字符串 s。输出两个整数 x y。

数据范围：3 ≤ n ≤ 2 × 10^5。

样例一输入：

9
ABCCABABC

样例一输出：

2 6

对应三段为 AB、CCAB、ABC，每段都包含一个 A 和一个 B。

样例二输入：

3
ABC

样例二输出：

-1 -1

3. 解题思路

设整个字符串中 A、B 的数量分别是 totalA、totalB。

首先，两个总数都必须能被 3 整除。令：

targetA = totalA / 3
targetB = totalB / 3

用 prefixA[i]、prefixB[i] 表示前 i 个字符中的计数。合法切点必须满足：

prefixA[x] = targetA
prefixB[x] = targetB

prefixA[y] = 2 * targetA
prefixB[y] = 2 * targetB

1 ≤ x < y < n

不需要实际建立前缀数组。先统计总数，再从左到右扫描一次，用两个变量维护前缀计数即可：

找到最早满足第一组条件的 x，且 x ≤ n - 2。
从 x 之后继续扫描，找到最早满足第二组条件的 y，且 y ≤ n - 1。
找不到则输出 -1 -1。

总数能被 3 整除只是必要条件，字符的排列仍可能导致无解。例如 AAABBBCCC 就无法合法划分。

4. 为什么贪心能得到字典序最小答案？

设存在一个合法划分 (x', y')，而扫描找到的第一个切点是 x。

因为 x 是最早满足第一组条件的位置，所以 x ≤ x'。
原合法划分满足 y' > x' ≥ x，因此 y' 仍在 x 之后。
x 和 y' 的前缀计数分别满足第一组、第二组条件，所以 (x, y') 也合法。

因此，只要存在解，选最早的 x 就不会漏解。固定这个 x 后再选最早的 y，得到的就是字典序最小答案。

5. 易错点

切点按题意使用从 1 开始的位置，s.charAt(i - 1) 对应第 i 个字符。
三段必须非空，不能让 x = 0、x = y 或 y = n。
全部为 C 时，合法答案是 1 2；不能在同一轮同时确定两个相同的切点。
A、B 中某一种的总数可以为 0。
暴力枚举两处切点需要 O(n²)，无法应对 2 × 10^5 的规模。

6. 复杂度

时间：O(n)。
额外空间：O(1)，不计保存输入字符串的空间；计入字符串则为 O(n)。

7. Java 参考代码

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();

        int totalA = 0, totalB = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'A') totalA++;
            if (s.charAt(i) == 'B') totalB++;
        }
        if (totalA % 3 != 0 || totalB % 3 != 0) {
            System.out.println("-1 -1");
            return;
        }

        int targetA = totalA / 3, targetB = totalB / 3;
        int a = 0, b = 0, x = -1, y = -1;
        for (int i = 1; i < n; i++) {
            char c = s.charAt(i - 1);
            if (c == 'A') a++;
            if (c == 'B') b++;

            if (x == -1) {
                if (i <= n - 2 && a == targetA && b == targetB) x = i;
            } else if (a == 2 * targetA && b == 2 * targetB) {
                y = i;
                break;
            }
        }

        if (y == -1) System.out.println("-1 -1");
        else System.out.println(x + " " + y);
    }
}

四、第三题：树的深度统计与查询

1. 题意

给定一棵包含 n 个节点的无向树，节点编号为 1 到 n，以节点 1 为根。节点深度为到根节点的边数，因此根节点深度为 0。

先输出三个整数：

整棵树的最大深度。
深度等于最大深度的节点数量。
叶子节点数量。

随后回答 q 次查询。每次给定深度 d，输出深度恰为 d 的节点数量，以及这些节点的编号之和。没有节点时输出 0 0。

本题按无向树的度数定义叶子：与恰好一个节点直接相连的节点是叶子。 所以根节点度数为 1 时也算叶子；n = 1 时唯一的根节点也视为叶子。

2. 输入输出

第一行输入 n q。
接下来 n - 1 行，每行输入一条无向边 u v。
接下来 q 行，每行输入一个查询深度 d。
输出第一行是上述三个整体统计量，之后每行对应一个查询结果。

数据范围：1 ≤ n, q ≤ 2 × 10^5，1 ≤ u, v ≤ n 且 u ≠ v，0 ≤ d ≤ n。输入保证是一棵树。

截图中的样例输入：

按题意计算的对应输出（截图未显示输出区域）：

其中各层节点为：

深度	节点	数量	编号之和
0	1	1	1
1	2、3	2	5
2	4、5	2	9
3	无	0	0

叶子节点是 2、4、5，共 3 个。

3. 解题思路

用邻接表存储无向树，同时统计每个节点的度数。从节点 1 开始执行 BFS，维护：

depth[u]：节点 u 的深度，初始为 -1 表示尚未访问。
count[d]：深度为 d 的节点数量。
sum[d]：深度为 d 的节点编号之和。
maxDepth：遍历过程中遇到的最大深度。

每次取出节点 u，将其计入对应深度的统计。对于尚未访问的相邻节点 v，设置 depth[v] = depth[u] + 1 并入队。

BFS 完成后，整体统计量可以直接得到；每次深度查询也只需访问数组，不需要重新遍历树。

叶子数量单独按度数统计：当 n > 1 时，统计度数为 1 的节点；当 n = 1 时，叶子数量为 1。

正确性依据：树上根到任意节点的路径唯一，BFS 得到的距离就是节点深度。每个节点仅访问一次，所以按深度累计的数量和编号之和准确无误。

4. 易错点

不要将本题叶子误判为“没有子节点的节点”；根节点也可能满足本题的叶子定义。
n = 1 时，最大深度为 0，该层节点数为 1，叶子数也为 1。
节点编号之和可能超过 int，sum 使用 long[]。
链状树的深度可达到 n - 1，递归 DFS 在 Java 中可能栈溢出，使用 BFS 更稳妥。
查询允许 d = n，但实际最大深度不超过 n - 1。若统计数组长度为 n，必须处理这个越界情况。
无向边要存两次；邻接表中的边数组长度为 2 × (n - 1)。

5. 复杂度

建图与 BFS：O(n)。
单次查询：O(1)，全部查询为 O(q)。
总时间：O(n + q)。
图、队列和统计数组占用 O(n)；本实现将输出暂存在 StringBuilder 中，因此按通常的字符输出规模计，总空间为 O(n + q)。

6. Java 参考代码

import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner in = new FastScanner();
        int n = in.nextInt(), q = in.nextInt();
        int[] head = new int[n + 1];
        Arrays.fill(head, -1);
        int[] to = new int[2 * (n - 1)];
        int[] next = new int[2 * (n - 1)];
        int[] degree = new int[n + 1];

        int edge = 0;
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt(), v = in.nextInt();
            to[edge] = v;
            next[edge] = head[u];
            head[u] = edge++;
            to[edge] = u;
            next[edge] = head[v];
            head[v] = edge++;
            degree[u]++;
            degree[v]++;
        }

        int leaves = 0;
        for (int i = 1; i <= n; i++) {
            if (n == 1 || degree[i] == 1) leaves++;
        }

        int[] depth = new int[n + 1];
        Arrays.fill(depth, -1);
        int[] count = new int[n];
        long[] sum = new long[n];
        int[] queue = new int[n];
        int front = 0, rear = 0, maxDepth = 0;
        queue[rear++] = 1;
        depth[1] = 0;

        while (front < rear) {
            int u = queue[front++];
            int d = depth[u];
            count[d]++;
            sum[d] += u;
            maxDepth = Math.max(maxDepth, d);
            for (int e = head[u]; e != -1; e = next[e]) {
                int v = to[e];
                if (depth[v] == -1) {
                    depth[v] = d + 1;
                    queue[rear++] = v;
                }
            }
        }

        StringBuilder out = new StringBuilder();
        out.append(maxDepth).append(' ').append(count[maxDepth])
           .append(' ').append(leaves).append('\n');
        for (int i = 0; i < q; i++) {
            int d = in.nextInt();
            if (d >= n) out.append("0 0\n");
            else out.append(count[d]).append(' ').append(sum[d]).append('\n');
        }
        System.out.print(out);
    }
}

五、复习与自测清单

题目	建议自测	应关注的结果
记录修改统计	对不存在的编号执行 `CLEAR`	拒绝次数增加，成功次数不变
记录修改统计	`SET 1 0` 后 `CLEAR 1`	两次均成功，零值记录也存在
记录修改统计	`SET 1 5`、`CLEAR 1`、`SET 1 7`	历史修改次数为 3，不满足“恰好一次”
记录修改统计	同一编号连续增加 `10^9`	使用 `long` 避免累计溢出
字符串三等分	`CCC`	输出 `1 2`
字符串三等分	`ABC`	输出 `-1 -1`
字符串三等分	`AAABBBCCC`	总数均可整除，但仍然无解
树的深度统计	只有一个节点，查询深度 0 和 1	首行 `0 1 1`，查询分别为 `1 1`、`0 0`
树的深度统计	只有两个节点	两个节点都算叶子
树的深度统计	20 万节点的链或星形树	避免递归爆栈，编号和使用 `long`

建议按以下顺序复习：

哈希表模拟：练习“当前状态”和“历史状态”分别维护。
前缀计数：把区间条件转换为前缀条件，练习证明贪心选择成立。
图的存储与 BFS：熟练写出无向图邻接表、数组队列和访问标记。
数据范围意识：看到 2 × 10^5 时优先考虑线性或 O(n log n) 方法，并估算累加结果是否超过 int。

六、代码验证记录

本次整理沿用已在本地编译、验证的三份 Java 代码，验证内容包括：

第一题：截图样例、随机操作对拍，以及 20 万次大数累加。
第二题：截图样例、全 C 等边界；另对长度 3 至 8 的全部 9,828 个 ABC 字符串，将同一贪心算法与暴力枚举结果比较；Java 程序另外运行了选取的样例、随机串和 20 万长度输入。
第三题：单节点、双节点、随机树，以及各有 20 万节点的链和星形树。

以上是本地验证记录，不代表已在原笔试平台提交通过。

一、整体难度：放在蓝桥杯里是什么水平？

二、第一题：记录修改统计

1. 题意

2. 输入输出

3. 解题思路

4. 易错点

5. 复杂度

6. Java 参考代码

三、第二题：字符串三等分

1. 题意

2. 输入输出

3. 解题思路

4. 为什么贪心能得到字典序最小答案？

5. 易错点

6. 复杂度

7. Java 参考代码

四、第三题：树的深度统计与查询

1. 题意

2. 输入输出

3. 解题思路

4. 易错点

5. 复杂度

6. Java 参考代码

五、复习与自测清单

六、代码验证记录

相关文章

Java 数论基础：最大公约数、最小公倍数与素数

Java 字符串方法速查

图的存储与遍历：DFS、BFS 与回溯

前缀和与差分：一维与二维区间操作