题目链接：https://codeforces.com/contest/1367/problem/C

题意

给出一个长为 $n$ 的 $01$字符串，两个相邻 $1$ 间距应大于 $k$，初始序列合法，问最多能再使多少 $0$ 变为 $1$ 。

题解

如果当前字符为 $0$，查找 $k$ 个距离内是否有 $1$：

若有则不合法，跳至最近的 $1$
否则因为 $k$ 个距离内没有 $1$，当前字符置为 $1$，跳至第 $i + k$ 个字符

如果当前字符为 $1$，因为初始序列合法，下一个可以置为 $1$ 的 $0$ 至少在第 $i + k$ 个字符后，跳至第 $i + k$ 个字符。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, k; cin >> n >> k;

    string s; cin >> s;

    int ans = 0;

    for (int i = 0; i < s.size(); i++) {

        if (s[i] == '0') {

            int j = i + 1;

            while (j < s.size() and s[j] == '0' and j - i <= k) ++j;

            if (j - i > k or j == s.size()) {

                ans++;

                i += k;

            } else i = j - 1;

        } else i += k;

    }

    cout << ans << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

巴特西

Codeforces Round #650 (Div. 3) C. Social Distance

题意

题解

代码

最新文章

热门文章