P7078 || [CSP-S2020] 贪吃蛇

kanlla · 2025-05-20 19:56:08 · 题解

省队学长给我们拉的模拟赛的 T4，没想到还能交题解，这下不得不写我的第一篇黑题题解来纪念了。

思路

70pts

先引出结论：当最大的蛇吃了后没有变成最小的蛇，它一定会吃；否则需要递推进行决策。

下面解释为什么一定会吃。令初始时蛇的能力为 A_1,A_2,\dots,A_n，那么它们一定是单调不降的。若未变成最小的蛇，那么说明 A_n-A_1\ge A_2，如果 n-1 不吃，那么游戏结束，n 会吃；否则一定有 A_{n-1}-A_2\le A_n-A_1，那么 n-1 一定会死在 n 前面，所以 n 也会吃。

而当最大蛇吃掉后变成了最小蛇，若次大蛇经过一系列头脑风暴后选择不吃，那它就会白吃一回合；否则它不吃。正着决策显然困难，所以选择倒着推回去。

我们可以使用 set 维护这一过程。具体地，先假设所有蛇都不聪明，每条蛇都一定会吃，模拟一轮后可以得到每轮最大的蛇 eat_i 和最小的蛇 beat_i。再倒着往前推，定义 del_i 为每条蛇的死亡时间，若 del_{eat_i}\ge ans，则说明在它死前游戏就已经结束了，因此可以吃，同时将 del_{beat_i} 设成 i；否则不吃，将 ans 更新为 i。

100pts

上述做法中瓶颈在于 set 的时间复杂度，我们考虑能否用线性结构进行维护。使用双端队列真是再合适不过了！

具体地，开两个双端队列 st1,st2，st1 用来维护未进食过的蛇，st2 维护进食过的蛇。容易发现，除了一种情况外，两个队列一定是具有单调性的。我们先假定两个队列都是队尾最弱，队头最强，下面给出证明：

这一轮进食完毕后的蛇的能力值一定是 \max(st1_l,st2_l)-\min(st1_r,st2_r)。分讨一下，发现由于 max 的值一定是单调不升的，因此我们主要对 min 作讨论。记第 i 轮的 min 为 min_i，得到以下情况：

若 min_i=st1_r，那么一定符合单调性：若 min_{i-1} 来自 st1，那么一定有 min_{i-1}\le min_i，因此此轮能力值一定小于上一轮；若 min_{i-1} 来自 st2，那么说明它比 st1_r 后面的那个值大，因此依旧有 min_{i-1}\le min_i，于是同理。
若 min_i=st2_r，那就不一定符合单调性了。如果符合单调性就依旧满足，否则的那种情况会在下面提到。

对于出现不满足单调性的情况，那就只能是当前值比 st2_r 大，即 st2_r 要被吃掉。那么在这种情况下 st2_r 就会选择在上一轮停手。于是你发现这和“剩两条蛇，如果较小的那条能反悔，它一定会反悔”的逻辑是一样的。于是我们就可以从这个时候开始往回推，而不是一定要全部模拟完了。

代码

#include<set>
#include<queue>
#include<iostream>
#define int long long
using namespace std;
const int N=1e6+5;
int _anll_,t;
int n,m,ans,tim,A[N],del[N],eat[N],beat[N];
deque<pair<int,int> > st1,st2;
void solve(bool _anll_){
    if(!_anll_){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>A[i];
    }
    else{
        cin>>m;int a,b;
        while(m--) cin>>a>>b,A[a]=b;
    }
    tim=-1,ans=1;
    while(st1.size()) st1.pop_back();
    while(st2.size()) st2.pop_back();
    for(int i=1;i<=n;i++)
        st1.push_back({A[i],i}),
        eat[i]=beat[i]=del[i]=0;
    for(int i=n;i>1;i--){
        pair<int,int> mx,mn,an;
        if(st1.size()&&st2.size()){
            if(st1.back()>st2.back())
                 {mx=st1.back();st1.pop_back();}
            else {mx=st2.back();st2.pop_back();}
        }
        else if(st1.size())
             {mx=st1.back();st1.pop_back();}
        else {mx=st2.back();st2.pop_back();}
        if(st1.size()&&st2.size()){
            if(st1.front()<st2.front())
                 {mn=st1.front();st1.pop_front();}
            else {mn=st2.front();st2.pop_front();}
        }
        else if(st1.size())
             {mn=st1.front();st1.pop_front();}
        else {mn=st2.front();st2.pop_front();}
        beat[i]=mn.second,eat[i]=mx.second;
        an={mx.first-mn.first,mx.second};
        if(st2.size()&&an>st2.front()){
            ans=tim=i;break;
        }
        st2.push_front(an);
    }
    if(tim==-1) tim=2;
    for(int i=tim;i<=n;i++){
        int x=eat[i];
        if(del[x]>=ans) ans=i;
        else del[beat[i]]=i;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int i=0;i<t;i++) solve(i);
    return 0;
}