题解

简述题意：给定两个数组 $a$ , $b$ ，要从 $a, b$ 中各选一个连续的子数组，满足其对应位置的值都不相同，其中两个子数组的下标要一样，问能选多少个。

做法：从左往右枚举，维护一个计数器 $cnt$, 表示当前连续的 $a[i] != b[i]$ 的数组长度，记 $res$ 为最终答案

假设当前有 $len$ 长度的连续子数组满足条件，那么对答案的贡献为 $\frac{(1 + len) \times len}{2}$

所有满足条件连续子数组的贡献相加即可

时间复杂度 $O(n)$

AC代码

• Cpp

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    vector<int> a(n), b(n);
    for(int& i : a) cin >> i;
    for(int& i : b) cin >> i;
    LL res = 0;
    int c = 0;
    for(int i = 0; i < n; i ++)
    {
        if(a[i] != b[i])
        {
            c ++ ;
            res += c;
        }
        else{
            c = 0;
        } 
    }
    cout << res << "\n";
    return 0;
}

• Java

import java.util.Scanner;
​
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }
        long res = 0;
        int c = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) {
                c++;
                res += c;
            } else {
                c = 0;
            }
        }
        System.out.println(res);
    }
}
​

• Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
c = 0
for i in range(n):
    if a[i] != b[i]:
        c += 1
        res += c
    else:
        c = 0
print(res)

问题描述

小红的村庄将要举办一年一度的搭配大赛。在这项赛事中，参赛者需要从两个长度相等的数组中，分别挑选出相同长度的子数组进行搭配。如果两个子数组在相同位置上的元素完全不同，则认为这是一次成功的搭配。小红作为赛事的主办方，需要计算出所有可能的成功搭配的数量。

输入格式

第一行包含一个正整数 $n$，表示数组的长度。

第二行包含 $n$ 个由空格分开的整数 $a_1, a_2, ..., a_n$，代表第一个数组。

第三行包含 $n$ 个由空格分开的整数 $b_1, b_2, ..., b_n$，代表第二个数组。

输出格式

输出一个整数，代表所有可能的成功搭配的数量。

样例输入

3
1 2 3
3 2 1

样例输出

2

样例说明

在这个例子中，数组 1 2 3 和 3 2 1 可以形成两个成功的搭配：

• 第一个成功的搭配是第一个数组的第一个元素 1 与第二个数组的第一个元素 3 组成的子数组对。
• 第二个成功的搭配是第一个数组的第三个元素 3 与第二个数组的第三个元素 1 组成的子数组对。

其他子数组对至少在一个位置上有相同的元素，因此不构成成功的搭配。

评测数据与规模

对于 $100\%$ 的评测数据，$1 \leq n \leq 10^5$，$0 \leq a_i, b_i \leq 10^9$。