题解 CF1491C 【Pekora and Trampoline】
SSerxhs
2021-03-01 10:34:17
提供一种 $O(\sum n)$ 的做法。
注意到操作顺序对序列没有影响,可以考虑每次都从 $\min\limits_{a_i\ne 1} \{i\}$ 开始(因为它不能被其他非 $1$ 点跳到)。
记 $i$ 被 $f_i$ 次跳到
1. 若 $f_i< a_i-1$
还需要从 $i$ 出发跳 $a_i-1-f_i$ 步,且包括之前跳的恰好跳到 $[i+1,\min(i+a_i)]$ 各一次,为了维护 $f_i$ 只需对这个区间做区间修改,可以差分实现。
2. 若 $f_i\ge a_i-1$
包括之前跳的恰好跳到 $[i+2,\min(i+a_i)]$ 各一次,且跳到 $i+1$ 共 $f_i-a_i$ 次,同上处理即可。
从左到右扫一次,$ans=\sum\limits_{i=1}^n \max{(0,a_i-1-f_i)}$
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
std::mt19937 rnd(time(0));
inline int sj(int n)
{
unsigned int x=rnd();
return x%n+1;
}
#define rand fst
template<typename typC> void read(register typC &x)
{
register int c=getchar(),fh=1;
while ((c<48)||(c>57))
{
if (c=='-') {c=getchar();fh=-1;break;}
c=getchar();
}
x=c^48;c=getchar();
while ((c>=48)&&(c<=57))
{
x=x*10+(c^48);
c=getchar();
}
x*=fh;
}
template<typename typC> void write(register typC x)
{
if (x<0) putchar('-'),x=-x;
static int st[100];
register int tp=1,y;st[1]=x%10;x/=10;
while (x) y=x/10,st[++tp]=x-y*10,x=y;++tp;
while (--tp) putchar(st[tp]|48);
}
template<typename typC> void write(register typC *a,register int num)
{
for (register int i=1;i<=num;i++) write(a[i]),putchar(i==num?10:32);
}
#define space(x) write(x),putchar(32)
#define enter(x) write(x),putchar(10)
const int N=5e3+2;
ll ans;
ll f[N],g[N];
int a[N];
int T,n,m,c,i,j,k,x,y,z,la;
int main()
{
T=1;read(T);
while (T--)
{
read(n);ans=0;
for (i=1;i<=n;i++) read(a[i]);
memset(f+1,0,n<<3);
memset(g+1,0,n<<3);
for (i=1;i<=n;i++)
{
f[i]+=(g[i]+=g[i-1]);
if (f[i]<a[i]-1) ans+=a[i]-1-f[i]; else f[i+1]+=f[i]-(a[i]-1);
++g[i+2];--g[1+min(n,i+a[i])];
}
printf("%lld\n",ans);
}
}
```