专栏文章

题解：CF2027C Add Zeros

MMeickol
CF2027C题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip4kmud
此快照首次捕获于
2025/12/03 06:03
3 个月前
此快照最后确认于
2025/12/03 06:03
3 个月前
查看原文

记忆化搜索 + 图论建模

由于每次操作后是对序列的末尾插入 00，显然后面插入的这些 00 对应的位置 ii 一定不满足 ai=∣a∣+1−ia_i = |a| + 1 -i 这个式子，所以后面插入的这些 00 对应的下标 ii 完全不需要纳入考虑范围。
也就是说我们只需要考虑一开始数组中存在的下标 i∈[1,n]i \in [1,n] 进行考虑即可，并且每次操作后 ∣a∣|a| 呈现单调递增，而每次操作也不会让 aia_i 的值改变，这意味着每个下标 ii 的值最多只会操作一次。
对于题目的 ai=∣a∣+1−ia_i = |a| + 1 -i 这个条件显然可以转化为 ∣a∣=ai+i−1|a|=a_i+i-1，当该式成立时会使 ∣a∣←∣a∣+i−1|a| \leftarrow |a|+i-1，于是考虑从图论的角度建立一张 DAG 图，即对点 ai+i−1a_i+i-1 向 ai+i−1+i−1a_i+i-1+i-1 连一条有向边边，表示当 ∣a∣=ai+i−1|a|=a_i+i-1 时 ∣a∣|a| 可以变为 ∣a∣+i−1|a|+i-1。
当按照上述规则进行建图后，再从 nn 进行 dfs，维护一下 dfs 过程中遇到的最大点权即可。点权就表示数组长度。
由于 aa 数组值域很大，需要用 map 来存储。
同时搜索需要记忆化，否则会 TLE。
代码如下：
CPP
#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=3e5+5;
int n;
LL a[N];
map<LL,bool> vis;
map<LL,vector<LL>> E;
LL ans;
void dfs(LL u){
	vis[u]=1;
	ans=max(ans,u);
	for(auto v:E[u]){
		if(vis[v]) continue;
		dfs(v);
	}
}
void solve(){
	vis.clear();
	E.clear();
	cin>>n;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n){
		LL u=a[i]+i-1;
		LL v=u+i-1;
		E[u].push_back(v);
	}
	ans=0;
	dfs(n);
	cout<<ans;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...