首页 > 试题广场 >

可匹配子段计数

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

热度指数：85 时间限制：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

输入

输出

算法知识视频讲解

赵成1212

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

int main() {
    int t;
    cin >> t;
    vector<int> res(t);

    for (int i = 0; i < t; ++i) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> a;
        vector<int> b;
        unordered_map<int , int> ma;
        unordered_map<int, int> mb;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            a.push_back(x);
        }
        for (int i = 0; i < m; ++i) {
            int x; 
            cin >> x;
            b.push_back(x);
            mb[x]++;
        }

        int cnt = 0;
        // init
        for (int i = 0; i < m; ++i) {
            ma[a[i]]++;
        }
        int match_cnt = 0;
        for (auto& [x, count] : mb) {
            if (ma.find(x) != ma.end()) {
                match_cnt += min(count, ma[x]);
            }
        }
        if (match_cnt >= k) cnt++;
        for (int i = m; i < n; ++i) {
            int left_val = a[i - m];
            if (mb.find(left_val) != mb.end() && ma[left_val] <= mb[left_val]) {
                match_cnt--;
            }
            ma[left_val]--;
            if (ma[left_val] == 0) ma.erase(left_val);
            int right_val = a[i];
            ma[right_val]++;
            if (mb.find(right_val) != mb.end() && ma[right_val] <= mb[right_val]) {
                match_cnt++;
            }
            if (match_cnt >= k) cnt++;
        }
        res[i] = cnt;
    }
    for (int i = 0; i < t; ++i) {
        cout << res[i] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2025-08-14 17:07:22 回复(0)