HJ177 可匹配子段计数

知识点双指针校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定整数数组 aa长度 nn与数组 bb长度 mmm≦nm≦n。设一个长度为 mm 的数组 cc 被称为可匹配的当且仅当将 cc 的元素重新排列后与数组 bb 在对应位置上至少有 kk 个元素相等。对于 aa 中的每一个长度恰为 mm 的连续子段都可视为一个候选数组 cc。求满足条件的子段数量。【形式化解释】若子段 al..lm−1al..lm−1​ 经重排可与 bb 至少 kk 个位置相等则称该子段为可匹配的。等价地设 cntx(S)cntx​(S) 为元素 xx 在序列 SS 中出现次数则子段 cc 的匹配度为 match⁡(c)∑xmin⁡(cntx(c), cntx(b))match(c)∑x​min(cntx​(c), cntx​(b))若 match⁡(c)≧kmatch(c)≧k 则符合要求。输入描述第一行输入整数 t(1≦t≦104)t(1≦t≦104)——测试用例组数。每个测试用例• •​一行三个整数 n,m,k(1≦k≦m≦n≦2×105)n,m,k(1≦k≦m≦n≦2×105)• •​一行 nn 个整数 a1…an (1≦ai≦106)a1​…an​ (1≦ai​≦106)• •​一行 mm 个整数 b1…bm (1≦bi≦106)b1​…bm​ (1≦bi​≦106)。输入保证所有测试用例的 nn 之和、mm 之和均不超过 2×1052×105。输出描述对每个测试用例输出一行整数表示满足条件的子段数量。示例1输入1 4 1 1 4 1 5 6 6复制输出1#include iostream #include vector #include map using namespace std; void solve() { int n, m, k; cin n m k; vectorint a(n); mapint, int mapB; for (int i 0; i n; i) { cin a[i]; } for (int i 0; i m; i) { int val; cin val; mapB[val]; } mapint, int mapA; int current_match 0; int ans 0; // 初始化第一个窗口 for (int i 0; i m; i) { mapA[a[i]]; } for (auto const [val, countB] : mapB) { if (mapA.count(val)) { current_match min(mapA[val], countB); } } if (current_match k) { ans; } // 滑动窗口 for (int i m; i n; i) { int remove_val a[i - m]; int add_val a[i]; // 处理移出窗口的元素 if (mapB.count(remove_val)) { if (mapA[remove_val] mapB[remove_val]) { current_match--; } } mapA[remove_val]--; if (mapA[remove_val] 0) { mapA.erase(remove_val); } // 处理加入窗口的元素 if (mapB.count(add_val)) { if (mapA.count(add_val) 1 || mapA[add_val] mapB[add_val]) { current_match; } } mapA[add_val]; if (current_match k) { ans; } } cout ans endl; } int main() { int t; cin t; while (t--) { solve(); } return 0; }