Skip to content

Problem I: 走开，别做我

📝 题目描述

🔑 算法模块

💡 思路分析

可以看出，最后变化成的字符串只有两种，要么 \(0\) 开头，要么 \(1\) 开头。那可以直接枚举出这两个字符串，然后依次遍历出结果，两种情况取最小值即可。如果两种情况都无法得到答案，输出 \(-1\)。

🖥️ 代码实现

 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
#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, ans1 = 0, ans2 = 0;
    std::cin >> n;
    std::string s, a, b;
    std::cin >> s;
    for (int i = 0; i < n; i++) {
        a += '0' + (i & 1);
        b += '0' + 1 - (i & 1);
    }
    for (int i = 0; i <= n - 1 - i; i++) {
        int j = n - 1 - i;
        if (s[i] != a[i] && s[j] != a[j]) {
            ans1++;
        } else if (!(s[i] == a[i] && s[j] == a[j])) {
            ans1 = 1e9;
        }
        if (s[i] != b[i] && s[j] != b[j]) {
            ans2++;
        } else if (!(s[i] == b[i] && s[j] == b[j])) {
            ans2 = 1e9;
        }
    }
    int ans = std::min(ans1, ans2);
    if (ans >= 1e9) {
        ans = -1;
    }
    std::cout << ans << "\n";
    return 0;
}

⏱️ 复杂度分析

📚 拓展