当前位置：首页 > news >正文

LeetCode --- 433周赛

news 来源：原创 2025/5/19 0:32:44

题目列表

3427. 变长子数组求和
3428. 最多 K 个元素的子序列的最值之和
3429. 粉刷房子 IV
3430. 最多 K 个元素的子数组的最值之和

一、变长子数组求和

3427. 变长子数组求和
题意要求我们能快速算出 $n u m s [s t a r t ... i]$ 这段区间和，其中 $s t a r t = ma x (0, i - n u m s [i])$ 。求任意区间之和，可以用前缀和来计算。

对于区间 $[l, r]$ ，可以用 $p re [r + 1] - p re [l]$ 计算出区间和， $p re [i]$ 表示前 $i$ 个数的和 ( $p re [i + 1] = p re [i] + n u m s [i], p re [0] = 0$ )

代码如下

class Solution {
public:int subarraySum(vector<int>& nums) {int n = nums.size();vector<int> pre(n + 1);for(int i = 0; i < n; i++){pre[i+1] = pre[i] + nums[i];}int ans = 0;for(int i = 0; i < n; i++){int start = max(0, i - nums[i]);ans += pre[i+1] - pre[start];}return ans;}
};// 可以同时计算前缀和 & 答案
class Solution {
public:int subarraySum(vector<int>& nums) {int n = nums.size();vector<int> pre(n + 1);int ans = 0;for(int i = 0; i < n; i++){pre[i+1] = pre[i] + nums[i];int start = max(0, i - nums[i]);ans += pre[i+1] - pre[start];}return ans;}
};

二、最多 K 个元素的子序列的最值之和

最多 K 个元素的子序列的最值之和
由于本题只关注子序列的最大和最小值，所以我们可以给原始数组排序，然后计算每个数作为最大值或最小值对于答案的贡献即可。
具体操作如下

假设排序后 $n u m s = [1, 3, 4, 6, 7, 10, 12]$ ，并且 $k = 2$
对于 $4$ 来说，它作为最大值出现了 $\binom{2}{0}+\binom{2}{1}$ 次，即从 $[1, 3]$ 这两个数中选出 $0$ 个或者 $1$ 个数和 $4$ 组成子序列。子序列的长度小于 $k$
对于 $4$ 来说，它作为最小值出现了 $\binom{4}{0}+\binom{4}{1}$ 次，即从 $[6, 7, 10, 12]$ 这四个数中选出 $0$ 个或者 $1$ 个数和 $4$ 组成子序列。子序列的长度小于 $k$
其他数字同理，故一般的 $n u m s [i]$ 对答案的贡献为 $(\sum_{j=0}^{min(k-1,n_l)}\binom{n_l}{j}+\sum_{j=0}^{min(k-1,n_r)}\binom{n_r}{j})\times nums[i]$ ，其中 $n_l$ 为在 $n u m s [i]$ 左边的数的个数， $n_r$ 为在 $n u m s [i]$ 右边的数的个数，此处的 $n u m s$ 数组是排序后的

代码如下

