CF1491C Pekora and Trampoline

· · 题解

原题链接 洛谷链接
题目翻译
我的Blog

题意就不赘述了

考虑贪心，显然每轮最开始调到第一个 s_i 不为 1 的蹦床上是最优的，因为这样可以让后面的 s 尽可能减少。
定义 c_i 为位置 i 已经被踩了多少次

那么，我们贪心的从 1 开始枚举跳到的第一个蹦床，设当前枚举到第 i 个蹦床
由于最终这个蹦床的 s_i 会被踩到只剩 1，所以肯定会对区间 [i+2,\min(i+s_i,n)] 的蹦床造成 1 点贡献（后面会讲到对 i+1 的贡献） 由于在正常情况下，当蹦床的 s_i 达到 1 的时候，就不会再从它开始起跳了，所以这样就不会对 i+1 造成贡献。只有当 s_i-c_i<1 的时候，也就是说从别的地方跳过来，才可以对 i+1 做出贡献。所以蹦床 i 对 i+1 做出的贡献为 \max(0,1-(s_i-c_i))

在考虑完对后面蹦床的贡献后，我们考虑蹦床 i 对最终答案的贡献。这个其实非常简单，就不细说了，贡献：\max(0,(s_i-c_i)-1)

总时间复杂度 \mathcal O(T\cdot n\log n)
PS: 为了美观并且方便理解，这里只提供未开 long long 的代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int Maxn=5010;
int n,ans;
int a[Maxn],sum[Maxn];
inline int lowbit(int x)
{
    return x&(-x);
}
void modify(int x,int v)
{
    if(x>n || x<1)return;
    while(x<=n)
    {
        sum[x]+=v;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int ret=0;
    while(x)
    {
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int main()
{
    // freopen("in.txt","r",stdin);
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;++i)
        a[i]=read(),sum[i]=0;
        for(int i=1;i<=n;++i)
        {
            int tmp=a[i]-query(i);
            if(tmp>1)
            ans+=tmp-1;
            if(a[i]>1)
            modify(i+2,1),modify((i+a[i])+1,-1);
            if(tmp<1ll)
            modify(i+1,1-tmp),modify(i+2,tmp-1);
        }
        printf("%lld\n",ans);
        ans=0;
    }
    return 0;
}

Update: 03.04: 发现这个做法好像可以优化到 \mathcal O(n)。
我们把树状数组换成差分，但看上去似乎差分只能支持区间修改，不支持在线的查询。
但是，可以发现这些操作具有一些良好的性质：

  1. 查询操作是从前往后依次查询的，也就是 1\dots n 的位置都被挨个查了一遍。
  2. 当我们查询完位置 i，之后的所有修改都不会跟 1\dots i 有关系。

那么，我们可以在枚举蹦床的时候维护差分数组，也就是 sum[i]+=sum[i-1]。这样，单次查询和修改就都是 \mathcal O(1) 的了。
总时间复杂度 \mathcal O(n)。

代码仍旧未开 long long

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int Maxn=5010;
int n,ans;
int a[Maxn],sum[Maxn];
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int main()
{
    // freopen("in.txt","r",stdin);
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;++i)
        a[i]=read(),sum[i]=0;
        for(int i=1;i<=n;++i)
        {
            sum[i]+=sum[i-1];
            int tmp=a[i]-sum[i];
            if(tmp>1)
            ans+=tmp-1;
            if(a[i]>1)
            {
                if(i+2<=n)
                sum[i+2]++;
                if(i+a[i]+1<=n)
                sum[i+a[i]+1]--;
            }
            if(tmp<1)
            {
                if(i+1<=n)
                sum[i+1]+=(1-tmp);
                if(i+2<=n)
                sum[i+2]-=(1-tmp);
            }
        }
        printf("%lld\n",ans);
        ans=0ll;
    }
    return 0;
}