CF1754C2 题解

· · 题解

简单版

在赛时写这题的我,想说: 这就是一个诈骗题!!!!

这题相对于简单版 最大的难点就是在处理0上，但两者实际的处理方法是一样的，所以我们先讲简单版。

简单版题目大意:

给出了一个只有 1 和 -1 的序列，要求我们划分出若干个区间，每个区间内的元素按照在这段区间里的下标,奇不变偶变的方式求出和,求所有区间的和是否能为 0 ，如果无解输出 -1，否则输出所有区间的左,右端点。

首先可以知道，在区间长度为奇数时，无解。 因为在这种情况下,无论如何构造，一定会多出来一个数，所以无解。

由于这题没有对答案有限制，只要符合要求就行，所以我们将区间长度往小了想,只对每两个数进行讨论。于是有两种情况:

至此,简单版就讲完了。

那这题对于简单版难在哪呢?序列里不只有 1 , -1 了，还有 0 。 这导致这题码量相对于简单版大大增加,但思想仍然是一样的,但在处理时要特别注意中间的 0 导致的数所在区间的下标奇偶性的变化。

详情见代码吧:

#include <bits/stdc++.h>
using namespace std;
int wz[200005],n,a[200005],b[200005],x[200005],L[200005],R[200005];
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int cnt=0,ok=0,len=0;
        for (register int i=1;i<=n;i++){
            cin >> a[i];
            if (a[i]!=0) b[++cnt]=a[i],wz[cnt]=i;//记录每个非0位置的信息
        }
        if (cnt%2==1){
            cout << -1 << endl;//无解
            continue ;
        }
        for (register int i=1;i<=cnt;i+=2){
            if (b[i]!=b[i+1]){//第二种情况
                for (register int j=wz[i-1]+1;j<=wz[i+1];j++){
                    L[++len]=R[len]=j;//每段单独分
                }
            }
            else {
                if (wz[i]+1==wz[i+1]) L[++len]=wz[i-1]+1,R[len]=wz[i+1];//相邻就直接分,注意要从上个非0位置+1开始
                else {
                    for (register int j=wz[i-1]+1;j<=wz[i];j++) L[++len]=R[len]=j;//i之前全部单独分
                    for (register int j=wz[i]+1;j<=wz[i+1]-2;j++) L[++len]=R[len]=j;
                    L[++len]=wz[i+1]-1,R[len]=wz[i+1];//给第i+1个非零位置前留下一个0使它在区间里的长度变为偶数
                }
            }
        }
        if (R[len]<n){
            L[len+1]=R[len]+1,R[len+1]=n;
            len++;//可能最后一个非零数后面还有,单独再开一段
        }
        cout << len << '\n';
        for (register int i=1;i<=len;i++) cout << L[i] << ' ' << R[i] << endl;
    }
}