飞虹网架建设官方网站,私域电商平台排名,成都专业网站排名推广,软件开发工程师需要考什么证书今天来补一下之前没写的总结#xff0c;题是写完了#xff0c;但是总结没写感觉没什么好总结的啊#xff0c;就当打卡了789. 数的范围 - AcWing题库思路#xff1a;一眼二分#xff0c;典中典先排个序#xff0c;再用lower_bound和upper_bound维护相同的数的左界和右界就…今天来补一下之前没写的总结题是写完了但是总结没写感觉没什么好总结的啊就当打卡了789. 数的范围 - AcWing题库思路一眼二分典中典先排个序再用lower_bound和upper_bound维护相同的数的左界和右界就好了注意特判无解Code#include bits/stdc.h
#define int long long
const int mxn1e510;
const int mxe2e510;
using namespace std;int n,q,x;
int a[mxn];
bool check(int x){return x0xn-1;
}
void solve(){cinnq;for(int i0;in;i) cina[i];while(q--){cinx;int pos1lower_bound(a,an,x)-a;int pos2upper_bound(a,an,x)-a-1;if((!check(pos1)||!check(pos2))||(pos1pos2)) cout-1 -1\n;else coutpos1 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 mxn1e510;
const int mxe2e510;
const double eps1e-8;
using namespace std;double n,ans;
bool check(double x){return x*x*xn;
}
void solve(){cinn;double l-10000.0,r10000.0;while(abs(r-l)eps){double mid(lr)/2;if(check(mid)){ansmid;rmid;}else lmid;}coutfixedsetprecision(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 mxn1e510;
const int mxe2e510;
const double eps1e-8;
using namespace std;int n,m,l,r;
int a[mxn],sum[mxn];
void solve(){cinnm;for(int i1;in;i) cina[i],sum[i]sum[i-1]a[i];while(m--){cinlr;coutsum[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 mxn1e310;
const int mxe2e510;
const double eps1e-8;
using namespace std;int n,m,q,x1,y1,x2,y2;
int a[mxn][mxn],sum[mxn][mxn];
void solve(){cinnmq;for(int i1;in;i){for(int j1;jm;j) cina[i][j];}for(int i1;in;i){for(int j1;jm;j) sum[i][j]sum[i-1][j]sum[i][j-1]a[i][j]-sum[i-1][j-1];}while(q--){cinx1y1x2y2;coutsum[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 mxn1e510;
const int mxe2e510;
const double eps1e-8;
using namespace std;int n,mx-1;
int h[mxn];
bool check(int x){int resx;for(int i0;in;i){if(h[i1]res){res-(h[i1]-res);}else{res(res-h[i1]);}if(resmx) return true; if(res0) return false;}return res0;
}
void solve(){cinn;for(int i1;in;i) cinh[i],mxmax(mx,h[i]);int l0,r1e5;int ans;while(lr){int midlr1;if(check(mid)){ansmid;rmid-1;}else lmid1;}//check(19);coutans\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 mxn2e510;
const int mxe2e510;
const double eps1e-8;
using namespace std;mapint,pairint,int v;
int n,len0;
void solve(){cinn;for(int i0;i*in;i){for(int j0;i*ij*jn;j){v[i*ij*j]{i,j};}}for(int i0;i*in;i){for(int j0;i*ij*jn;j){if(v.count(n-i*i-j*j)){couti 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 mxn1e510;
const int mxe2e510;
const double eps1e-8;
using namespace std;
struct ty{int h,w;
}p[mxn];int n,k;
bool check(int x){int res0;for(int i1;in;i){res(p[i].h/x)*(p[i].w/x);}return resk;
}
void solve(){cinnk;for(int i1;in;i) cinp[i].hp[i].w;int l1,r1e5;int ans;while(lr){int midlr1;if(check(mid)){ansmid;lmid1;}else rmid-1;}coutans\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 mxn5e310;
const int mxe2e510;
const double eps1e-8;
using namespace std;int n,r,x,y,w;
int a[mxn][mxn];
void solve(){cinnr;rmin(r,5001);for(int i1;in;i){cinxyw;x,y;a[x][y]w;}for(int i1;i5001;i){for(int j1;j5001;j) a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1];}int ans-1e9;for(int i1;ir-15001;i){for(int j1;jr-15001;j){int x1i,y1j;int x2i,y2jr-1;int x3ir-1,y3j;int x4ir-1,y4jr-1;int Sa[x4][y4]-a[x2-1][y2]-a[x3][y3-1]a[x1-1][y1-1];ansmax(ans,S);}}coutans\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 mxn1e510;
const int mxe2e510;
const double eps1e-8;
using namespace std;mapint,int mp;
int n,k;
int a[mxn],sum[mxn];
void solve(){cinnk;for(int i1;in;i) cina[i],sum[i]sum[i-1]a[i],sum[i]%k;int ans0;for(int i1;in;i){ansmp[sum[i]];mp[sum[i]];}coutansmp[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;
}
