万一打仗哪个省最安全,安卓优化大师清理,优化大师使用心得,阿里云创建网站数的范围 原题链接#xff1a;https://www.acwing.com/problem/content/791/ 整数二分步骤#xff0c;找一个区间#xff0c;使得答案一定在区间中。找一个判断条件#xff0c;使得该判断条件具有二段性#xff0c;并且答案一定是该二段性的分界点。分析终点在该判断条件下…数的范围 原题链接https://www.acwing.com/problem/content/791/ 整数二分步骤找一个区间使得答案一定在区间中。找一个判断条件使得该判断条件具有二段性并且答案一定是该二段性的分界点。分析终点在该判断条件下是否成立根据是否成立考虑在哪个区间。如果更新方式写的是RMid则不用做任何处理。如果写的是LMid则需要在计算Mid时1。
在本题中
判断条件就是左右区间的边界。两个端点会划分三个区间不具二段性。但可以先找左端点再找右端点。
左端点的判断条件是midx因为是升序的如果成立说明左端点l只会在mid上或mid左侧。 将右端点调整为mid这样mid只会不变或变小。 现在变小了说明目前的l并非答案的左区间中间掺杂了更小的数列此时需要使左区间l1。 左端点是通过l查找l从0累加不会产生遗漏。 左端点确定之后右端点从n-1也就是最右端开始累减确定答案的右端点。
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includevectorusing namespace std;const int N 100000;
int n, m;
int q[N];int main() {scanf(%d%d, n, m);for (int i 0; i n; i) scanf(%d, q[i]);for (int i 0; i m; i) {int x;scanf(%d, x);int l 0, r n - 1;while (l r) {int mid l r 1;if (q[mid] x)r mid;else l mid 1;}if (q[r] x) {cout r ;r n - 1;while (l r) {int mid l r 1 1;if (q[mid] x)l mid;else r mid - 1;}cout l endl;} else cout -1 -1 endl;}
}
数的三次方根 原题链接https://www.acwing.com/problem/content/792/ 这里求二分之一不能用位移因为是浮点数。
#include iostream
#include cstdio
using namespace std;
double x;
int main() {cin x;double l -100000, r 100000;while (r - l 1e-8) {double mid (l r) / 2;if (mid * mid * mid x) l mid;else r mid;}printf(%.6f, r);return 0;
}
前缀和 原题链接https://www.acwing.com/problem/content/797/ #includeiostream
#includecstdiousing namespace std;
const int N 100010;
int n, m;
int a[N], s[N];int main() {scanf(%d%d, n, m);for (int i 1; i n; i) {scanf(%d, a i);s[i] s[i - 1] a[i];}while (m--) {int l, r;scanf(%d%d, l, r);printf(%d\n, s[r] - s[l - 1]);}return 0;
}
子矩阵的和 原题链接https://www.acwing.com/problem/content/798/ 如何计算前缀和矩阵
容斥原理 S x , y S x − 1 , y S x , y − 1 − S x − 1 , y − 1 a x , y S_{x,y}S_{x-1,y}S_{x,y-1}-S_{x-1,y-1}a_{x,y} Sx,ySx−1,ySx,y−1−Sx−1,y−1ax,y
如何利用前缀和矩阵计算子矩阵的和
容斥原理 S x 2 , y 2 − S x 2 , y 1 − 1 − S x 1 − 1 , y 2 S x 1 − 1. y 1 − 1 S_{x_2,y_2}-S_{x_2,y_1-1}-S_{x_1-1,y_2}S_{x_1-1.y_1-1} Sx2,y2−Sx2,y1−1−Sx1−1,y2Sx1−1.y1−1
#includeiostream
#includecstdiousing namespace std;
const int N 1e3 10;
int n, m, q;
int a[N][N], s[N][N];int main() {scanf(%d%d%d, n, m, q);for (int i 1; i n; i) {for (int j 1; j m; j) {scanf(%d, a[i][j]);s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1] a[i][j];}}while (q--) {int x1, y1, x2, y2;scanf(%d%d%d%d, x1, y1, x2, y2);printf(%d\n, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]);}return 0;
}
