专栏文章

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

ffish_love_cat
P12288题解参与者 9已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@minh86sx
此快照首次捕获于
2025/12/02 02:22
3 个月前
此快照最后确认于
2025/12/02 02:22
3 个月前
查看原文
要求写一个数据结构，支持单点删除，末尾增加，快速求前后数字。
考虑双向链表。
我们对于每个数字统计前后数字，删除的时候改一次贡献，增加的时候再改一次贡献就做完了。
正常链表写法就可以，由于第一次插入不需要删除，所以还要记录一个 vis 数组。
不要忘记二次插入某个数字时清空删除前的维护信息。
CPP
#include<bits/stdc++.h>
using namespace std;
struct fish{
    int pre,nxt;
    bool vis;
}a[1000005];
int lst=-1,ans;
int main(){
    int n,x;
    cin>>n>>x,n--;
    a[x].pre=a[x].nxt=-1;
    a[x].vis=1;
    lst=x;
    puts("0");
    while(n--){
        cin>>x;
        if(a[x].vis){
            if(a[x].pre!=-1)
            ans-=(x+a[x].pre)&1;
            if(a[x].nxt!=-1)
            ans-=(x+a[x].nxt)&1;
            if(a[x].pre!=-1&&a[x].nxt!=-1)
            ans+=(a[x].pre+a[x].nxt)&1;
            if(a[x].pre!=-1)
            a[a[x].pre].nxt=a[x].nxt;
            if(a[x].nxt!=-1)
            a[a[x].nxt].pre=a[x].pre;
            if(a[x].nxt==-1)lst=a[x].pre;
        }
        a[x].pre=lst;
        a[x].vis=1;
        a[x].nxt=a[lst].nxt;
        if(lst!=-1)
        a[lst].nxt=x,ans+=(lst+x)&1;
        lst=x;
        cout<<ans<<'\n';
    }
    return 0;
}
//「是啊。虽然不清楚，但我大概回应不了你的期待。我一直都是这样。无论是谁的期望，我都回应不了。」

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...