AT_arc156_a 题解

· · 题解

AT_arc156_a 题解

有一点点难度

正文开始

首先，显而易见，当 1 的个数为奇数时，这种情况不存在，输出 -1。

那么 1 的个数为偶数呢？

我们可以用一个数组 a 存储 1 出现的位置，对于像我一样的蒟蒻来说，可以分为两种情况：

  1. 特判。当只有两个 1 时，要判断这两个 1 下标的距离是否大于等于 2。如果是，输出 1，否则过程不能实现，输出 -1。

  2. 其余情况。设有 tp 个 1，因为 tp \ge 2 且 tp 为偶数，所以在 a 数组中，下标 1 对应下标 3，下标 2 对应下标 4，以此类推，都可以被消去。这怎么证明呢？假设这种情况极其不利，上来就是三个 1，假设 a 数组中 a_1 = 1 且 a_2 = 2 且 a_3 = 3，即使 a_1 和 a_2 之间只差了 1，而 a_1 和 a_3 在最坏的情况下也相差 2，其余情况同理。所以，这种情况存在，输出 \displaystyle \frac{tp}{2}。

上代码：

#include<iostream>
#include<string>
using namespace std;
int a[200005];//存储下标
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,tp=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            char c;
            cin>>c;
            if(c=='1') a[++tp]=i;
        }//输入并且存储1的下标
        if(tp&1){
            cout<<"-1\n";
            continue;
        }//tp为奇数
        if(tp==2&&a[2]-a[1]<2){
            cout<<"-1\n";
            continue;
        }//情况1
        printf("%d\n",tp>>1);//情况2
    }
    return 0;
}

注：请勿抄袭！