LeetCode：第 401 场周赛

总结

第四题作为第三题的延申，学习到了使用bitset对DP问题进行优化的技巧

Q1：3178. 找出 K 秒后拿着球的孩子

题目传送门：3178. 找出 K 秒后拿着球的孩子 - 力扣（LeetCode）

签到题。

最后实现代码如下：

class Solution {
public:
    int numberOfChild(int n, int k) {
        int res = k % ((n-1)*2);
        if (res > n-1) {
            res -= (n-1);
            return n-1-res;
        }
        return res;
    }
};

Q2：3179. K 秒后第 N 个元素的值

题目传送门：3179. K 秒后第 N 个元素的值 - 力扣（LeetCode）

签到题*2

最后实现代码如下：

class Solution {
public:
    int valueAfterKSeconds(int n, int k) {
        vector<int> a(n,1);
        int MOD = 1e9 + 7;
        for(int i=1;i<=k;++i){
            int nw = 0;
            for(int j=0;j<n;++j){
                a[j] = (a[j] + nw)%MOD;
                nw = a[j]; nw = nw % MOD;
            }
        }
        return a[n-1];
    }
};

Q3：3180. 执行操作可获得的最大总奖励 I

题目传送门：3180. 执行操作可获得的最大总奖励 I - 力扣（LeetCode）

有点意思的一道题,对于rewardValues中的数，如果先选大的，就没法再选小的，所以按照从小到大的顺序选是最好的。

排序后问题变为了一个01背包问题，定义 $dp[i]$ 表示的是能否选到奖励为i，初始条件dp[0]=true。

最后实现代码如下：

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(),rewardValues.end());
        vector<bool> dp(300000,false);dp[0]=true;
        int maxx = 0;
        for(auto rewardValue : rewardValues){
            for(int i=min(maxx,rewardValue-1);i>=0;--i){
                if (dp[i]) {
                    dp[rewardValue+i] = true;
                    maxx = max(rewardValue+i,maxx);
                }
            }
        }
        for(int i=maxx;i>=0;--i){
            if (dp[i]) return i; 
        }
        return 0;
    }
};

Q4：3181. 执行操作可获得的最大总奖励 II

题目传送门：3181. 执行操作可获得的最大总奖励 II - 力扣（LeetCode）

该题相比上一题就是数据范围变大了一些，从2000变为了50000，因此上一题的做法无法直接用进来，需要一些优化。观察到我们的DP数组是一个bool数组，因此考虑可以用bitset进行优化。

将bool DP数组转化为一个二进制数后，选择数V相当于把当前二进制后V项左移V位和当前项进行或运算

因为Python对大数支持很好所以先展示Python代码：

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        rewardValues.sort()
        dp = 1
        for rewardValue in rewardValues:
            mask = (1<<rewardValue) - 1 # 生成mask选取最后v个项
            dp |= (dp&mask)<<rewardValue
        return dp.bit_length() - 1

CPP由于不支持大数不能像Python一样实现的这么直接，需要使用bitset库，bitset库详细用法见C++教程栏目。

此外还需注意的是，对于mask的生成不能像Python一样先定义一个全1 mask进行求并集运算，而是要采用先左移后右移的方式。

CPP最后实现代码如下：

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        bitset<100000> dp(1);
        for (auto rewardValue : rewardValues) {
            int shift = dp.size() - rewardValue;
            dp |= (dp<<shift>>shift)<<rewardValue;
        }
        for(int i=rewardValues.back()*2-1;;i--){
            if(dp.test(i)) return i;
        }
    }
};

时间复杂度

时间复杂度上，使用bitset优化的DP相比原来的数组DP能够提供32倍到64倍速度上的优化（取决于机器是32位还是64位的）