选择题10题(30分)
算法 + JAVA + 计网 + 计组 八股
难度中等,算法考察了二叉排序树,二叉树前中后序,图的广搜深搜
编程题3题(20 + 20 + 30)
1.T组询问,给定一个数字n, 找到一个数字m满足1<=m <= n使得 gcd(n, m) 为质数
做法:直接枚举就好
2.给定一个长度为n的数组a, 每次操作可以让 a[i] -> a[i] - 1, a[j] -> a[j] + 1, 问最少多少次操作可以使得数组极差最小。
做法:令 k = sum % n, svg = sum / n, 构造一个序列 b,后 k 个数为 svg + 1, 剩余数为 svg
将 a 升序排序后, 因为加减对称,所以答案就是 a[i] - b[i] (a[i] > b[i]) 的和。
3.给定一个长度为 n 的数组 a, 和一个数字 k, 每次操作必须选择一个非空区间 [l, r] 将区间中所有数字乘上 k , A先手且希望最终数组和最大, B后手希望数组和最小,问一轮过后数组和 sum 是多少。
数据范围: 1 <= n <= 1e3, -1e9 <= a[i], k <= 1e9
做法:
k > 0 :可以枚举 A 的操作区间,问题转化为动态维护全局最小子段和,因为 B 一定操作最小子段和区间
k = 0: 答案为 0
k < 0 :相反,维护全局最大子段和
实现:n^2 枚举 A 操作区间,线段树单点修改维护区间最小/大子段和, 详见https://blog.csdn.net/m0_51156601/article/details/124014996
复杂度: O(n^2logn)
不知道是否有大佬提供O(n^2)及以内的做法,欢迎讨论。
全部评论
(5) 回帖