const int MOD = 1e9 + 7;
const int MX = 1e5 + 1;
long long F[MX];
long long INV_F[MX];
// 快速幂
long long pow(long long x, int y) {long long res = 1;while(y){if(y & 1) res = res * x % MOD;x = x * x % MOD;y >>= 1;}return res;
}
int init = []{F[0] = 1;// 计算阶乘for(int i = 1; i < MX; i++){F[i] = F[i - 1] * i % MOD;}INV_F[MX-1] = pow(F[MX-1], MOD-2);// 计算 阶乘的逆元 即计算 1/n! % MOD 的结果for(int i = MX - 1; i; i--){INV_F[i-1] = INV_F[i] * i % MOD;}return 0;
}();
// 计算 C(n,m) = n!/(m!(n-m)!) = n! * (1/m!) * (1/(n-m)!)
int comb(int n, int m){ return F[n] * INV_F[m] % MOD * INV_F[n-m] % MOD;
}
class Solution {
public:int minMaxSums(vector<int>& nums, int k) {int n = nums.size();ranges::sort(nums);long long ans = 0;for(int i = 0; i < n; i++){long long s = 0;// 计算 nums[i] 作为最小值的子序列个数for(int j = 0; j < min(i + 1, k); j++){s += comb(i, j);}// 计算 nums[i] 作为最大值的子序列个数for(int j = 0; j < min(n - i, k); j++){s += comb(n - i - 1, j);}ans = (ans + s % MOD * nums[i]) % MOD;}return ans;}
};

优化：对于 $\sum_{j=0}^{min(k-1,n_i)}\binom{n_i}{j}$ ，我们是否能在 $O (1)$ 的时间内计算出来？即是否能利用之前计算出来的结果。

令 $s_i=\sum_{j=0}^{min(k-1,n_i)}\binom{n_i}{j}$ ，那么 $s_{i+1}=?$
从实际意义出发， $s_{i+1}$ 表示从 $n_{i+1}$ 个数中选出 $0,1,2,...,min(k-1,n_{i+1})$ 个数的所有可能方案， $s_{i}$ 表示从 $n_{i}$ 个数中选出 $0,1,2,...,min(k-1,n_{i})$ 个数的所有可能方案，其中 $n_{i+1}=n_i+1$ ，也就是说，两者的区别仅仅在于多出了一个数可选
在 $s_i$ 的合法方案数基础上，多出了一个数，有选和不选两种可能，所以共用 $s_i\times2$ 个方案数。但是其中会包含已经选择了 $k - 1$ 个数，再多选一个数，就会非法的情况，所以需要减去 $\binom{n_i}{k-1}$ 的非法方案数
故 $s_{i+1}=s_i\times2-\binom{n_i}{k-1}$

代码如下

const int MOD = 1e9 + 7;
const int MX = 1e5 + 1;
long long F[MX];
long long INV_F[MX];
long long pow(long long x, int y) {long long res = 1;while(y){if(y & 1) res = res * x % MOD;x = x * x % MOD;y >>= 1;}return res;
}
int init = []{F[0] = 1;for(int i = 1; i < MX; i++){F[i] = F[i - 1] * i % MOD;}INV_F[MX-1] = pow(F[MX-1], MOD-2);for(int i = MX - 1; i; i--){INV_F[i-1] = INV_F[i] * i % MOD;}return 0;
}();
int comb(int n, int m){ // 注意 m > n 的非法情况return m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n-m] % MOD;
}
class Solution {
public:int minMaxSums(vector<int>& nums, int k) {int n = nums.size();ranges::sort(nums);long long ans = 0, s = 1;for(int i = 0; i < n; i++){// 这里利用对称性，即对于[1,2,3,4,5]中的 1 和 5 而言，1 作为最小值的出现次数 等于 5 作为最大值的出现次数ans = (ans + s * (nums[i] + nums[n - i - 1])) % MOD;s = (2 * s - comb(i, k - 1) + MOD) % MOD;}return ans;}
};

三、粉刷房子 IV

粉刷房子 IV
我们对左右两边的房子涂色后，剩下的问题就成了剩下的房子如何涂色成本最低，显然这是一个子问题。所以本题可以用动态规划来做。
本题要求相邻房子的颜色不同，所以需要记录当前房子颜色，同时还要求对称房子的颜色也不同，所以还需要记录对称房子的颜色，故状态定义如下

状态定义： $f [i] [j] [k]$ 表示前后各 $i$ 个房子涂色的最小成本，其中第 $i$ 个房子涂色 $j$ ，第 $n - i - 1$ 个房子涂色 $k$
状态转移方程： $f [i] [j] [k] = min (f [i - 1] [a] [b]) + cos t [i] [j] + cos t [n - i - 1] [k]$ ，其中 $j! = k$ 保证对称位置的房子颜色不同， $j! = a ， k! = b$ 保证相邻位置的房子颜色不同。
初始化：根据状态定义 $f [0]$ 表示前后各 $0$ 个房子涂色的最小成本，显然为 0

代码如下

class Solution {
using LL = long long;
public:long long minCost(int n, vector<vector<int>>& cost) {// f[i][j][k] 表示前后各 i+1 个房子涂色的最小成本，其中第 i 个房子涂色 j，第 n-i-1 个房子涂色 kvector f (n / 2 + 1, vector(3, vector<LL>(3, LLONG_MAX/2)));f[0] = vector(3, vector<LL>(3));for(int i = 0; i < n/2; i++){for(int j = 0; j < 3; j++){for(int k = 0; k < 3; k++){if(j == k) continue;f[i+1][j][k] = min({f[i][(j+1)%3][(k+1)%3],f[i][(j+1)%3][(k+2)%3],f[i][(j+2)%3][(k+1)%3],f[i][(j+2)%3][(k+2)%3]}) + cost[i][j] + cost[n-i-1][k];}}}LL ans = LLONG_MAX/2;for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){ans = min(ans, f.back()[i][j]);}}return ans;}
};

四、最多 K 个元素的子数组的最值之和

最多 K 个元素的子数组的最值之和
这题和第二题很相似，不同是本题要求的是子数组的最值之和，我们的思路一样，依旧是看每个数字作为最大值的贡献和作为最小值的贡献。
具体操作如下

假设数组 $n u m s = [1, 5, 4, 6, 3, 4, 4, 9] ， k = 3$
- 第一个 $4$ 作为最大值，出现了 $1$ 次，只有 $[4]$ 一种情况，左右两边的数都比它大。贡献为 $4\times1=4$
- 第一个 $4$ 作为最小值，出现了 $3$ 次，有 $[4], [5, 4], [4, 6]$ 三种情况，再往外 $1$ 和 $3$ 都比它小。贡献为 $4\times3=12$
故对于 $n u m s [i]$ ，需要计算出它左右两边大于它的第一个数字下标，和小于它的第一个数字下标，这可以用单调栈解决。
- 小技巧：我们可以只算数字作为最小值的贡献，然后将数组中的元素取相反数，这时候求最小值就等价于求它作为负数的最大值的贡献，我们只要将两个结果相减就能算出结果
  - 举个例子，将上面的 $n u m s$ 取相反数得 $[- 1, - 5, - 4, - 6, - 3, - 4, - 4, - 9]$
  - 计算第一个 $- 4$ 作为最大值出现次数为 $3$ ，有 $[- 4], [- 5, - 4], [- 4, - 6]$ 三种情况，贡献为 $-4\times3=-12$
- 下面我们只考虑数字作为最小值的贡献（当然只考虑最大值也是同理）
假定对于数字 $n u m s [i]$ ，已经用单调栈计算出了它左右两边大于它的第一个数字下标 $L$ 和 $R$ ，并且子数组的长度最大为 $k$
- 如果 $R-L-1\leq k$ ，那么可以在 $(L, i]$ 中任取一个数作为左端点，在 $[i, R)$ 中任取一个数作为右端点，从而形成一个合法子数组，根据乘法原理，共有 $(i-L)\times(R-i)$ 种情况
- 如果 $R - L - 1 > k$ ，具体情况如下图
  - 公式推导：令 $L = ma x (L, i - k), R = min (R, i + k)$ 缩小范围
  - 其中 $a_0=k-(i-L)+1$ ， $a_n=R-i$ ，则等差数列求和为 $a_0+a_n)(a_n-a_0+1)/2=(L+R-2i+k+1)(R-L-k)/2$ 。
  - 当 $R - i < k$ 时，还剩下 $k - (R - i)$ 个左端点有 $R - i$ 个右端点，共有 $(k - (R - i)) (R - i)$ 种匹配方式
注意重复统计问题，如 $[2, 3, 2, 1]$ 中第一个 $2$ 作为最小值有 $[2], [2, 3], [2, 3, 2]$ 三种，第二个 $2$ 作为最小值有 $[2], [3, 2], [2, 3, 2]$ 三种，显然 $[2, 3, 2]$ 被重复统计了
- 这里我们要采用左边找 $< 2$ 的第一个数，右边找 $\leq2$ 的第一个数，此时第一个 $2$ 作为最小值有 $[2], [2, 3]$ 两种，第二个 $2$ 作为最小值有 $[2], [3, 2], [2, 3, 2]$ 三种，如此就不会重复统计
- 即只要一边允许等于 $n u m s [i]$ ，另一边严格不等即可以保证不重复计算

代码如下

class Solution {long long minSubarraySum(vector<int>& nums, int k){int n = nums.size();vector<int> left(n, -1), right(n, n);stack<int> st;for(int i = 0; i < n; i++){while(st.size() && nums[st.top()] > nums[i]){right[st.top()] = i; // 右边允许相等st.pop();}if(st.size()) left[i] = st.top(); // 左边严格不等st.push(i);}long long ans = 0;for(int i = 0; i < n; i++){int L = left[i], R = right[i];long long s = 0;if(R - L - 1 <= k) s += 1LL*(R - i) * (i - L);else{L = max(L, i - k);R = min(R, i + k);// k - (i - L) + ... + R - iint m = R - i - (k - (i - L));s += 1LL * (R - i + k - (i - L - 1)) * m / 2;if(R - i < k){s += 1LL*(R - i) * (k - (R - i));}}ans += s * nums[i];}return ans;}
public:long long minMaxSubarraySum(vector<int>& nums, int k) {long long ans = minSubarraySum(nums, k);for(auto& x : nums) x = -x;return ans - minSubarraySum(nums, k);}
};

题目列表

一、变长子数组求和

二、最多 K 个元素的子序列的最值之和

三、粉刷房子 IV

四、最多 K 个元素的子数组的最值之和

相关文章：