45双周赛与227周赛复盘

上周的这两场比赛都是在国际服打的,双周赛a了3题,周赛a了2题,本周的题除了最后一题都比较偏简单,下面来分享一下好题。

5660. 最多可以参加的会议数目 II

题目大意:你有一个数组,每个元素包含一个start,end,value。你最多可以拿k个元素,但是这k个元素的区间不能重合,求怎样拿可以使价值最大。这题咋一看是一个背包问题,我直接大刀阔斧的写下dp转移方程式:
$$
dp[i][j] = dp[i-1][j-1] + nums[i].val \ if \nums[i].start > nums[i-1].end
$$
其中$dp[i][j]$表示为用前i个元素,取j可以取到的最大值,现在问题来了,怎么找到上一个状态呢,显然需要将元素按照起始位置进行排序,在找上一个需要转移的状态时,暴力的话就是从头一个一个找,但是这样会超时,因为我们进行了排序,所以我们可以二分出来这个点,这个点之前的所有状态都是可以转移的,因为我们是按照起始位置进行排序的,那么就得按照从后往前的顺序进行dp的状态转移。

class Solution {
public:
int maxValue(vector<vector<int>>& events, int k) {
sort(events.begin(), events.end(), [&](vector<int>& a, vector<int>& b) {
return a[0] < b[0];
});
int n = events.size();
long long res = 0;
long long dp[n + 5][k + 5];
memset(dp, 0, sizeof(dp));
for(int i = n-1; i >= 0; --i) {
int l = i + 1, r = n;
while(l < r) {
int mid = (l + r) / 2;
if(events[mid][0] <= events[i][1]) {
l = mid + 1;
} else {
r = mid;
}
}
for(int rem = 1; rem <= k; ++rem) {
dp[i][rem] = dp[i+1][rem];
dp[i][rem] = max(dp[i][rem], dp[l][rem - 1] + events[i][2]);
res = max(res, dp[i][rem]);
}
}
return res;
}
};

5675. 最接近目标值的子序列和

周赛的题,感觉都是脑筋急转弯,只有最后一题有点说法,其中这个题解已经说的很清楚:非常好的题解,就是一个状态压缩,其中为了降低运算,分为两部分,并且还使用了双指针这种技巧,总之很是综合,喜欢!

class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size();
int half = n / 2;
int ls = half, rs = n - half;

vector<int> lsum(1 << ls, 0);
for (int i = 1; i < (1 << ls); i++) {
for (int j = 0; j < ls; j++) {
if ((i & (1 << j)) == 0) continue;
lsum[i] += nums[j];
}
}
vector<int> rsum(1 << rs, 0);
for (int i = 1; i < (1 << rs); i++) {
for (int j = 0; j < rs; j++) {
if ((i & (1 << j)) == 0) continue;
rsum[i] += nums[ls+j];
}
}
sort(lsum.begin(), lsum.end());
sort(rsum.begin(), rsum.end());

int ret = INT_MAX;
for (int x: lsum) {
ret = min(ret, abs(goal - x));
}
for (int x: rsum) {
ret = min(ret, abs(goal - x));
}

int i = 0, j = rsum.size() - 1;
while (i < lsum.size() && j >= 0) {
int s = lsum[i] + rsum[j];
ret = min(ret, abs(goal - s));
if (s > goal) {
j--;
} else {
i++;
}
}
return ret;
}
};