11294808 小苯的好区间

题目链接

https://www.nowcoder.com/practice/d47bbdc50a3941fc97e37f6d4217c535

题意

给两个长度为 n 的 01 字符串 s 和 t，求有多少区间 [l, r] 使得 s 和 t 在该区间按位或（OR）后得到一个"好串"（全为 0 或全为 1）。

思路分析

关键观察：先对每个位置 i 预处理 c[i] = s[i] OR t[i]，得到一个新的 01 串 c。

• OR 结果全为 0：要求 s[i] = t[i] = '0'，即 c[i] = '0'
• OR 结果全为 1：要求每个位置至少有一个 '1'，即 c[i] = '1'

因此，问题转化为：在字符串 c 中，找有多少区间 [l, r] 使得 c 在该区间全为 '0' 或全为 '1'，即找有多少区间内 c 的字符全部相同。

做法：将 c 按连续相同字符分段，设每段长度为 len，则该段内的合法区间数为 len * (len + 1) / 2（等差数列求和）。累加所有段的贡献即为答案。

时间复杂度：O(n)

验证示例

示例 1：n=4, s="1010", t="0011"

• c[0] = 1|0 = 1
• c[1] = 0|0 = 0
• c[2] = 1|1 = 1
• c[3] = 0|1 = 1

c = "1011"，分段：[1]长度1, [0]长度1, [11]长度2

答案 = 1 + 1 + 3 = 5 ✓

代码实现

C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;

    string c(n, '0');
    for (int i = 0; i < n; i++) {
        c[i] = ((s[i]-'0') | (t[i]-'0')) ? '1' : '0';
    }

    long long ans = 0;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && c[j] == c[i]) j++;
        long long len = j - i;
        ans += len * (len + 1) / 2;
        i = j;
    }

    cout << ans << endl;

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();
        String t = br.readLine().trim();

        long ans = 0;
        int i = 0;
        while (i < n) {
            char ci = (char)(((s.charAt(i) - '0') | (t.charAt(i) - '0')) + '0');
            int j = i;
            while (j < n) {
                char cj = (char)(((s.charAt(j) - '0') | (t.charAt(j) - '0')) + '0');
                if (cj != ci) break;
                j++;
            }
            long len = j - i;
            ans += len * (len + 1) / 2;
            i = j;
        }

        System.out.println(ans);
    }
}