XP04-02 DAY01

2025-08-02 21:00:29

发布于：上海

27阅读

0回复

0点赞

DAY01 主要进行了普及组复赛知识点的复习。除此之外，还学习了提高组初赛的知识点：ST表。
普及组复赛知识点：结构体排序，前缀和&差分，双指针和二分（查找与答案）。
这里主要总结二维前缀和，双指针和二分。
一. 二维前缀和
定义： $s[i][j]$ 表示以 $(1,1)$ 为左上角，以 $(i,j)$ 为右下角的矩阵和。
二位前缀和主要有两个重要的部分：
1. $s[i][j]$ 的计算：

从此图可得知：是 $s[i][]j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$
2.从左上角 $(x1,y1)$ 到右下角 $(x2,y2)$ 的矩阵和计算。

从此图可知： $ANS=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]$
二.二分
这是一个很玄学的东西，需要凭感觉。
相关题目1：题1 这道题目属于二分查找。
有三种普遍做法：
1.最简洁的版本：

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x;
	cin>>x;
	cout<<lower_bound(a+1,a+1+n,x)-a;
	return 0;
}

使用了一个lower_bound()函数。
2.通用的初学版本：

#include<bits/stdc++.h>
using namespace std;
int a[105];	
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x,l,r;
	cin>>x;
	l=1,r=n;
	int ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid]>=x){
			ans=mid;
			r=mid-1;
		}else l=mid+1;
	}
	cout<<ans;
	return 0;
}

3.比赛时使用的高级版本：

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x;
	cin>>x;
	int l,r;
	l=1,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]>=x)r=mid;
		else l=mid+1;
	}
	cout<<l;
	return 0;
}

其实在while停止后，变量是处在一个 $l=r$ 的状态的。
又知 $r$ 一定大于等于 $x$ 。
所以可以直接输出 $l$ 。
二分答案：
相关题目：题目二
三.ST表
只是模板。

#include<bits/stdc++.h>
using namespace std;
int a[500005];
int dp_min[500005][25];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	} 
	for(int i=1;i<=m;i++){
		dp_min[i][0]=a[i];
	}
	for(int k=1;k<=log2(m);k++){
		for(int i=1;i<=m;i++){
			if(i+(1<<(k-1))>m)break;
			dp_min[i][k]=min(dp_min[i][k-1],dp_min[i+(1<<(k-1))][k-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		int k=log2(r-l+1);
		cout<<min(dp_min[l][k],dp_min[r-(1<<k)+1][k])<<" ";
	}
	return 0;
}

四.考试题目
题目一：区间
此题是二分答案。考试时没做出来的原因：对于二分题目接触过少。
总结：可以少学一点，多练一点。
判断二分的原因：首先 $n*k\le1e10$ ,满足条件。
其次，数组 $b$ 中适合的起始位置 $l$ 大概是这样分布的： $000000000011111111$ （其中0为适合的起始位置，1为不适合的起始位置）。
那么就可以二分查找一下第一个1。
然后下标减1即最后一个0。
然后check()里面添一点东西即可。
注：向上取整：
1.int ans=(m-n+1)/n;
2.int ans=ceil(m/n);
代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
long long x;
int a[100005];
long long sum[100005];
bool check(long long id){
	long long sz;//所属组。
	sz=(id+n-1)/n;
	long long tot=(k-sz)*sum[n];
	int st=id%n;
	if(st==0)st=n;
	for(int i=st;i<=n;i++){
		tot+=a[i];
	}
	if(tot>=x)return 0;
	return 1;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>k>>x;
		memset(sum,0,sizeof sum);
		memset(a,0,sizeof a);
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum[i]=sum[i-1]+a[i];
		}
		long long l=1;
		long long r=1e10;
		while(l<r){
			long long mid=l+r>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		cout<<l-1<<endl;
	}
	return 0;
}