7.23 小红书提前批笔试 后端-C++

2小时，单选+不定项选择+3道编程。

选择题考点包括dp、继承、信号量、KMP、linux系统、HTTP状态码、循环队列、操作符重载等。

编程题：

• 第一题

题意：给出n（<1e5）和k。构造包含n个数的正整数数组，满足数组的最大公约数为k，求数组总和的最小值。

题解：构造数组形如【k，2k，...，nk】即可。

• 第二题

题意：给出线段的长度n（<1e9）、区间的数量m（<1e5）、截取的长度k（<1e9），以及m个区间（1<=L[i],R[i]<=1e9，保证区间不相交）。用k尽量覆盖更多的区间总长度，求最大覆盖的值。

题解：前缀和+滑动窗口 首先，对于最大的结果，一定存在一个截取窗口在其右边界与某个区间的R[i]重合时满足。可以想象一下，对于一个窗口左右移动时发生的变化。那么从左向右枚举区间，维护窗口左端所在的区间编号，计算当下最大值更新答案。复杂度为O(m)。

• 第三题

题意：给出一个n个数的数组（n<2e5，-1e9<a[i]<1e9）和一个数x（-1e9<x<1e9）。可以把数组中某个值改为x，也可以不修改。求所有连续子数组中总和的最大值。

题解：前缀和 首先对数组求一遍前缀和sum，那么子数组[l, r]的和即为sum[R] - sum[L-1]，再求前缀最大值数组L和后缀最大值数组R（L[i]=max(sum[1,...,i])，R[i]=max(sum[i,...,n])）。先考虑不使用x，那么枚举子数组包含i，ans = max(R[i] - L[i - 1])，即i右侧的最大sum值减去i左侧的最小sum值。接着考虑加入x的影响。如果把a[i]改为x，那么sum[i~n]的值都会增加(x - a[i])，R[i]的值也会增加(x - a[i])。那么对于ans的计算稍加修改，ans = max(R[i] - L[i - 1] + x - a[i])。复杂度为O(n)。

————————————————————————

update：约了8.6面试，不能改时间，有点烦。