蓝桥杯备赛 Day7 双指针

双指针

1.要点

(1)常用于数组或字符串,用两个变量来表示下标实现
(2)对撞指针:
left=1,right=n反向,直到left>right
查询有序数组中满足约束条件的一组元素问题，如二分查找、数字之和等
字符串反转问题：反转字符串、回文数、颠倒二进制等
(3)快慢指针(区间问题):
left=1,right=0,初始区间[l,0]为非法区间.两个指针从同侧开始,以不同策略、不同速度移动，形成[l,r]合法区间,直到right>n或者left>right

for(int l=0,r=0;r<n;r++){
	while(){//区间太大了,缩小左边界
		l++;
		//l改变产生什么影响
	}
	if(l<=r){
		//r改变产生什么影响
	}
}

2.例题

2018日志统计

学习:
(1)学会用pair<int,int>,不要老想着用map<int,int>，map的键是唯一的
(2)想明白开几个数组，每个数组什么含义
代码:

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
const int N=1e5+10;
PII logs[N];//日志编号，时刻-id
bool res[N];//id是否是热帖
int cnt[N];//id获赞次数 

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,D,K;
	cin>>n>>D>>K;
	for(int i=0;i<n;i++){
		cin>>logs[i].first>>logs[i].second;
	}
	sort(logs,logs+n);//按日志的时刻排序
	for(int l=0,r=0;r<n;r++){ //快慢指针 
		int id=logs[r].second; //新日志的id 
		cnt[id]++;
		while(logs[r].first-logs[l].first+1>D){//区间长度大于D，左指针向右移动，对应的id点赞次数减一 
			cnt[logs[l].second]--;
			l++; 
		}
		if(cnt[id]>=K)	res[id]=true;
	} 
	for(int i=0;i<N;i++){
		if(res[i]){
			cout<<i<<"\n";
		}
	}
	return 0;
}

2022统计子矩阵

学习:
(1)二维前缀和√
(2)遍历二维矩阵时注意x2,y2从x1,y1开始，不重复
(3)双指针一般只考虑一维，所以遍历行，列为快慢指针，然后for中r++,而for里面条件判断l++,再看快慢指针动完后所求数变了多少

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=510;
int a[N][N],prefix[N][N];

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,m;
	ll k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			prefix[i][j]=a[i][j]+prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];
		}
	}
	ll res=0;
	//i,i遍历上下边界，l,r为快慢指针,这样不会重复 
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			for(int l=1,r=1;r<=m;r++){
				while(l<=r && prefix[j][r]-prefix[j][l-1]-prefix[i-1][r]+prefix[i-1][l-1]>k)	l++;
				if(l<=r)	res+=r-l+1;//新增的子矩阵个数,比如l为1,r变为3, 多了 123,23,3三个子矩阵(不用管行)
			}
		}
	}
	cout<<res;
	return 0;
}