题解贪吃蛇

xiaolilsq · 2020-11-08 21:48:44 · 题解

题解贪吃蛇

题目链接

可能更好的阅读体验

一组可能可以 hack 掉你的代码的数据：

input:
1
15
0 1 2 2 2 2 3 3 4 5 5 6 7 8 8
output:
8

题目分析

本篇题解参考了 EI 的一篇 blog ，实现有部分不同，建议大家去看看原文。

不难发现，操作序列是固定的，也就是说，如果吃蛇游戏进行了 i 轮，那么第 j(1\le j\le i) 轮的选择是固定的，所以我们可以把问题分解为“求每一轮是哪条蛇吃掉了哪条蛇”和“已知每一轮的吃蛇情况，求出答案”。

首先考虑“已知每一轮的吃蛇情况，求出答案”，不妨假设第 i 轮的吃蛇情况是 A_i 吃掉了 B_i ，考虑从后往前递推，由于每条蛇都不想被吃掉，所以如果在第 i 轮中， A_i 选择吃掉 B_i ，那么必须要满足在第 i+1 轮及以后中 A_i 都不会被吃掉，否则 A_i 肯定会直接结束游戏，用一个桶来统计就可以得到答案了。

然后考虑“求每一轮是哪条蛇吃掉了哪条蛇”，这个很容易用平衡树或者堆等数据结构来维护，就是每次找出最大的和最小的，然后两个相减再放回去，但是这样的复杂度是 \mathcal O(Tn\log_2n) 的，不够优秀。

不妨假设所有的蛇的实力从小到大实力一样编号从小到大依次为 a_1,a_2,\dots,a_n ，如果 a_n\ge 2a_1 ，那么 a_n-a_1\ge a_1 ，此时最大值一定是不增的，最小值一定是不降的，可以用一个队列来维护，每次都把最大值减去最小值加入到队列中，不难发现，这个队列一定是单调的，这个套路和 “NOIP2016蚯蚓” 是一样的，我们使用一个队列来维护答案，直到最大值小于最小值的两倍。

此时 a_n<2a_1 ，此时 a_1\ne 0 ，可以得到每次取出的最大值减去最小值的值是多少：

第一次操作，最大值减去最小值为 a_n-a_1<a_1 。
第二次操作，最大值减去最小值为 (a_{n-1}-a_n)+a_1\le a_1 。
第三次操作，最大值减去最小值为 (a_{n-2}-a_{n-1})+a_n-a_1<a_1 。
......

需要注意的是，上面说的是“值”，但是实际比较大小的时候我们还需要比较编号。

不难发现，最小值最大也是 a_1 ，所以我们可以使用一个数据结构来维护值为 a_1 的所有的编号，首先不妨假设 a_1=a_2=\cdots=a_m<a_{m+1}\le\cdots\le a_n ，那么在接下来 n-m 轮中，每一轮的最大值依次为 a_{n\sim m+1} 。

先考虑这 n-m 轮，最大值固定，如何维护最小值？可以使用类似 \mathcal O(n) 构造 prufer 序列的思路，用一个类似指针的东西来表示值为 a_1 的所有编号中最小的是什么，然后每次“最大值减去最小值”如果比这个指针的值要小，或者等于这个指针的值但是编号小于这个指针的编号的话，这个“最大值减最小值”就是下一次的最小值，下一次一定会被删除，否则的话下一次的最小值就是这个指针指着的值，然后让指针跳下一个就行了，不难发现，这部分的时间复杂度是 \mathcal O(n) 。

然后考虑后面 m 轮，此时剩下的只有两种情况，一种情况是有一个值小于 a_1 ，其他值都等于 a_1 ，另一种情况是所有值都等于 a_1 。

如果有一个值小于 a_1 ，不妨设为 x ，那么 x>0 （因为 n-m 轮中的最后一轮的最大值为 a_{m+1}>a_1 ，而每一轮的最小值都 \le a_1 ），于是最小值就依次是 x,a_1-x,x,a_1-x,\dots ，所以一开始最大的蛇肯定会吃掉一开始小于 a_1 的蛇，后面的蛇就吃掉上一次吃东西的蛇。

如果所有值都等于 a_1 ，那么一开始最大的蛇肯定会吃掉次小的蛇，然后实力变成 0 ，然后被次次小的蛇吃掉，然后次次小的蛇变成最大的蛇，一直继续下去。

这部分的时间复杂度也是 \mathcal O(n) 。

