今日学习记录
1. Problem-2149E-cf
关键词：滑动窗口
问题分析：
就是找到数组中的一个连续子数组,该数组满足(l<len<r),恰好有 k 个不同的元素
找到满足条件的数组数
核心思路:
恰好型滑窗
首先看到连续子数组反应滑窗,包含 k 个不同的数字,就是恰好型滑窗,对于这类问题可以分解为两个小问题,就是求至多为 k 的数组数,和至多为 k-1 的数组数,相差就为答案 题目还有个别的就是对长度的限制,这个好判断,就是最小为多少,最大又为多少 对于 k 个不同的数字,直接记录到 map 中(因为还要看数量) 注意
0 的时候要从 map 中删除,因为不同看的是 map 的 size,数量为 0 但是键还在 map 中 但是这是 cf,还没完,使用常规的 map 会超时,我们要自定义哈希函数进行优化才能过**最终代码：
/*
恰好型滑窗
*/
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
const int N = 2e5+5;
int T;
int n,k,l,r;
ve<int> arr(N);
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
ll f(int m){
ll ans = 0;
unordered_map<int,int> mp;
for(int i = 0,j = 0;i<n;i++){
mp[arr[i]]++;
while(j<=i&&mp.size()>m){
mp[arr[j]]--;
if(mp[arr[j]]==0) mp.erase(arr[j]);
j++;
}
ans += max(min(i-j+1,r)-l+1,0);
}
return ans;
}
void solve(){
cin>>n>>k>>l>>r;
for(int i = 0;i<n;i++) cin>>arr[i];
cout<<f(k) - f(k-1)<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
while(T--) solve();
}学到的点：
- 恰好型滑窗