XP04-02 DAY01
2025-08-02 21:00:29
发布于：上海
DAY01 主要进行了普及组复赛知识点的复习。除此之外，还学习了提高组初赛的知识点：ST表。
普及组复赛知识点：结构体排序，前缀和&差分，双指针和二分（查找与答案）。
这里主要总结二维前缀和，双指针和二分。
一. 二维前缀和
定义：表示以为左上角，以为右下角的矩阵和。
二位前缀和主要有两个重要的部分：
1.的计算：
从此图可得知：是
2.从左上角到右下角的矩阵和计算。
从此图可知：
二.二分
这是一个很玄学的东西，需要凭感觉。
相关题目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停止后，变量是处在一个的状态的。
又知一定大于等于。
所以可以直接输出。
二分答案：
相关题目：题目二
三.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;
}
四.考试题目
题目一：区间
此题是二分答案。考试时没做出来的原因：对于二分题目接触过少。
总结：可以少学一点，多练一点。
判断二分的原因：首先,满足条件。
其次，数组中适合的起始位置大概是这样分布的： （其中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;
}
题目二：排列缺失
此题除了用到一点前缀和外，难点集中在读懂题目和理清思路上。
思路大概是这样的：
以第二个样例为例，可以画一个图：
5
4 5 3 1 2
4 5 1 3 2
五.每日拓展
今天的T4是返回贪心的题目。
题目：链接描述
个人认为返回贪心只要想到了就不难。
在认为有点像DP但又不会写DP时，可以考虑返回贪心。
但是对于此题根本就没有返回贪心的想法。
个人认为也是因为做的太少了，还是得多练。
有帮助，赞一个