C - Coloring Colorfully

乍看很難，但是逆著思考，結果是不是只有兩種呢？$010101…$ 跟 $1010101…$ 對吧？

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    char inp[100010];
    scanf("%s", inp);
    int ans = INT_MAX, n = strlen(inp);
    int cnt = 0, cnt2 = 0;
    for (int i = 0; i < n; i++) {
        if (inp[i] == '0' && i % 2 == 1)
            cnt++;
        else if (inp[i] == '1' && i % 2 == 0)
            cnt++;

        if (inp[i] == '0' && i % 2 == 0)
            cnt2++;
        else if (inp[i] == '1' && i % 2 == 1)
            cnt2++;
    }

    ans = min(cnt, cnt2);

    printf("%d\n", ans);

    return 0;
}

D - Handstand

我們可以發現，我們選的區間不能同時有 1 和 0，因為 1 反轉後是 0，會破壞了連續區間這個需求！

所以，我們用爬行法就可以解決問題囉！

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    char inp[n + 3];
    scanf("%s", inp);
    int num[n];
    for (int i = 0; i < n; i++) {
        num[i] = inp[i] == '0' ? 0 : 1;
    }

    int l = 0;
    int ans = 0;
    int i = 0;
    // 111000111
    // 000111000
    // 000111
    // 111000
    while (i < n) {
        while (i < n && num[i] == 1)
            i++;
        ans = max(ans, i - l);
        while (i < n && num[i] == 0)
            i++;
        k--;
        if (k < 0) {
            while (l < n && num[l] == 1)
                l++;
            while (l < n && num[l] == 0)
                l++;
        }

        ans = max(ans, i - l);
    }

    printf("%d\n", ans);

    return 0;
}