526互联

Codeforces Global Round 21 B. NIT Destroys the Universe

发布时间 2023-09-10 21:29:33作者: zsxuan

给一个长为 \(n\) 的数组，可以执行以下操作任意次：

  • 选择 \(l, r(1 \leq l < r \leq n)\) ，让 \(\forall i(l \leq i \leq r), a_i = mex(\{a_l, a_{l+1}, \cdots, a_{r}\})\) 。

问最小操作数使得 \(\forall i, a_i = 0\) 。

观察：答案 \(\leq 2\) ，因为对 \([1, n]\) 操作不超过两次即可使 \(max_{i=1}^{n} a_i = 0\) 。

经典问题：左右端点处的连续合法区间舍去。

如果全为 \(0\) ，则不存在非 \(0\) 位，不需要操作。

否则到左起第一个非 \(0\) 位 \(l\) ，右起第一个非 \(0\) 位 \(r\) 。

  • 若 \(\min_{i = l}^{r} a_i = 0\) ，则需操作 \(2\) 次。
  • 若 \(\min_{i = l}^{r} a_i = 1\) ，则需操作 \(1\) 次。
view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1, x; i <= n; i++) {
		std::cin >> a[i];
	}
	if (std::count(a.begin() + 1, a.end(), 0) == n) {
		std::cout << 0 << '\n';
		return;
	}
	int l = 1, r = n;
	while (a[l] == 0) l += 1;
	while (a[r] == 0) r -= 1;	
	if (std::count(a.begin() + l, a.begin() + r + 1, 0) > 0) std::cout << 2 << '\n';
	else std::cout << 1 << '\n';

}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}

若不先考虑是否全为 \(0\) ，直接寻找非 \(0\) 位的做法是不优的。

如

一种不优做法 
int l = 1, r = n;
while (l < n && a[l] == 0) l++;
while (r > 1 && a[r] == 0) r--;

最后根据 \(l, r\) 位置判断的做法是不优的。比如理论上 \(l > r\) 直观上容易认为当且仅当全是 \(0\) 成立。

但当 \(n = 1, a_1 = 0\) ，会得到 \(l = r\) 。需要追加考虑。

这在思维逻辑性上是不强且更复杂的。