codeforce每日一题
题目链接
题目分数:1900
题目描述
输入 $n,k(1≤k≤n≤4e5)$ 和长为 $n$ 的数组 $a(1≤a[i]≤1e9)$。
统计有多少个连续子数组 $b$,满足 $b$ 中有至少 $k$ 个相同的数。
样例
输入样例1
4 2
1 2 1 2
输出样例1
3
输入样例2
5 3
1 2 1 1 3
输出样例2
2
输入样例3
3 1
1 1 1
输出样例3
6
算法
(双指针) $O(n)$
这道题我们可以用双指针来做。用双指针,就要证明两个指针具有单调性,我们可以假设$i,j (j < i)$ 是两个指针,表示的是在这个区间内恰好只有一个数字并且刚好满足出现次数等于$k$次,当$i$变成$i+1$时,$j$到$i+1$这个区间满足至少有一个数字满足上述性质,此时$j$需要向右移动,直到$j$到$i+1$内只有一个数字满足出现次数等于$k$。以上证明了可以使用双指针。
C++ 代码
// codeforce每日一题 https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>m;
vector<int> w(n + 1);
map<int,int> g;
rep(i, 1, n) cin>>w[i];
LL res = 0, cnt = 0;
for(int i=1,j=0;i<=n;i++){
g[w[i]] ++;
if(g[w[i]]==m) cnt++;
while(j<i){
g[w[j + 1]] --;
if(g[w[j + 1]]==m-1) cnt--;
if(cnt==0){
g[w[j + 1]]++;
if(g[w[j + 1]] == m) cnt++;
break;
}
else j++;
}
// cout<<cnt<<" "<<j<<endl;
if(cnt) res += j + 1;
}
cout<<res<<endl;
return 0;
}
Java 代码
// https://www.acwing.com/blog/content/34755/
import java.util.*;
public class Main{
public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] w = new int[n + 1];
for(int i=1;i<=n;i++) w[i] = sc.nextInt();
Map<Integer, Integer> g = new HashMap<Integer, Integer>();
long res = 0, cnt = 0;
int tmp;
for(int i=1,j=0;i<=n;i++){
if(g.containsKey(w[i])){
tmp = g.get(w[i]);
g.remove(w[i]);
g.put(w[i], tmp + 1);
}else g.put(w[i], 1);
if(g.get(w[i])==m) cnt++;
while(j<i){
tmp = g.get(w[j + 1]);
g.remove(w[j + 1]);
g.put(w[j + 1], tmp - 1);
if(g.containsKey(w[j + 1]) && g.get(w[j + 1])==m-1) cnt--;
if(cnt==0){
if(g.containsKey(w[j + 1])){
tmp = g.get(w[j + 1]);
g.remove(w[j + 1]);
g.put(w[j + 1], tmp + 1);
}else g.put(w[j + 1], 1);
if(g.get(w[j + 1]) == m) cnt++;
break;
}
else j++;
}
// cout<<cnt<<" "<<j<<endl;
if(cnt > 0) res += j + 1;
}
System.out.println(res);
}
public static void main(String args[])
{
solve();
}
}
Python 代码
# https://www.acwing.com/blog/content/34755/
def solve():
n, m = map(int, input().split())
w = [int(i) for i in input().split()]
w.insert(0, 0)
g = {}
res, cnt = 0, 0
j = 0
for i in range(1, n + 1):
g[w[i]] = g.get(w[i], 0) + 1
if g[w[i]] == m: cnt += 1
while j < i:
g[w[j + 1]] = g[w[j + 1]] - 1
if g[w[j + 1]] == m - 1: cnt -= 1
if cnt == 0:
if g[w[j + 1]] == m - 1: cnt += 1
g[w[j + 1]] = g[w[j + 1]] + 1
break
else: j += 1
if cnt > 0: res += j + 1
print(res)
def main():
solve()
if __name__ == '__main__':
main()