题目大意
给你一个数组 \([a_1,a_2,...a_n]\) ,其中每一项 \(a_i\) 都为 \(1\) 或 \(-1\) ,你需要构造一个划分 \([l_1,r_1],[l_2,r_2],[l_3,r_3],...[l_k,r_k]\) 使得:
-
将每一个区间内的数按照以下方法计算出\(s_i=a_{l_i}-a_{l_i+1}+a_{l_i+2}-a_{l_i+3}+...\pm a_{r_i}\)
-
对于一个合法的划分,所有的 \(s_i\) 之和为 \(0\)
如果存在这样的划分,输出任何一个,否则输出 -1
,代表无解。
称一组区间 \([l_1,r_1],[l_2,r_2],[l_3,r_3],...[l_k,r_k]\) 为数组 \([a_1,a_2,...a_n]\) 的划分当且仅当 \(1=l_1\leq r_1,l_2\leq r_2,l_3\leq r_3,...,l_k\leq r_k = n\) 且对于 \(1\leq i \leq k-1\) ,均有 \(r_i+1=l_{i+1}\)
注意在本题中,你不需要最小化 \(k\)。
思路
这题很容易想复杂(比如我,看了眼题解才醒悟)
既然题目没要求最小化\(k\),那不妨找找通解
可以发现,如果相邻两个数符号相同,那么他们分成一段的话,他们的和就恰好为\(0\)了
而如果相邻两数符号不同,分成两段即可,这样他们的和就能够相互抵消了
而如果\(n\)是奇数,那么就永远构造不出来整个数组和为\(0\)的情况了,也就是无解
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int a[Maxn];
int n;
int run()
{
vector<pair<int,int> >ans;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n%2==1)
{
cout<<-1<<endl;
return 0;
}
for(int i=1;i<n;i+=2)
{
if(a[i]==a[i+1]) ans.push_back(make_pair(i,i+1));
else ans.push_back(make_pair(i,i)),ans.push_back(make_pair(i+1,i+1));
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl;
return 0;
}
int main()
{
int t;
cin>>t;
while(t--) run();
return 0;
}