Cf #779 (Div. 2) - A

题目连接

题目大意

给一个01串，其中每一个长度大于等于2的子区间中0的数量不大于1的数量，最少插入多少1

思路

寻找 00 和 010

00 -->0110     加2

010 -->0110   加1

代码

#include 
using namespace std;
int t;
int main()
{
    std::ios::sync_with_stdio(false);
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        if (n == 1)
        {
            cout << "0" << endl;
            continue;
        }
        int z = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '0')
                z++;
        }
        if (z == 0 || z == 1 && n >= 2)
        {
            cout << "0" << endl;
            continue;
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '0')
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (s[j] == '0')
                    {
                        if (j - i == 1)
                            ans += 2;
                        else if (j - i == 2)
                            ans += 1;
                        i = j - 1;
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

小结：

简单的字符串问题，从最小的单元为起点去思考