526互联

Codeforces Round 896 (Div. 2) A. Make It Zero

发布时间 2023-10-16 18:20:46作者: zsxuan

给一个大小为 \(n\) 的数组 \(a\) \((n \geq 2)\) 。你希望进过一些操作使得 \(\forall i, a_i = 0\) 。

在一步操作中，可以选择 \(1 \leq l \leq r \leq n\) 并且执行：

  • \(s = \bigoplus_{i = l}^{r} a_i\) 。
  • \(\forall l \leq i \leq r, a_i = s\) 。

输出一个解决方案，使得操作次数 \(\leq 8\) 。

观察到，第一步可以选择 \(l = 1, r = n\) 。于是 \(a = [x, x, \cdots, x]\) 。

  • 若 \(n\) 为偶数，再选择一次 \(l = 1, r = n\) ，则 \(a = [0, 0, \cdots, 0]\) 。
  • 否则
    • 选择 \(l = 1, r = n - 1\) ，使 \(a = [0, \cdots, 0, x]\) 。
    • 选择 \(l = n - 1, r = n\) ，使 \(a = [0, \cdots, x, x]\) 。
    • 选择 \(l = n - 1, r = n\) ，使 \(a = [0, \cdots, 0, 0]\) 。

\(n\) 为偶数最多需要操作两次，\(n\) 为奇数最多需要操作 \(4\) 次。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	if (~n & 1) {
		std::cout << 2 << '\n';
		std::cout << 1 << ' ' << n << '\n';
		std::cout << 1 << ' ' << n << '\n';
	}
	else {
		std::cout << 4 << '\n';
		std::cout << 1 << ' ' << n << '\n';
		std::cout << 2 << ' ' << n << '\n';
		std::cout << 1 << ' ' << 2 << '\n';
		std::cout << 1 << ' ' << 2 << '\n';
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}