题解 CF1491C 【Pekora and Trampoline】

SSerxhs

2021-03-01 10:34:17

Solution

提供一种 $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); } } ```