上海计算机学会2023年12月月赛C++丙组T5特定的串

keywords: 贪心

题目链接

特定的串

题目描述

给定一个01序列，要求序列不能存在110的组合，问最少操作次数是多少

思路

看数据范围 5e5，这应该是一个贪心，否则，就搞不成了 具体怎么贪，就是一个技术活

方案1

// 这种贪心，只能30pts
#include <bits/stdc++.h>

using namespace std;

string s;
int cnt, n;

int main() {
    cin >> n;
    cin >> s;

    for (int i = n - 1; i >= 2; i--) {
        if (s[i] == '0' && s[i - 1] == '1' && s[i - 2] == '1') {
            cnt++;
            s[i - 2] = 0;
        }
    }

    cout << cnt << '\n';

    return 0;
}

方案2

// 这样贪心，可以对6个点
#include <bits/stdc++.h>

using namespace std;

string s;
int cnt, n;

int main() {
    cin >> n;
    cin >> s;

    for (int i = 2; i < n; i++) {
        if (s[i] == '0' && s[i - 1] == '1' && s[i - 2] == '1') {
            if (i == 2 || i == 3) {
                s[i - 2] = 0, cnt++;
                continue;
            }

            if (!(s[i - 3] == '1' && s[i - 4] == '1')) {
                s[i - 2] = '0';
                cnt++;
                continue;
            }

            s[i] = '1';
            cnt++;
        }       
    }

    cout << cnt << '\n';

    return 0;
}

方案3

#include <bits/stdc++.h>

using namespace std;

string s;
int ret, n, zero;
vector<int> A;

int main() {
    cin >> n;
    cin >> s;

    bool flag = false;
    for (int i = 0; i < n; i++) {
        if (!flag && s[i] == '0') continue; // 开头是0，就跳过
        flag = true;

        int j = i, t = 0;
        while (j < n && s[j] == s[i]) t++, j++;
        A.push_back(t);
        i = j - 1;
    }

    int len = A.size();
    if (len % 2) A.pop_back(); // 保证是长度是偶数，就是一段1一段0的101010交替组合

    for (int i = 1, len = A.size(); i < len; i += 2)
        zero += A[i];

    for (int i = 0, len = A.size(); i < len; i += 2){
        if (A[i] >= 2 && i + 1 < len && A[i + 1] >= 1) {
            ret += min(A[i] / 2, zero); // {把这段111111改成1010101，把后面的0全部变成1}
        }
        zero -= A[i + 1]; // 右边还剩下多少个0
    }

    cout << ret << '\n';

    return 0;
}

总结

比赛场上，想不到完整思路，就要实现部分思路。不能不写，不能放弃，不能不得分。

AC代码的思路，来源于，贾宸浩同学

@贾宸浩

，我完善了一下代码