题解 | #小美的01串翻转#

问题分析

该问题的核心在于计算所有子串的“权值”之和。给定一个 串，权值的定义是将其转换为“相邻字符均不相等”的字符串所需的最小翻转次数。

1. 目标状态分析 对于任意长度为 的字符串，满足“相邻字符都不相等”的目标状态仅有两种：

• 模式 A：010101...（以 '0' 开头）
• 模式 B：101010...（以 '1' 开头）

模式 A 与 模式 B 是完全互补的。这意味着，如果一个子串转化为模式 A 需要 次翻转，那么转化为模式 B 就需要 次翻转。

2. 权值定义推导 对于一个给定的子串 ，其长度 。 设将其变为模式 A 所需翻转次数为 ，则其权值 为：

增量扫描与对比预计算

为了实现 ，我们固定子串的起点 ，并让终点 向后移动。当终点从 移动到 时，子串的长度和对应的翻转计数可以通过增量更新得到。

1. 差异化序列构建

我们可以构建一个全局的“差异数组”或“指示序列”。 定义一个全局参考模式 （例如 ）。 对于原字符串 中的每一个位置 ，记录 ：

• 如果 ，则
• 如果 ，则

2. 子串翻转数计算

对于子串 ，它与参考模式 在对应区间内的差异总数即为： 由于参考模式 在子串区间的起始字符可能与子串期望的目标模式 A 相同或相反，但这并不影响结果。根据之前的推导，该子串转化为某种交替模式的代价是 ，转化为另一种则是 。

最终权值公式：

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.length();

    vector<int> P0(n + 1, 0);
    vector<int> P1(n + 1, 0);

    for (int i = 0; i < n; i++) {
        P0[i + 1] = P0[i] + ((i % 2 == 0 && s[i] != '0') || (i % 2 == 1 &&
                             s[i] != '1'));
        P1[i + 1] = P1[i] + ((i % 2 == 0 && s[i] != '1') || (i % 2 == 1 &&
                             s[i] != '0'));
    }

    ll ans = 0;
    int cost0, cost1;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (i % 2 == 0) {
                cost0 = P0[j + 1] - P0[i];
                cost1 = P1[j + 1] - P1[i];
            } else {
                cost0 = P1[j + 1] - P1[i];
                cost1 = P0[j + 1] - P0[i];
            }
            ans += min(cost0, cost1);
        }
    }

    cout << ans << endl;
}

复杂度分析

时间复杂度：

空间复杂度：