CF1753A1

前言

题目传送门！

更好的阅读体验？

提供一种更加好理解的方法。

思路

关键点：只要凑够就行，不需要区间数量最小。

首先，每个数是 \(-1\) 或 \(1\)，说明 \(n\) 为奇数时，必定无解。

我们看相邻两个数 \(a_i\) 与 \(a_{i + 1}\)：显然有四种可能，\((-1, -1), (-1, 1), (1, -1), (1, 1)\)。

其中，\((-1, 1)\) 与 \((1, -1)\) 不需要动，他们的和就是 \(0\) 了。我们可以用两个区间 \([i, i]\) 与 \([i + 1, ui + 1]\) 表示。

而 \((-1, -1)\) 与 \((-1, 1)\) 需要通过改变后一个数的符号，和才能是 \(0\)。所以我们可以用区间 \([i, i + 1]\) 表示。

统计全部区间就完成了。

这个办法好处是，特别好想好写。缺点是，加强版还要改一点东西。

但是能过这一题就够啦。

代码

//赛时代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], l[N], r[N];
void solve()
{
	int n, cur = 0;
	cin >> n;
	if (n & 1)
	{
		for (int i = 1, x; i <= n; i++) cin >> x;
		cout << "-1\n";
		return;
	}
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 2; i <= n; i += 2)
		if (a[i - 1] + a[i] == 0)
		{
			l[++cur] = i - 1, r[cur] = i - 1;
			l[++cur] = i, r[cur] = i;
		}
		else l[++cur] = i - 1, r[cur] = i;
	cout << cur << '\n';
	for (int i = 1; i <= cur; i++) cout << l[i] << ' ' << r[i] << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

希望能帮助到大家！

原文地址：http://www.cnblogs.com/liangbowen/p/16823086.html