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

_Hzq_ · 2025-08-15 16:01:58 · 题解

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

题意分析

题目要求我们模拟一个栈，但与普通的栈不同的是，栈中不会出现相同的元素，相同的元素只会保留后插入的那一个，问我们每一次插入后在栈中相邻的数的和为奇数的个数，读完题目，我们便很容易能想到模拟。

具体做法

这里介绍一种不同的做法，双向链表。

:::info[什么是双向链表] 不同于数组，双向链表是一种非线性数据结构，其储存地址并不连续，采用前后指针的方式将各个数据串联起来，因此，双向链表在查询某一个特定元素时特别麻烦。 :::

在这题中，每一个元素在栈中只会出现一次，而且 1\leq a_i\leq10_6，刚好弥补了链表查询困难的缺点，我们只需用一个桶存每一种元素出现的最后的地址就可以了。\ 得益于使用双向链表，本题的删除操作异常简单，只需将要删除的节点的左节点的右节点改为节点的右节点，右节点在同理操作便可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct node
{
    int val;
    node* left;
    node* right;
};
int n,res;
node* lastx[N];
node* tail;
int main()
{
    cin >> n;
    int i,j,k,x;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        node* temp=new node();
        temp->val=x;
        temp->left=tail;
        if(tail!=NULL) //插入元素x
        {
            tail->right=temp;
            if((tail->val+x)%2==1) res++;
        }
        if(lastx[x]!=NULL) //删除之前存在过的元素x
        {
            if(lastx[x]->left!=NULL)
            {
                if((lastx[x]->val+lastx[x]->left->val)%2==1) res--;
                lastx[x]->left->right=lastx[x]->right;
                if((lastx[x]->left->val+lastx[x]->right->val)%2==1) res++;
            }
            lastx[x]->right->left=lastx[x]->left;
            if((lastx[x]->val+lastx[x]->right->val)%2==1) res--;
        } 
        lastx[x]=temp;
        tail=temp;
        cout << res << endl;
    }
    return 0;
}

温馨提示

使用链表需小心，一不小心就 RE\ 由于空指针的特殊性，直接使用空指针中的值会 RE，如

lastx[x]->val=1;

所以，我们在使用指针前要判断一下它是否为空。