基本熟練掌握了。

目錄

• 789. 數的范圍 【整數二分 板子題】
• 790. 數的三次方根 【實數二分】
• 795. 前綴和 【一維前綴和 板子題】
• 796. 子矩陣的和 【二維前綴和 板子題】
• 730. 機器人跳躍問題 【二分】
• 1221. 四平方和 【二分 / 哈希】
• 1227. 分巧克力 【二分】
• 99. 激光炸彈 【二維前綴和】
• 1230. K倍區間 【前綴和 / 思維】

789. 數的范圍 【整數二分 板子題】

題目詳解

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

790. 數的三次方根 【實數二分】

實數二分的值是連續的，所以不用考慮死循環的情況

#include<bits/stdc++.h> using namespace std; int main(void) {double s; cin>>s;double l=-1000,r=1000;while(r-l>1e-7){double mid=(l+r)/2;if(mid*mid*mid>=s) r=mid;else l=mid;}printf("%.6lf",l);return 0; }

795. 前綴和 【一維前綴和 板子題】

前綴和用來解決一個靜態的數組當需要求解一段區間的值的時候所用的。
用一個數組來保存當前位，前面的數的和。
當我們查找時，只需要兩個數相減即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,m; int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];while(m--){int l,r; cin>>l>>r;cout<<a[r]-a[l-1]<<endl;}return 0; }

796. 子矩陣的和 【二維前綴和 板子題】

詳細講解
代碼如下:

#include<bits/stdc++.h> using namespace std; const int N=1010; int s[N][N],n,m,k; int main(void) {cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>s[i][j],s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];while(k--){int x,y,xx,yy; cin>>x>>y>>xx>>yy;cout<<s[xx][yy]-s[xx][y-1]-s[x-1][yy]+s[x-1][y-1]<<endl;} }

730. 機器人跳躍問題 【二分】

你會發現當
H(k+1)>E時
結果為 E-(H-E)=2E-H
當H(k+1)<E時
E+E-H=2E-H
所以不管如何運算的結果都是一樣的。

#include<cstdio> #include<iostream> #include<cstring> #include<string> using namespace std;const int N=100010;int n; int h[N]; bool check(int e) {for(int i=1;i<=n;i++){e=e*2-h[i];if(e>=1e5) return true;//可能會爆long longif(e<0) return false; }return true; } int main(void) {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&h[i]);int l=0,r=1e5;while(l<r){int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}printf("%d\n",r);return 0; }

1221. 四平方和 【二分 / 哈希】

方式一:暴力 不過會超時

#include<cstdio> #include<iostream> #include<cmath> using namespace std; const int N=2500010; int n; int main(void) {cin>>n;for(int a=0;a*a<=n;a++){for(int b=a;b*b+a*a<=n;b++){for(int c=b;c*c+b*b+a*a<=n;c++){int t=n-a*a-b*b-c*c;int d=sqrt(t);if(d*d==t){printf("%d %d %d %d\n",a,b,c,d);return 0;}}}}return 0; }

方式二：二分

#include<cstring> #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N=2500010; struct Sum {int s,c,d;bool operator< (const Sum &t)const{if(s!=t.s) return s<t.s;if(c!=t.c) return c<t.c;return d<t.d;} }sum[N];int n,m;int main(void) {cin>>n;for(int c=0;c*c<=n;c++){for(int d=c;c*c+d*d<=n;d++){sum[m++]={c*c+d*d,c,d};}}sort(sum,sum+m);for(int a=0;a*a<=n;a++){for(int b=0;a*a+b*b<=n;b++){int t=n-a*a-b*b;int l=0,r=m-1;while(l<r){int mid=l+r>>1;if(sum[mid].s>=t) r=mid;else l=mid+1;}if(sum[l].s==t){printf("%d %d %d %d\n",a,b,sum[l].c,sum[l].d);return 0;}}}return 0; } #include<cstring> #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N=1e7+10; struct node {int x,y,s; }ve[N]; int n; bool cmp(node a,node b) {if(a.s==b.s) {if(a.x==b.x) return a.y<b.y;return a.x<b.x;}return a.s<b.s; } int main(void) {cin>>n;int k=0;for(int i=0;i*i<=n;i++)for(int j=i;j*j+i*i<=n;j++)ve[k++]={i,j,i*i+j*j};sort(ve,ve+k,cmp);for(int i=0;i*i<=n;i++){for(int j=0;j*j+i*i<=n;j++){int temp=n-i*i-j*j;int l=0,r=k-1;while(l<r){int mid=(l+r)/2;if(ve[mid].s>=temp) r=mid;else l=mid+1;}if(ve[l].s==temp){printf("%d %d %d %d\n",i,j,ve[l].x,ve[l].y);return 0;}}}return 0; }

1227. 分巧克力 【二分】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,k; struct node {int x,y; }s[N]; bool check(int mid) {int sum=0;for(int i=0;i<n;i++) sum+=(s[i].x/mid)*(s[i].y/mid);if(sum>=k) return true;else return false; } int main(void) {cin>>n>>k;for(int i=0;i<n;i++) cin>>s[i].x>>s[i].y;int l=1,r=1e6;while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<l<<endl;return 0; }

99. 激光炸彈 【二維前綴和】

#include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N = 5010;int n, m; int s[N][N];int main() {int cnt, R;cin >> cnt >> R;R = min(5001, R);n = m = R;while (cnt -- ){int x, y, w;cin >> x >> y >> w;x ++, y ++ ;n = max(n, x), m = max(m, y);s[x][y] += w;}// 預處理前綴和for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];int res = 0;// 枚舉所有邊長是R的矩形，枚舉(i, j)為右下角for (int i = R; i <= n; i ++ )for (int j = R; j <= m; j ++ )res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);cout << res << endl;return 0; } #include<bits/stdc++.h> using namespace std; const int N=5010; int a[N][N],n,r; int main(void) {cin>>n>>r;r=min(r,5000);while(n--){int x,y,w; cin>>x>>y>>w;a[x+1][y+1]+=w;}for(int i=1;i<=5000;i++)for(int j=1;j<=5000;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];int ans=0;for(int i=r;i<=5000;i++){for(int j=r;j<=5000;j++){int x=i-r+1,y=j-r+1;int xx=i,yy=j;int sum=a[xx][yy]-a[x-1][yy]-a[xx][y-1]+a[x-1][y-1];ans=max(ans,sum);}}cout<<ans;return 0; }

1230. K倍區間 【前綴和 / 思維】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long int LL; LL a[N],s[N],st[N],n,k,ans; int main(void) {cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];st[0]++;for(int i=1;i<=n;i++){int t=s[i]%k;ans+=st[t];st[t]++;}cout<<ans;return 0; }

總結

以上是生活随笔為你收集整理的第二章：二分和前缀和 【完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。