网站建设公司,国外网站开发文献,a站下载安装,wordpress一个主站多个子站文章目录 前言Ⅰ. 数的范围0x00 算法思路0x00 代码书写 Ⅱ. 数的三次方根0x00 算法思路0x01代码书写 Ⅲ. 前缀和0x00 算法思路0x01 代码书写 Ⅳ. 子矩阵的和0x00 算法思路0x01 代码书写 Ⅴ. 机器人跳跃问题0x00 算法思路0x01 代码书写 Ⅵ. 四平方和0x00 算法思路0x01 代码书写 … 文章目录 前言Ⅰ. 数的范围0x00 算法思路0x00 代码书写 Ⅱ. 数的三次方根0x00 算法思路0x01代码书写 Ⅲ. 前缀和0x00 算法思路0x01 代码书写 Ⅳ. 子矩阵的和0x00 算法思路0x01 代码书写 Ⅴ. 机器人跳跃问题0x00 算法思路0x01 代码书写 Ⅵ. 四平方和0x00 算法思路0x01 代码书写 Ⅶ. 分巧克力0x00 算法思路0x01 代码书写 Ⅷ. 激光炸弹0x00 算法思路0x01 代码书写 Ⅸ. K倍区间0x00 算法思路0x01 代码书写 总结 前言
本篇博客主要打卡记录博主学习蓝桥杯CAB组辅导课的习题第一章节的题目。 Ⅰ. 数的范围
0x00 算法思路
详细可以看下这一篇博客详细讲解了二分算法知识 【algorithm】算法基础课—二分查找算法附笔记 | 建议收藏
0x00 代码书写
#include iostreamusing namespace std;const int maxn 100005;
int n, q, x, a[maxn];int main()
{scanf(%d%d, n, q);for (int i 0; i n; i) scanf(%d, a[i]);while (q--) {scanf(%d, x);int l 0, r n - 1;while (l r) {int mid l r 1;if (a[mid] x) l mid 1;else r mid;}if (a[l] ! x) {printf(-1 -1\n);continue;}int l1 l, r1 n;while (l1 1 r1) {int mid l1 r1 1;if (a[mid] x) l1 mid;else r1 mid;}printf(%d %d\n, l, l1);}return 0;
}Ⅱ. 数的三次方根
0x00 算法思路
1.迭代的思路就是无脑迭代100次就可. 2.根据题目法写的方法其实这个就是while(r-l谁就行啦).
0x01代码书写
#includeiostream
#includecstdiousing namespace std;int main()
{double n;scanf(%lf,n);double l -100000, r 100000;while(r - l 0.00000001){double mid (l r) / 2;if(mid * mid * mid n) r mid;else l mid;}printf(%.6lf,l);return 0;
}Ⅲ. 前缀和
0x00 算法思路
详细知识看算法基础课笔记 前缀和与差分 【algorithm】认真讲解前缀和与差分 (图文搭配)
0x01 代码书写
#includeiostreamusing namespace std;int n,m;
int sum[100010];int main()
{cinnm;for(int i1;in;i){int tmp;cintmp;sum[i]sum[i-1]tmp;}while(m--){int l,r;cinlr;coutsum[r]-sum[l-1]endl;}return 0;
}Ⅳ. 子矩阵的和
0x00 算法思路
详细知识看算法基础课笔记 前缀和与差分 【algorithm】认真讲解前缀和与差分 (图文搭配)
0x01 代码书写
#includeiostreamusing namespace std;int n,m,q;
int s[1010][1010];int main()
{cinnmq;for(int i1;in;i)for(int j1;jm;j){cins[i][j];}for(int i1;in;i){for(int j1;jm;j){s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1];}}while(q--){int x1,y1,x2,y2;cinx1y1x2y2;couts[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1]endl;}return 0;
}Ⅴ. 机器人跳跃问题
0x00 算法思路
这一道题主要考查了二分答案的算法通过物理计算得到不论是从低到高还是从高到低都是e 2 * e - h[i] 所以我们假设有一个临界点 E0 满足 0 ~ E0 能量是不满足的E0 ~ 0x3f3f3f3f 是满足的就可以使用y总的二分模板了。
0x01 代码书写
#includebits/stdc.husing 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;//防止爆intelse if(e 0) return false; }return true;
}int main()
{cin n;for(int i 1 ; i n ; i) cin h[i];int l 0 , r 1e5;while(l r){int mid l r 1;if(check(mid)) r mid;else l mid 1;}cout r endl;return 0;
}Ⅵ. 四平方和
0x00 算法思路
这一道题我没学具体的算法思路感觉不如暴力来的实在确信哈哈哈
0x01 代码书写
#includeiostream
#includecmathusing namespace std;int n;
int a,b,c,d;int main()
{scanf(%d,n);for(int a0;a*an;a){for(int ba;a*ab*bn;b){for(int cb;a*ab*bc*cn;c){int tn-a*a-b*b-c*c;int dsqrt(t);if(d*dt){printf(%d %d %d %d\n,a,b,c,d);return 0;}}}}return 0;
}Ⅶ. 分巧克力
0x00 算法思路
这道题主要考查了二分算法主要是对于一块大巧克力进行分割思考的到当分割的块数越多边长就越短块数越少边长就越大所以肯定可以有一个临界点 mid 可以使得刚好的块数 满足要求 刚好 k 块 如果边长 在 Left ~ mid 之间的话 就是边长很大 所以check函数可以判断这个 如果在 mid ~ Right 之间的话 肯定是都满足要求的。 最后套用y总的算法模板即可
0x01 代码书写
#includebits/stdc.husing namespace std;const int N 100010;int n,k;
int h[N],w[N];bool check(int mid)
{int res 0;for(int i 0 ; i n ; i){res (long long)h[i] / mid * (w[i] / mid);if(res k) return true;}return false;
}int main()
{cin n k;for(int i 0 ; i n ; i) cin h[i] w[i];int l 1 , r 1e5;while(l r){int mid l r 1 1;if(check(mid)) l mid;else r mid - 1;}cout r endl;return 0;
}Ⅷ. 激光炸弹
0x00 算法思路
贴一个acwing的图片 链接 AcWing 99. 激光炸弹第一题解
0x01 代码书写
#includebits/stdc.husing namespace std;const int N 5010;
int cnt,r;
int s[N][N];
int n,m;int main()
{cin cnt r;rmin(r,5001);n m r;while(cnt --){int x,y,w;cin x y w;x ;y ;n max(x,n);m max(y,m);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; 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 \n;return 0;
}Ⅸ. K倍区间
0x00 算法思路
这一道题我只是用了 前缀和做优化感觉我考试的时候也想不到y总的算法思路呜呜呜呜呜…
0x01 代码书写
#includeiostreamusing namespace std;int n,k;
int a[100010];
int sum[100010];int main()
{cinnk;for(int i1;in;i) cina[i];int ans0,i0;for(i1;in;i){sum[i]sum[i-1]a[i];}for(int j1;ji;j){for(int sj1;si;s){if((sum[s]-sum[j])%k0) // 前缀和优化{ans;}else continue;}}coutans;return 0;
}总结
本篇博客主要讲解了前缀和 和 二分算法的知识前面四道题都是算法基础课 的模板题后面几道题才是真正考查这两个算法的真实难度开始我也觉得很难很难但是认真学习完发现其实还是可以学会的所以请热爱 请认真学习总会学好总会获得不小的进步的加油吧夏目浅石.
