Acwing 蓝桥杯 第二章 二分与前缀和

今天来补一下之前没写的总结，题是写完了，但是总结没写

感觉没什么好总结的啊，就当打卡了

789. 数的范围 - AcWing题库

思路：

一眼二分，典中典

先排个序，再用lower_bound和upper_bound维护相同的数的左界和右界就好了

注意特判无解

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=1e5+10;
const int mxe=2e5+10;
using namespace std;int n,q,x;
int a[mxn];
bool check(int x){return x>=0&&x<=n-1;
}
void solve(){cin>>n>>q;for(int i=0;i<n;i++) cin>>a[i];while(q--){cin>>x;int pos1=lower_bound(a,a+n,x)-a;int pos2=upper_bound(a,a+n,x)-a-1;if((!check(pos1)||!check(pos2))||(pos1>pos2)) cout<<-1<<" "<<-1<<'\n';else cout<<pos1<<" "<<pos2<<'\n';}
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

790. 数的三次方根 - AcWing题库

思路：

注意到答案具有单调性，因此二分即可

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=1e5+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;double n,ans;
bool check(double x){return x*x*x>=n;
}
void solve(){cin>>n;double l=-10000.0,r=10000.0;while(abs(r-l)>eps){double mid=(l+r)/2;if(check(mid)){ans=mid;r=mid;}else l=mid;}cout<<fixed<<setprecision(6)<<ans<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 795. 前缀和 - AcWing

思路：

大一学弟也会写的前缀和板子

Code：

#include <bits/stdc++.h>
#define int long long
const int mxn=1e5+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;int n,m,l,r;
int a[mxn],sum[mxn];
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];while(m--){cin>>l>>r;cout<<sum[r]-sum[l-1]<<"\n";}
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

796. 子矩阵的和 - AcWing题库

同样是大一学弟也会的二维前缀和，但是我可能不太会，嘻

Code：

#include <bits/stdc++.h>
#define int long long
#define y1 Y1
const int mxn=1e3+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;int n,m,q,x1,y1,x2,y2;
int a[mxn][mxn],sum[mxn][mxn];
void solve(){cin>>n>>m>>q;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++) sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];}while(q--){cin>>x1>>y1>>x2>>y2;cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<'\n';}
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

730. 机器人跳跃问题 - AcWing题库

思路：

答案具有二分性，可以直接二分

然后在check函数里去模拟这个过程，如果中间存在能量值<0的情况就false，否则如果出现大于maxH的情况，那么剩下的只会得到，因此直接true就好了

Code：

#include <bits/stdc++.h>
#define int long long
#define y1 Y1
const int mxn=1e5+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;int n,mx=-1;
int h[mxn];
bool check(int x){int res=x;for(int i=0;i<=n;i++){if(h[i+1]>res){res-=(h[i+1]-res);}else{res+=(res-h[i+1]);}if(res>=mx) return true; if(res<0) return false;}return res>=0;
}
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>h[i],mx=max(mx,h[i]);int l=0,r=1e5;int ans;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}//check(19);cout<<ans<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

AcWing 1221. 四平方和 - AcWing

思路：

四指针枚举，想到先把两个指针的结果哈希一下，然后再去枚举两个指针，一个指针的复杂度是sqrt(n)，两个就是O(n)的了

Code：

#include <bits/stdc++.h>
#define int long long
#define y1 Y1
const int mxn=2e5+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;map<int,pair<int,int> > v;
int n,len=0;
void solve(){cin>>n;for(int i=0;i*i<=n;i++){for(int j=0;i*i+j*j<=n;j++){v[i*i+j*j]={i,j};}}for(int i=0;i*i<=n;i++){for(int j=0;i*i+j*j<=n;j++){if(v.count(n-i*i-j*j)){cout<<i<<" "<<j<<" "<<v[n-i*i-j*j].second<<" "<<v[n-i*i-j*j].first<<'\n';return;}}}
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

1227. 分巧克力 - AcWing题库

思路：

直接去二分边长，然后去check函数计算能有多少巧克力块就行

Code：

#include <bits/stdc++.h>
#define int long long
#define y1 Y1
const int mxn=1e5+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;
struct ty{int h,w;
}p[mxn];int n,k;
bool check(int x){int res=0;for(int i=1;i<=n;i++){res+=(p[i].h/x)*(p[i].w/x);}return res>=k;
}
void solve(){cin>>n>>k;for(int i=1;i<=n;i++) cin>>p[i].h>>p[i].w;int l=1,r=1e5;int ans;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=mid;l=mid+1;}else r=mid-1;}cout<<ans<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

99. 激光炸弹 - AcWing题库

思路：

数据范围都比较小，因此可以直接求个二维前缀和，然后求二维差分，维护最大值即可

#include <bits/stdc++.h>
//#define int long long
#define y1 Y1
const int mxn=5e3+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;int n,r,x,y,w;
int a[mxn][mxn];
void solve(){cin>>n>>r;r=min(r,5001);for(int i=1;i<=n;i++){cin>>x>>y>>w;x++,y++;a[x][y]+=w;}for(int i=1;i<=5001;i++){for(int j=1;j<=5001;j++) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];}int ans=-1e9;for(int i=1;i+r-1<=5001;i++){for(int j=1;j+r-1<=5001;j++){int x1=i,y1=j;int x2=i,y2=j+r-1;int x3=i+r-1,y3=j;int x4=i+r-1,y4=j+r-1;int S=a[x4][y4]-a[x2-1][y2]-a[x3][y3-1]+a[x1-1][y1-1];ans=max(ans,S);}}cout<<ans<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}

1230. K倍区间 - AcWing题库

思路：

很典，直接求前缀和，然后对前缀和取模k，两个模为0的点就可以作为k倍区间端点，然后用动态map维护即可，也可以算C(n,2)

Code：

#include <bits/stdc++.h>
#define int long long
#define y1 Y1
const int mxn=1e5+10;
const int mxe=2e5+10;
const double eps=1e-8;
using namespace std;map<int,int> mp;
int n,k;
int a[mxn],sum[mxn];
void solve(){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i],sum[i]%=k;int ans=0;for(int i=1;i<=n;i++){ans+=mp[sum[i]];mp[sum[i]]++;}cout<<ans+mp[0]<<'\n';
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}