日常训练2025-1-16

C. Add Zeros

rating：1500

https://codeforces.com/problemset/problem/2027/C

思路（转化为图）

我们把公式化成 |a| = a_i + i - 1，即满足这个公式的位置会给长度加 i - 1

所以相当于从 a_i + i - 1 ----> a_i + i - 1 + i - 1 建一条有向边，跑一个 dfs 即可。

评述

写dfs，和bfs的时候一定要写vis数组，千万别相信愚蠢的直觉。

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n;
	std::cin >> n;

	std::map<i64, bool> vis;
	std::map<i64, std::vector<i64>> mp;
	std::vector<i64> a(n+1);
	for (int i = 1; i <= n; i++){
		std::cin >> a[i];
		mp[a[i]+i-1].emplace_back(a[i]+2*(i-1));
	}

	i64 ans = n;
	auto dfs = [&](auto self, i64 p) -> void {
		vis[p] = 1;
		ans = std::max(ans, p);

		for (auto to : mp[p]){
			if (!vis[to]){
				self(self, to);
			}
		}

	};

	dfs(dfs, n);

	std::cout << ans << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	std::cin >> t;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}