综上，总的时间复杂度为 \mathcal O(Tn) 。

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
    static int f;static char c;
    for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
    static int q[64];int cnt=0;
    if(x==0)return pc('0'),void();
    if(x<0)pc('-'),x=-x;
    while(x)q[cnt++]=x%10,x/=10;
    while(cnt--)pc(q[cnt]+'0');
}
const int maxn=1000005;
int n,a[maxn],q0[maxn],q1[maxn],q2[maxn],A[maxn],B[maxn],in[maxn],cp[maxn],c2;
int hp[maxn];
void solve2(int st){
    for(int i=1;i<=n;++i)hp[i]=false;
    int key=a[q2[0]],p=1;hp[q2[0]]=true;
    while(p<c2&&a[q2[p]]==key)hp[q2[p]]=true,++p;
    int e=p,MN=0;p=1;while(!hp[p])++p;
    for(int i=c2-1;i>=e;--i){
        A[st]=q2[i];
        if(MN){
            B[st]=MN;
            if(((a[q2[i]]-=a[MN])<key)||q2[i]<p)
                MN=q2[i];
            else{
                MN=0;hp[q2[i]]=true;
            }
        }
        else{
            B[st]=p;hp[p]=false;++p;
            while(p<=n&&!hp[p])++p;
            a[MN=q2[i]]-=key;
        }
        ++st;
    }
    if(MN&&a[MN]==key){
        hp[p=MN]=true;MN=0;
    }
    if(MN){
        for(int i=n;i>=1;--i)if(hp[i]){
            A[st]=i;B[st]=MN;++st;MN=i;
        }
    }
    else{
        int o=0;
        for(int i=n;i>=1;--i)if(hp[i]){
            o^=1;
            if(o){
                if(MN){
                    A[st]=i,B[st]=MN;++st;
                }
                MN=i;
            }
            else{
                A[st]=MN;B[st]=i;++st;
            }
        }
    }
}
void solve(void){
    for(int i=1;i<=n;++i)cp[i]=a[i],in[i]=0;
    int f0=0,b0=0,f1=n,b1=n;
    for(int i=1;i<=n;++i)q0[b0++]=i;
    for(int i=1;i<n;++i){
        int mx=-1,mxp=0;
        if(f0<b0&&(a[q0[b0-1]]>mx||(a[q0[b0-1]]==mx&&q0[b0-1]>mxp)))mx=a[mxp=q0[b0-1]];
        if(f1<b1&&(a[q1[b1-1]]>mx||(a[q1[b1-1]]==mx&&q1[b1-1]>mxp)))mx=a[mxp=q1[b1-1]];
        int mn=1000000001,mnp=n+1;
        if(f0<b0&&(a[q0[f0]]<mn||(a[q0[f0]]==mn&&q0[f0]<mnp)))mn=a[mnp=q0[f0]];
        if(f1<b1&&(a[q1[f1]]<mn||(a[q1[f1]]==mn&&q1[f1]<mnp)))mn=a[mnp=q1[f1]];
        if(a[mxp]<a[mnp]*2){
            int _l=f0,_r=f1;c2=0;
            while(_l<b0||_r<b1){
                if(_r>=b1||(_l<b0&&(a[q0[_l]]<a[q1[_r]]||(a[q0[_l]]==a[q1[_r]]&&q0[_l]<q1[_r])))){
                    q2[c2++]=q0[_l++];
                }
                else{
                    q2[c2++]=q1[_r++];
                }
            }
            solve2(i);
            break;
        }
        A[i]=mxp;B[i]=mnp;
        if(f0<b0&&q0[f0]==mnp)++f0;else ++f1;
        if(f0<b0&&q0[b0-1]==mxp)--b0;else --b1;
        a[mxp]-=a[mnp];q1[--f1]=mxp;
    }
    int no=n;
    for(int i=n-1;i>=1;--i){
        ++in[B[i]];
        if(in[A[i]])
            while(no>i)--in[B[--no]];
    }
    --no;
    for(int i=1;i<=n;++i)a[i]=cp[i];
    write(n-no),pc('\n');
}
int main(){
    int T;read(T),read(n);
    for(int i=1;i<=n;++i)read(a[i]);
    solve();--T;
    while(T--){
        int k;read(k);
        while(k--){
            int x,y;
            read(x),read(y);
            a[x]=y;
        }
        solve();
    }
    return 0;
}

题解 贪吃蛇

题解 贪吃蛇

题目分析

参考代码

题解贪吃蛇

题解贪吃蛇