传送门
题外话
被 CF 上的题解硬控半小时都不懂啊真的读不懂。
题目思路
由题意中的式子可知：如果要对位置 \(i\) 进行一次操作，\(a\) 的长度必须满足 \(|a| = a_i + i -1\)。如果对位置 \(i\) 进行一次操作，\(a\) 的长度会增加 \(i-1\) 位。
稍微能看出：操作前对 \(a\) 的长度有所要求，操作完后对 \(a\) 的长度有所贡献。
不妨以 \(a\) 的可能的长度为节点建图。对于每一个 \(i\)，从操作前要求的长度指向操作后的长度。最后从 \(n\) 跑一次 dfs 即可。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int n,a[N];
map<int,vector<int> >g;
set<int>s;
void init(){g.clear();s.clear();
}
void dfs(int u){if(s.count(u)) return ;s.insert(u);for(int v:g[u]) dfs(v);
}
void solve(){cin>>n;init();for(int i=1;i<=n;i++){cin>>a[i];int u=a[i]+i-1,v=u+i-1;//u 执行操作所需的当前长度//v 执行操作后得到的新长度g[u].push_back(v);}dfs(n);//当前长度 cout<<*s.rbegin()<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0);int t;cin>>t;while(t--) solve();return 0;
}