题解

题面描述

给定一个长度为 $n$ 的二进制字符串 $s$（仅包含字符 '0' 和 '1'），我们可以对任意子串执行以下操作：每次添加或删除一个字符 '0' 或者字符 '1'。现在要求我们求出所有非空子串的"权值"之和。

一个子串 $t$ 的权值定义为：通过任意次数交换相邻字符的前提下，确保任意相邻的字符都不相等的最少操作次数。换句话说，最小的操作次数就是将该子串变为一个 "交替字符串"（例如 '010101' 或 '101010'）所需的操作。

思路

我们通过前缀和的概念来优化计算过程，将字符串中的字符差异（'1'与'0'的数量差）转换为前缀和数组。每次更新前缀和，并统计前缀和的频次，利用哈希表在常数时间内更新频次，从而快速计算每个位置的操作代价。最终通过对前缀和数组排序并计算每个子串的代价，得到所有非空子串的权值之和。

1. 定义权值： 先考虑一个子串 $t$，它可能包含多次相同的相邻字符。例如，子串 "111" 需要通过删除或添加字符才能变成 "101" 或 "010" 的交替形式。在这个问题中，我们的目标是计算所有非空子串的权值之和。

2. 观察： 我们可以通过观察子串的前缀和来优化计算。具体来说，可以通过维护一个前缀和数组来跟踪字符串中 '1' 的数量与 '0' 的数量的差值，这将帮助我们更高效地计算子串的权值。

3. 优化方法：

   • 通过前缀和来统计每个位置的差值。对于每个前缀和，如果出现次数较多的前缀和，则该部分会需要较多的操作来确保相邻字符不相同。
   • 使用哈希表来统计前缀和出现的频次，从而计算出所有子串的最小操作次数。

4. 具体操作： 通过一次遍历，计算每个位置的前缀和并更新权值累加值。为避免重复计算，使用哈希表（或频次数组）来记录每个前缀和的频次。

代码实现

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int test_cases;
    cin >> test_cases;  // 输入测试用例的数量
    
    while (test_cases--) {
        int length;
        cin >> length;  // 输入字符串的长度
        string str;
        cin >> str;  // 输入字符串
        
        // 初始化前缀和数组
        vector<int> prefix_sum(length + 1, 0);
        unordered_map<int, int> freq_map;  // 用哈希表代替Counter
        long long total_cost = 0;

        for (int i = 1; i <= length; i++) {
            // 更新哈希表
            freq_map[prefix_sum[i - 1]]++;

            // 更新前缀和
            prefix_sum[i] = prefix_sum[i - 1] + (str[i - 1] == '1' ? 1 : -1);
            
            // 更新总成本
            total_cost -= i;
            total_cost += freq_map[prefix_sum[i]];
        }

        // 直接在main函数内实现计算代价的功能
        sort(prefix_sum.begin(), prefix_sum.end());
        long long count = 0;
        long long prev_sum = 0;
        for (int i = 0; i < prefix_sum.size(); i++) {
            prev_sum += prefix_sum[i];
            count += 1;
            total_cost += prefix_sum[i] * count - prev_sum;
        }

        // 输出结果
        cout << total_cost << endl;
    }

    return 0;
}

Python

from collections import defaultdict

# 输入测试用例数量
t = int(input())

for _ in range(t):
    n = int(input())  # 输入字符串长度
    s = input().strip()  # 输入字符串

    # 初始化前缀和数组
    prefix_sum = [0] * (n + 1)
    freq_map = defaultdict(int)  # 使用默认字典来存储频次
    total_cost = 0

    for i in range(1, n + 1):
        # 更新哈希表
        freq_map[prefix_sum[i - 1]] += 1

        # 更新前缀和
        prefix_sum[i] = prefix_sum[i - 1] + (1 if s[i - 1] == '1' else -1)

        # 更新总成本
        total_cost -= i
        total_cost += freq_map[prefix_sum[i]]

    # 排序前缀和数组
    prefix_sum.sort()
    count = 0
    prev_sum = 0
    for ps in prefix_sum:
        prev_sum += ps
        count += 1
        total_cost += ps * count - prev_sum

    # 输出结果
    print(total_cost)

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 输入测试用例数量

        while (t-- > 0) {
            int n = sc.nextInt(); // 输入字符串长度
            String s = sc.next(); // 输入字符串

            // 初始化前缀和数组
            int[] prefixSum = new int[n + 1];
            Map<Integer, Integer> freqMap = new HashMap<>();
            long totalCost = 0;

            for (int i = 1; i <= n; i++) {
                // 更新哈希表
                freqMap.put(prefixSum[i - 1], freqMap.getOrDefault(prefixSum[i - 1], 0) + 1);

                // 更新前缀和
                prefixSum[i] = prefixSum[i - 1] + (s.charAt(i - 1) == '1' ? 1 : -1);

                // 更新总成本
                totalCost -= i;
                totalCost += freqMap.getOrDefault(prefixSum[i], 0);
            }

            // 排序前缀和数组
            Arrays.sort(prefixSum);
            long count = 0;
            long prevSum = 0;
            for (int ps : prefixSum) {
                prevSum += ps;
                count++;
                totalCost += ps * count - prevSum;
            }

            // 输出结果
            System.out.println(totalCost);
        }

        sc.close();
    }
}

题目内容

对于一个字符串，小美每次操作可以:添加或者删除一个$0$字符或者$1$。

她定义一个字符串$t$的权值为:

满足任意次交换两个相邻字符的前提下使得任意相邻的两个字符都不相等的最少操作次数。

例如:对于$t=011$,其权值为$1$。

可以选择在$11$之间添加$0$变成$0101$。

也可以选择删除$1$变成$01$。

给你一个长度为$n$的字符串$s$，仅包含"$0、1$"，请你帮助小美求出非空子串的权值之和。

子串:是指一个字符串中的连续部分。

输入描述

第一行一个整数$t(1≤1≤10)$,表示数据组数。

对于每一组数据格式为:

第一行一个整数$n(1≤n≤2×10^5)$,表示字符串长度。

第二行第一个长度为n的字符串$s$，输入保证仅含"$0、1$".

单个测试文件数据保证$\sum n ≤2×10^5$。

输出描述

对于每一组数据：

每行输出一个整数，表示给定字符串的所有非空子串的权值之和。

样例1

输入

2
3
011
4
1111

输出

1
10

说明

对于第二个样例$s$="$1111$": 长度为$1$的子串$[1,1,1,1]$均不需要操作。 长度为$2$的子串$[11,11,11]$均需要操作一次，使得 $11→101$。 长度为$3$的子串$[111,111]$均需要操作两次，使得 $111→10101$。 长度为4的子串$[1111]$需要操作三次，使得 $1111→1010101$。

共累计$3×1+2×2+1×3=10$。