首页 > 试题广场 >

可匹配子段计数

[编程题]可匹配子段计数

热度指数：1554 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定整数数组 $a$ （长度 $n$ ）与数组 $b$ （长度 $m$ ， $m\leqq n$ ）。设一个长度为 $m$ 的数组 $c$ 被称为 可匹配的，当且仅当将 $c$ 的元素重新排列后，与数组 $b$ 在对应位置上至少有 $k$ 个元素相等。
$\hspace{15pt}$ 对于 $a$ 中的每一个长度恰为 $m$ 的连续子段，都可视为一个候选数组 $c$ 。求满足条件的子段数量。

【形式化解释】
$\hspace{15pt}$ 若子段 $a_{l..l+m-1}$ 经重排可与 $b$ 至少 $k$ 个位置相等，则称该子段为"可匹配的"。等价地，设 $cnt_x(S)$ 为元素 $x$ 在序列 $S$ 中出现次数，则子段 $c$ 的"匹配度"为 $\operatorname{match}(c)=\sum_{x} \min\bigl(cnt_x(c),\ cnt_x(b)\bigr)$ ，若 $\operatorname{match}(c)\geqq k$ 则符合要求。

输入描述:

第一行输入整数 ——测试用例组数。 
每个测试用例： 
一行三个整数 ； 
一行  个整数 ； 
一行  个整数 。 
输入保证所有测试用例的  之和、 之和均不超过 。

输出描述:

对每个测试用例输出一行整数，表示满足条件的子段数量。

示例1

输入

输出

算法知识视频讲解

Python3

HIKong

import sys
from collections import Counter

# 在 a 里滑动一个长度为 m 的窗口，
# 每次问：这个窗口里的数字，
# 和 b 最多能对上几个？
# 如果 ≥ k，就算一个好窗口。最终输出好窗口的数量。天天把题目写那么绕干蛤啊，嗯→膜⬆！
# 滑动窗口可以简单的理解成，右边进来一个数，然后左边出去一个
t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    need = Counter(b)
    window = Counter()
    match = 0 # 连续字段中数字匹配的次数
    ans = 0

    # 双指针
    left = 0
    for right in range(n):
        x = a[right]
        window[x] += 1
        if window[x] <= need[x]:
            match += 1

        # 保持窗口长度为 m。出去一个，自然匹配次数要-1
        if right - left + 1 > m:
            y = a[left]
            if window[y] <= need[y]:
                match -= 1
            window[y] -= 1
            left += 1

        if right - left + 1 == m and match >= k:
            ans += 1
    print(ans)

发表于 2025-12-20 20:25:44 回复(0)

Python3