Weekly-Contest-402

title: Weekly-Contest-402
date: 2024-06-16
Contest: leetcode
status: DONE
tags: Contest
Rank: 1686
Total: 3283
Credits: 7
T1: Accepted
T2: Accepted
T3: New Complement
T4: New Complement
author: AllenYGY
created: 2024-06-16T12:09
updated: 2024-06-22T16:18
publish: True

#T1 3184. 构成整天的下标对数目 I

给你一个整数数组 hours，表示以小时为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成整天的下标对 i, j 的数目。
整天定义为时间持续时间是 24 小时的 整数倍 。
例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

暴力没什么好说的

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        vector<int> remainderCount(24, 0);
        int count = 0;
        for (int hour : hours) {
            int remainder = hour % 24;
            int complement = (24 - remainder) % 24;
            count += remainderCount[complement];
            remainderCount[remainder]++;
        }
        return count;
    }
};

#T2 3185. 构成整天的下标对数目 II

模运算技巧+哈希优化


0	0
23	1
22	2
21	3
...	...
1	23

class Solution {
public:
    long long countCompleteDayPairs(vector<int>& hours) {
        vector<int> remainderCount(24, 0);
        long long count = 0;
        for (int hour : hours) {
            int remainder = hour % 24;
            int complement = (24 - remainder) % 24;
            count += remainderCount[complement];
            remainderCount[remainder]++;
        }
        return count;
    }
};

#T3 3185. 构成整天的下标对数目 II

统计每个元素的出现次数，记到哈希表 cnt 中。将哈希表的 key 整理到数组 a 中，把 a 按照从小到大的顺序排序。

定义 dfs(i) 表示从 a[0] 到 a[i] 中选择，可以得到的伤害值之和的最大值。

考虑 a[i] 选或不选：

不选：问题变成从 a[0] 到 a[i-1] 中选择，可以得到的伤害值之和的最大值，即。
选：那么伤害值等于 a[i]-2 和 a[i]-1 的数不能选，问题变成从 a[0] 到 a[j-1] 中选择，可以得到的伤害值之和的最大值，其中 j 是最小的满足的数。那么。
两种情况取最大值，得

递归边界：dfs(−1)=0。没有数可以选，伤害值之和为0。

递归入口：dfs(n−1)，即答案。注意这里 n 是 a 的长度，即 power 中的不同元素个数。

代码实现时，j 的计算可以用二分查找，也可以暴力用循环查找。

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int,int>cnt;
        for(int x:power){
            cnt[x]++;
        }
        vector<pair<int,int>>a(cnt.begin(),cnt.end());
        ranges::sort(a);
        int n = a.size();
        vector<long long>f(n+1);
        for(int i = 0, j=0; i < n; i++){
            auto& [x,c]=a[i];
            while(a[j].first < x - 2){
                j++;
            }
            f[i+1]=max(f[i],f[j]+(long long)x*c);
        }
        return f[n];
        
    }
};

#T4 3187. 数组中的峰值

树状数组

class Fenwick {
    vector<int> f;

public:
    Fenwick(int n) : f(n) {}

    void update(int i, int val) {
        for (; i < f.size(); i += i & -i) {
            f[i] += val;
        }
    }

    int pre(int i) {
        int res = 0;
        for (; i > 0; i &= i - 1) {
            res += f[i];
        }
        return res;
    }

    int query(int l, int r) {
        if (r < l) {
            return 0;
        }
        return pre(r) - pre(l - 1);
    }
};

class Solution {
public:
    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        Fenwick f(n - 1);
        auto update = [&](int i, int val) {
            if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
                f.update(i, val);
            }
        };
        for (int i = 1; i < n - 1; i++) {
            update(i, 1);
        }

        vector<int> ans;
        for (auto& q : queries) {
            if (q[0] == 1) {
                ans.push_back(f.query(q[1] + 1, q[2] - 1));
                continue;
            }
            int i = q[1];
            for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
                update(j, -1);
            }
            nums[i] = q[2];
            for (int j = max(i - 1, 1); j <= min(i + 1, n - 2); ++j) {
                update(j, 1);
            }
        }
        return ans;
    }
};