题解

题意简述

给定一个由 $0$ 和 $1$ 组成的字符串 $s$。每次操作可以选出一个非空子序列 $t$，要求 $t$ 中任意相邻字符不同（即 $t$ 是交替的 $0$、$1$ 序列），然后将 $t$ 中的每个字符翻转（$0$ 变 $1$，$1$ 变 $0$）。求将整个字符串变为全 $0$ 所需的最少操作次数。

解题思路

结论：最少操作次数等于字符串中 $1$ 的个数。

证明：

1. 下界：
   考虑一次操作中翻转的 $1$ 的个数为 $a$，翻转的 $0$ 的个数为 $b$。操作后，$1$ 的数量的变化量为 $b - a$（因为每个 $1$ 变成 $0$ 会减少 $1$ 个 $1$，每个 $0$ 变成 $1$ 会增加 $1$ 个 $1$），即净减少 $a - b$ 个 $1$。
   由于选出的子序列 $t$ 是交替的，若 $t$ 以 $1$ 开头，则序列模式为 $1,0,1,0,\dots$，设长度为 $k$，则 $a = \lceil k/2 \rceil$，$b = \lfloor k/2 \rfloor$，故 $a - b = 0$（$k$ 为偶数）或 $1$（$k$ 为奇数）。若 $t$ 以 $0$ 开头，则 $a = \lfloor k/2 \rfloor$，$b = \lceil k/2 \rceil$，$a - b = 0$ 或 $-1$。
   因此，一次操作最多使 $1$ 的数量减少 $1$。初始有 $\text{count}_1$ 个 $1$，最终为 $0$ 个 $1$，故至少需要 $\text{count}_1$ 次操作。

2. 上界：
   我们可以每次只选择一个单独的 $1$ 作为子序列（单个字符显然满足相邻字符不同的条件），将其翻转为 $0$。这样每次操作恰好减少一个 $1$，因此 $\text{count}_1$ 次操作即可完成。
   所以最少操作次数不会超过 $\text{count}_1$。

综上，最少操作次数就等于字符串中 $1$ 的个数。

算法实现

直接统计字符串中字符 $1$ 的个数并输出即可。时间复杂度 $O(|s|)$，空间复杂度 $O(1)$。

参考代码（标程）

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T,n,i,ans;
    for(cin>>T;T>0;T--){
        cin>>s; n=s.size();
        ans=0;
        for(i=0;i<n;i++) ans+=s[i]-'0';
        cout<<ans<<'\n';
    }
    return 0;
}