Codeforces Round #829 (Div. 2)-C1

C1

题目链接：https://codeforces.com/contest/1754/problem/C1

emmm，不知道怎么说，做的时候考虑的问题是我通过什么方法来划分整个数组使得题意成立，后面又困在怎么判断是否存在的问题。

经过一番他人的点拨之后，才明白其实还是自己的想法不太成熟。“Note that it is not required to minimize the number of segments in the partition.”原文中的这句话一开始看其实没感觉有什么，但是现在看感觉和B好像，就是它仍旧是一个存在性问题！！！所以你只有能够找到一个适当的便捷的方法就行。

下面说说思路吧（来自官方题解的思路）

　　对于整个数组的和，如果它是个奇数，那么原序列必定不存在相应的操作使其满足题意，因为0是一个偶数，而题目所给的操作只是修改组成和的元素的正负，没法改变正负

　　当和为偶数时，那么应该是存在相应的操作（怎么划分的方法应该有很多，但是这里只介绍自己理解的一种）：因为和为偶数，那么n应该也是偶数（1+1=2，1-1=0，-1-1=-2），故仅考虑a_2i-1与a_2i的关系。

　　　　①a_2i-1=a_2i时，将(2i-1,2i)划为一组即可，这时alternating sum(2i-1,2i)=0;

　　　　②a_2i-1!=a_2i时，将(2i-1,2i-1)、(2i,2i)分别划为一组即可。因为a[i]=±1，故当a_2i-1!=a_2i时，a_2i-1+a_2i=0一定成立，此时alternating sum(2i-1,2i-1)+alternating sum(2i,2i)=0;

　　故题目就可以解了。

最终代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
const int maxm=2e5+5,inf=0x3f3f3f3f;
int n;
vector<int> a,b;

void solve(){
	cin>>n;
	a.assign(n+5,0);
	b.assign(n+5,0);
	for(int i=1;i<=n;++i){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	if(b[n]%2){
		cout<<-1<<endl;
		return ;
	}
	deque<int> ans;
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		if(a[i]==a[i+1]){
			ans.push_back(i);
			ans.push_back(i+1);
			++cnt;
		}
		else{
			ans.push_back(i);
			ans.push_back(i);
			cnt+=2;
			ans.push_back(i+1);
			ans.push_back(i+1);
		}
	}
	cout<<cnt<<endl;
	for(int i=0;i<cnt;++i){
		cout<<ans.front()<<' ';
		ans.pop_front();
		cout<<ans.front()<<endl;
		ans.pop_front();
	}
	return ;
}

signed main(){
//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}