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

第 434 场周赛解题（超详细）

article 2025/1/29 8:05:45

Q1：3432. 统计元素和差值为偶数的分区方案

思路：前缀和，枚举一遍下标就可以了

int countPartitions(vector<int> &nums) {  
    size_t n = nums.size();  
    vector<int> pre_sum(n);  
    pre_sum[0] = nums[0];  
    for (int i = 1; i < n; ++i) {  
        pre_sum[i] = pre_sum[i - 1] + nums[i];  
    }  
    int res = 0, totalSum = pre_sum[n-1];  
    for (int i = 0; i < n-1; ++i) {  
        if (!((totalSum - pre_sum[i] * 2) & 1)) {  
            ++res;  
        }  
    }  
    return res;  
}

Q2：3433. 统计用户被提及情况

这是工程类问题，实现起来easy，但是写起来troublesome。

/**  
 * 统计用户收到的通知次数  
 * @param numberOfUsers 用户数量 （用户id为0...n-1）  
 * @param events 事件日志列表  
 * @return 每个用户被通知的次数  
 */vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {  
    vector<int> mentions(numberOfUsers, 0);  // 用户i被通知的次数  
    vector<bool> online_status(numberOfUsers, true);    // 用户i的在线状态  
    unordered_map<int, int> offline_events;  // 记录每个用户离线的时间（其实这道题用户数量不超过100个，用数组也不会超时）  
  
    /*  
     * 甲方给的时间日志是乱序的，所以首先需要进行排序。@排序规则： 时间; ("OFFLINE","MESSAGE")  
     */    /*sort(events.begin(), events.end(), [](const vector<string>& a, const vector<string>& b) {        int timestampA = stoi(a[1]);        int timestampB = stoi(b[1]);        return timestampA < timestampB || (timestampA == timestampB && a[0] != "OFFLINE" && b[0] == "OFFLINE");    });*/    /*     * C++20提供了更人性化的排序函数  
     * std::ranges::sort(range, comparator, projection);     * range：要排序的容器（范围）。  
     * comparator：比较器。std::ranges::less{}（默认）。std::ranges::greater{}。  
     * projection：比较权值。这与Python里的比较逻辑一样。  
     */    ranges::sort(events, {}, [](auto &x){return make_pair(stoi(x[1]), x[0]!="OFFLINE"/*也可以找一个字典序比较*/);});  
  
  
    /// 遍历日志  
    for (const auto& event : events) {  
        string event_type = event[0];   // 事件类型  
        int timestamp = stoi(event[1]); // 时间戳  
        string data = event[2]; // 通知数据  
  
        // 检查是否有用户的离线时间到期，让其重新上线  
        // 这里使用指针遍历是为了删除更方便。如果使用迭代器遍历需要删除掉的是键，例如offline_events.erase(it.first)  
        for (auto it = offline_events.begin(); it != offline_events.end(); ) {  
            if (timestamp >= it->second) {  
                online_status[it->first] = true;  
                it = offline_events.erase(it);  
            } else {  
                ++it;  
            }  
        }  
  
        if (event_type == "OFFLINE") {  /// 处理离线事件  
            int user_id = stoi(data);  
            online_status[user_id] = false;  
            offline_events[user_id] = timestamp + 60;  // 离线到期时间  
        } else if (event_type == "MESSAGE") {  /// 处理消息事件  
            istringstream ss(data);  
            string mention; // 这里使用字节流处理空格分隔的数据  
  
            // 处理提及字符串  
            while (ss >> mention) {  
                if (mention == "ALL") {  // 提及所有用户  
                    for (int i = 0; i < numberOfUsers; ++i) {  
                        mentions[i]++;  
                    }  
                } else if (mention == "HERE") { // 提及所有在线用户  
                    for (int i = 0; i < numberOfUsers; ++i) {  
                        if (online_status[i]) {  
                            mentions[i]++;  
                        }  
                    }  
                } else {    // 提及指定用户  
                    mentions[stoi(mention.substr(2))]++;  
                }  
            }  
        }  
    }  
    return mentions;  
}

Q3：3434. 子数组操作后的最大频率

方法1：枚举 + 状态机 DP

思路：枚举 + 状态机 DP
状态：

0：修改前
1：修改中
2：修改后
对于子数组，我们不知道要加多少合适，于是可以枚举nums中的数（假设枚举到t），将子数组中等于t的数增加到k。

int maxFrequency1(vector<int>& nums, int k) {  
    unordered_set<int > nums_set(nums.begin(), nums.end()); // 去重  
    int ans = 0;  
    for (int t: nums_set) {  
        int f0=0,f1=INT_MIN, f2=INT_MIN;  
        for (int x: nums) {  
            f2 = max(f2, f1) + (x == k);  
            f1 = max(f1, f0) + (x == t);  
            f0 += (x == k);  
        }  
        ans = max({ans, f1, f2});  
    }  
    return ans;  
}

方法2：哈希表 + 状态机 DP

f[i]：将i增加到k（将子数组增加k-i），能获得的最大频率
遍历数组
ans：当前能获得的最大 k的个数
nPreK：前缀k的个数（包括当前）
当前：
- x == k：ans++, nPreK++
- x != k：
  - 只修改当前的x，f[x] = nPreK + 1
  - 和上一个值为当前x的元素一起修改，f[x] += 1
    答案即为max(f)

int maxFrequency(vector<int> &nums, int k) {  
    vector<int> f(51, 0);  
    int ans = 0, nPreK = 0;  
    for (int x: nums) {  
        if (x == k) {  
            ++ans, ++nPreK;  
        } else {  
            f[x] = max(f[x], nPreK) + 1;  
            ans = max(ans, f[x]);  
        }  
    }  
    return ans;  
}