关注我们，每天更新大厂最新笔试题解析
前言
文末给大家推荐一下我们的活动，针对校招笔面试全覆盖的全程真一对一的提高，参加活动前会给你安排一个全面的摸底，摸底后会针对你的情况进行分析和对于参加活动的介绍，然后你再决定是否参加!
套题做题链接：https://niumacode.com
当我们都渐渐习惯秋招后期的笔试越来越简单时，米哈游义无反顾的站了出来，来了一场难度较高的机考。
米哈游hc不多，游戏厂一般都比较稳定，因为国内的游戏厂一般都是网游，网游的生命周期及其的长，君不见王者荣耀这么多年还是霸榜第一，所以游戏厂是可以跨越周期的存在，比互联网平台还坚韧，网易的西游跨过了多少个牛熊还活得好好的。经济好我充个钱开心一下不过分了，经济不好我都不买车买房了，充钱打个游戏不过分了吧。
米哈游的薪酬也非常可观：（20k-39k）*16（大多数集中在25k-30k）
这套题目的整体难度较高，主要考察了算法和数据结构的综合应用。题目涉及了滑动窗口、贪心算法、树形动态规划等知识，解决这些问题需要较强的计算能力和优化技巧。适合用来测试在大规模数据下的处理能力。
第一题难度中等，涉及到 滑动窗口。通过滑动窗口技术检查每个长度为 26 的子串与目标字母表的匹配情况，并计算最少操作次数，考察了对窗口的动态调整与字符串处理的能力。
第二题难度较高，涉及到 贪心算法与区间选择。要求通过选择最小的区间长度，使得经过某种操作后的数组极差超过给定值，考察了对区间选择和优化的理解。
第三题难度高，涉及到 树形动态规划与距离计算。通过树的遍历（DFS）和边贡献法，计算子树中所有节点对的距离和，考察了树结构的处理和高效查询的能力。
第一题
题意
给定一个长度为 n的字符串 s，字符串仅由小写字母组成，下标从 1 开始。你可以对字符串执行以下操作任意次：
- 选择一个下标
i，将 s的第 i个字符 s_i修改为任意小写字母。
请问最少需要多少次操作，才能让字符串中出现子串 "abcdefghijklmnopqrstuvwxyz"。
名词解释
- 子串：子串为从原字符串中连续地选择一段字符（可以全选、可以不选）得到的新字符串。
输入描述:
- 每个测试文件均包含多组测试数据。第一行输入一个整数
T(1 ≤ T ≤ 10^4)，代表数据组数。 - 第一行输入一个整数
n(1 ≤ n ≤ 2 × 10^5)，表示字符串长度。 - 第二行输入一个长度为
n、仅由小写字母构成的字符串 s。
- 除此之外，保证所有测试数据中
n的总和不超过 2 × 10^5。
输出描述:
- 对于每组测试数据，新起一行，输出一个整数，代表最少的操作次数。
- 如果不存在使字符串中出现完整英文小写字母序列的方案，则输出
-1。
示例1
输入:
337abcdefghijklmnopqrstuvwxyzzzzzzzzzzzz26bcdefghijklmnopqrstuvwxyza25abcdefghijklmnopqrstuvwxy
输出:
026-1xxxxxxxxxx 026-12
思路与代码
滑动窗口：
既然目标子串长度是 26，我们可以遍历 s中所有可能的、长度为 26 的连续子串。这些子串就是我们“改造”的候选区域。
对于当前窗口内的子串，我们计算将它变成目标字母表需要修改多少个字符。具体方法是：将窗口内的每个字符与目标字母表中对应位置的字符进行比较，如果不同，则修改次数加一。
import java.util.Scanner;publicclassMain{publicstaticvoidmain(String[] args){ Scanner in = new Scanner(System.in);int T = in.nextInt();while(T-- > 0){int n = in.nextInt(); String s = in.next();if(n < 26){ System.out.println(-1);continue; }int minOps = 26; String target = "abcdefghijklmnopqrstuvwxyz";//滑动窗口，检查当前字串的26个字符与目标的匹配情况for(int i = 0; i <= n-26; i++){int ops = 0;for(int j = 0; j < 26; j++){if(s.charAt(i+j) != target.charAt(j)){ //如果不匹配，操作数++ ops++; } } minOps = Math.min(minOps, ops); //得到最小的操作数 } System.out.println(minOps); } }}
第二题
题意
给定一个长度为 n 的非严格递增数组 a₁≤a₂≤…≤aₙ。你可以执行以下操作至多一次：
- 选择区间 [l,r]，对每个 i∈[l,r] 执行 aᵢ←aᵢ +k×(r−i+1)，其中 k 是给定的固定参数。
请找出能使操作后数组极差（最大值与最小值之差）超过 d 的最小区间长度（可以为 0）。若无法达成，输出 - 1。
【名词解释】
- 极差：数组最大值与最小值的差值，例如数组 {2,5,7} 的极差为 5。
输入描述
第一行输入 T（1≤T≤10⁴）表示测试组数。每组数据包含：
第一行三个整数 n,d,k（2≤n≤2×10⁵，0≤d≤10¹²，1≤k≤10⁹）；
第二行 n 个非严格递增整数 a₁,a₂,…,aₙ（1≤aᵢ≤10⁹）。
保证所有测试数据∑n≤2×10⁵。
输出描述
每组数据输出一个整数，表示满足条件的最小区间长度。
示例1
输入:
34 5 21 3 5 73 10 12 6 83 8 51 2 3
输出:
0-12
思路与代码
这道题的目标是找到一个最短的连续子区间 [l, r]，对该区间内的数 a_i进行 a_i <- a_i + k * (r - i + 1)的变换后，使得整个数组的极差（最大值 - 最小值）超过 d。
我们可以根据操作区间的起始位置 l分成两种情况来求解，并取两种情况中最优（即最小的 len）的结果。
遍历所有可能的 l（从 2 到 n），对于每个 l，计算出满足条件的最小 len，然后检查区间 [l, l+len-1]是否合法。在所有合法的 len中取最小值。
可以遍历所有可能的 r（从 1 到 n），检查哪个最小的 r(即 len) 满足此条件。 直接计算 max_{j=1..r}(a_j + k*(r-j+1))比较慢 ， 可以动态维护 max_{j=1..r}(a_j - k*j)的值 ， 这样，对于每个 r，我们都可以在 O(1) 时间内计算出 新最大值。
import java.util.Scanner;publicclassMain{publicstaticvoidmain(String[] args){ Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) { solve(sc); } sc.close(); }publicstaticvoidsolve(Scanner sc){int n = sc.nextInt();long d = sc.nextLong();long k = sc.nextLong();long[] a = newlong[n];for (int i = 0; i < n; i++) { a[i] = sc.nextLong(); }// 初始情况检查：如果原数组极差已经 > d，则不需要操作，区间长度为0if (a[n - 1] - a[0] > d) { System.out.println(0);return; }long minLen = Long.MAX_VALUE;// 情况一: l > 1 (操作区间不包含第一个元素)for (int i = 1; i < n; i++) {long l = i + 1;// 目标: new_max - a[0] > d// 我们通过提升 a[i] (即 a_l) 来达成目标: a[i] + k*len - a[0] > dlong rhs = d + a[0] - a[i];long requiredLen;if (rhs < 0) {// a[i] 已经足够大，任何正向操作(len>=1)都可满足条件 requiredLen = 1; } else {// len > rhs / k => len = (rhs / k) + 1 requiredLen = rhs / k + 1; }// 检查区间是否合法: r = l + len - 1 <= nif (l + requiredLen - 1 <= n) { minLen = Math.min(minLen, requiredLen); } }// 情况二: l = 1 (操作区间包含第一个元素) // 区间为 [1, r], 长度 len = rlong maxC = Long.MIN_VALUE; // 用于维护 max(a_j - k*j)for (int j = 0; j < n; j++) {long r = j + 1; // r 也是当前的 lenlong len = r;// 动态更新 maxC maxC = Math.max(maxC, a[j] - k * r);// 在 [1,r] 的最大值是 maxC + k*r + klong maxInSegment = maxC + k * r + k;long newMax = Math.max(a[n - 1], maxInSegment);long newMin = a[0] + k * len;if (newMax - newMin > d) { minLen = Math.min(minLen, len);// 因为 r(len) 是递增的，所以找到的第一个解就是此情况下的最优解break; } }// 输出结果if (minLen == Long.MAX_VALUE) { System.out.println(-1); } else { System.out.println(minLen); } }}
第三题
题意
给定一棵树节点数为 n 的树，树的根节点为 1。对树中的任意节点 u，定义其子树为以 u 为根的所有节点集合，记为 (S(u))。现有 m 次查询，每次查询给定一个节点 u，请你计算子树 (S(u)) 中所有节点对 ((v, w)) 之间的距离和， 即 (\sum_{\substack{v, w \in S(u) \ v < w}} \text{dist}(v, w)) ， 其中 dist (v,w) 表示节点 v 与 w 之间的距离。
【名词解释】
- 子树：子树指给定节点及其所有后代节点组成的连通子图。
输入描述
第一行输入两个整数 n 和 m（1≤n,m≤2×10⁵），分别表示树的节点数量与查询次数。
接下来 n-1 行，每行输入两个整数 u_i、v_i（1≤u_i, v_i≤n；u_i≠v_i），表示树的一条边。
接下来 m 行，每行输入一个整数 u（1≤u≤n），表示一次查询的节点编号。
输出描述
对于每次查询，在一行上输出一个整数，表示对应节点子树中所有节点对的距离和。
示例1
输入:
5 31 21 33 43 5134
输出:
1840
说明:
在这个样例中，节点 1 的子树为 {1,2,3,4,5}，其所有 10 对距离之和为 18；节点 3 的子树为 {3,4,5}，距离和 1+1+2=4；节点 4 的子树仅为自身，贡献距离和 0。
思路与代码
本题求解子树内所有点对的距离和。核心思路是边贡献法结合树形动态规划。
我们将问题转化为计算子树内每条边的贡献。对于子树 S(u) 内的一条边，若它连接的子节点 c 的子树大小为 size(c)，则该边对总距离和的贡献为 size(c) * (size(u) - size(c))。
为实现快速查询，我们通过一次 DFS 预处理出每个节点的三个关键值：子树大小 size、其子树内所有节点的 size之和、以及 size的平方和。利用这些预处理信息，每次查询的最终结果可以通过一个 O(1) 的公式直接计算得出，从而将总时间复杂度优化到 O(N+M)。
import java.io.*;import java.util.*;publicclassMain{static List<Integer>[] adj;staticlong[] subtreeSize;staticlong[] sumOfSizes;staticlong[] sumOfSquaresOfSizes;staticint n;publicstaticvoidmain(String[] args)throws IOException { FastReader sc = new FastReader(); PrintWriter out = new PrintWriter(System.out); n = sc.nextInt();int m = sc.nextInt();// 初始化邻接表和结果数组 (使用 n+1 大小方便处理 1-based 索引) adj = new ArrayList[n + 1];for (int i = 1; i <= n; i++) { adj[i] = new ArrayList<>(); } subtreeSize = newlong[n + 1]; sumOfSizes = newlong[n + 1]; sumOfSquaresOfSizes = newlong[n + 1];// 读入边，构建邻接表for (int i = 0; i < n - 1; i++) {int u = sc.nextInt();int v = sc.nextInt(); adj[u].add(v); adj[v].add(u); }// 从根节点1开始DFS进行预处理 dfs(1, 0);// 处理m次查询for (int i = 0; i < m; i++) {int u = sc.nextInt();// 使用推导出的公式 O(1) 计算结果// Result(u) = size[u] * (sum_sz[u] - size[u]) - (sum_sq_sz[u] - size[u]^2)long sz_u = subtreeSize[u];long sum_sz_u = sumOfSizes[u];long sum_sq_sz_u = sumOfSquaresOfSizes[u];long sumOfDescendantSizes = sum_sz_u - sz_u;long sumOfDescendantSqSizes = sum_sq_sz_u - sz_u * sz_u;long result = sz_u * sumOfDescendantSizes - sumOfDescendantSqSizes; out.println(result); } out.flush(); }/** * 深度优先搜索，用于计算每个节点的子树大小、子树内各节点size之和、子树内各节点size平方和 */privatestaticvoiddfs(int u, int parent){// 初始化当前节点的值 subtreeSize[u] = 1; sumOfSizes[u] = 0; // 会在最后加上 subtreeSize[u] sumOfSquaresOfSizes[u] = 0; // 会在最后加上 subtreeSize[u]^2for (int v : adj[u]) {if (v == parent) {continue; }// 递归访问子节点 dfs(v, u);// 回溯阶段，根据子节点的结果更新当前节点 subtreeSize[u] += subtreeSize[v]; sumOfSizes[u] += sumOfSizes[v]; sumOfSquaresOfSizes[u] += sumOfSquaresOfSizes[v]; }// 将当前节点自身的贡献加入总和 sumOfSizes[u] += subtreeSize[u]; sumOfSquaresOfSizes[u] += subtreeSize[u] * subtreeSize[u]; }// --- 快读模板 ---staticclassFastReader{ BufferedReader br; StringTokenizer st;publicFastReader(){ br = new BufferedReader(new InputStreamReader(System.in)); }String next(){while (st == null || !st.hasMoreElements()) {try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } }return st.nextToken(); }intnextInt(){return Integer.parseInt(next()); }longnextLong(){return Long.parseLong(next()); }doublenextDouble(){return Double.parseDouble(next()); }String nextLine(){ String str = "";try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); }return str; } }}
