题解：P12288 [蓝桥杯 2024 国 Java A] 栈

· · 题解

这是一道有点思维性的题目，我们可以找到两个老朋友来解决问题：

双向链表：便于维护元素顺序。

哈希表：记录每个元素在链表中的位置，实现 O (1) 时间的元素存在性检查和定位。

好，然后我们就确定了基本思路，可以开始做题了：

算法步骤（我分了二步）

处理重复元素：

若元素已存在，就通过哈希表找到其在链表中的位置，然后计算删除该元素对奇数对数量的影响。若该元素前后都有元素，要考虑前后元素合并后的新贡献，然后分别减去该元素与前、后元素的奇数对贡献。最后从链表中删除该元素，并从哈希表中移除记录就好。

添加新元素：

先将新元素添加到链表尾部，然后计算新元素与前一个元素的奇数对贡献，并更新结果，最后在哈希表中记录新元素的位置。

上代码！（有注释，方便理解）：

#include<iostream>
#include<list>
#include<unordered_map>
using namespace std;
struct Node{
    int val;
    list<int>::iterator it; // 记录元素在链表中的迭代器
};

int main() {
    int n;
    cin >> n;

    list<int> lst; // 双向链表模拟栈
    unordered_map<int, Node> pos; // 哈希表记录元素位置
    int ans = 0; // 记录奇数对数量

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        // 处理重复元素
        if (pos.find(num) != pos.end()) {
            auto it = pos[num].it; // 获取重复元素的迭代器

            // 判断是否有前一个和后一个元素
            bool has_prev = (it != lst.begin());
            bool has_next = (it != --lst.end()); // 等价于 next(it) != lst.end()

            // 情况1：元素前后都有元素，需计算前后元素合并的贡献
            if (has_prev && has_next) {
                auto prev_it = it;
                --prev_it; // 前一个元素
                auto next_it = it;
                ++next_it; // 后一个元素
                if ((*prev_it + *next_it) % 2 == 1) {
                    ans++; // 前后元素合并可能新增一个奇数对
                }
            }
            // 情况2：减去当前元素与前一个元素的贡献
            if (has_prev) {
                auto prev_it = it;
                --prev_it;
                if ((*prev_it + *it) % 2 == 1) {
                    ans--; // 删除前，当前元素与前一个元素的奇数对减少
                }
            }
            // 情况3：减去当前元素与后一个元素的贡献
            if (has_next) {
                auto next_it = it;
                ++next_it;
                if ((*it + *next_it) % 2 == 1) {
                    ans--; // 删除前，当前元素与后一个元素的奇数对减少
                }
            }

            // 从链表中删除元素，并清空哈希表记录
            lst.erase(it);
            pos.erase(num);
        }

        // 添加新元素到链表尾部
        lst.push_back(num);
        auto it = --lst.end(); // 获取新元素的迭代器

        // 计算新元素与前一个元素的贡献
        if (it != lst.begin()) { // 若不是第一个元素
            auto prev_it = it;
            --prev_it; // 前一个元素
            if ((*prev_it + *it) % 2 == 1) {
                ans++; // 新增一个奇数对
            }
        }

        // 记录新元素的位置到哈希表
        pos[num] = {num, it};

        // 输出当前结果
        cout << ans << endl;
    }

    return 0;
}

求赞求过。