HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

蓝桥杯2018年第九届真题-日志统计-题解（C++代码）

　　作者: HzuQZH　　　　发表时间：2020-10-13 17:17:02 浏览：362　|　评论：1　

原题链接：蓝桥杯2018年第九届真题-日志统计

### 解题思路：双指针i表示右端点，j表示左端点，如果i~j区间<k那么每次都把i扩展的点的权值加进来，当i-j的距离大于等于k时，那么左端点往右挪，并删除点原先端点的贡献，然后判断当前扩展的点的热度是否符合要求，符合就打标记，最后遍历所有可能是帖子id，有标记的就是答案

```cpp
#include<bits/stdc++.h>
#define x first
#define y second
#define mem1(h) memset(h,-1,sizeof h)
#define mem0(h) memset(h,0,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
	inline LL read(){
		LL o=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
		while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
		return o*f;
	}
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
int n,d,k;
PII a[N];
int cnt[N];
bool st[N];
int main(){
    n=read(),d=read(),k=read();
    for(int i=0;i<n;i++){
    	a[i].x=read(),a[i].y=read();
	}
	sort(a,a+n);
	for(int i=0,j=0;i<n;i++){//i表示右端点，j表示左端点
		cnt[a[i].y]++;//加上当前i扩展的点的热度
		while(a[i].x-a[j].x>=d){//如果右端点的距离与左端点的距离大于等于k就把左端点右移
			cnt[a[j].y]--;//把删除左端点的贡献
			j++;
		}
		if(cnt[a[i].y]>=k)st[a[i].y]=true;//当前扩展点的id的热度符合要求就标记
	}
	for(int i=0;i<N;i++){
		if(st[i])printf("%d\n", i);
	}
    return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

为什么要把左端点的贡献--

2023-03-08 20:34:58

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

C二级辅导-等差数列（C++代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

蓝桥杯2018年第九届真题-日志统计-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

文科生的悲哀（C语言代码）

矩形面积交（C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-求偶数和（C语言代码）

IP判断（C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

C二级辅导-等差数列 （C++代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

蓝桥杯2018年第九届真题-日志统计-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

文科生的悲哀 （C语言代码）

矩形面积交 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

IP判断 （C语言代码）

C二级辅导-等差数列（C++代码）

母牛的故事（C语言代码）

　　评论区

上车人数（C语言代码）

文科生的悲哀（C语言代码）

矩形面积交（C++代码）

C二级辅导-求偶数和（C语言代码）

IP判断（C语言代码）