# 二分与前缀和 学习笔记

Gettler•Main 2021-01-29 21:59

# 二分与前缀和

## 二分

### 整数金额二分

``````bool check(int x) {
/*查验 x 是不是符合要求*/
}

// 区段[l, r]被区划成[l, mid - 1]和[mid, r]时应用：
void bsearch_1(int l, int r) {
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
}
// 区段[l, r]被区划成[mid + 1, r]和[l, mid]时应用：
void bsearch_1(int l, int r) {
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid))
l = mid + 1;
else
r = mid;
}
}
``````
##### 789. 数的范畴

`1≤n≤100000,`

`1≤q≤10000,`

`1≤k≤10000`

``````6 3
1 2 2 3 3 4
3
4
5
``````

``````3 4
5 5
-1 -1
``````

``````#include

using namespace std;
const int N = 100001;
int a[N];

int main() {
int n, k, x;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < k; i++) {
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[r] == x) {
cout << r << " ";
//寻找左节点后找右节点
r = n - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (a[mid] <= x)
l = mid;
else
r = mid - 1;
}
cout << l << endl;
} else//找不着左节点立即輸出 -1 -1
cout << "-1 -1" << endl;
}
return 0;
}
``````

### 浮点数二分

``````bool check(int x) {
/*查验 x 是不是符合要求*/
}

void bserach(double l, double r) {
while (r - l > 1e6) {//题型规定精密度
double mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
}
``````
##### 790. 数的三次方根

`−10000 ≤ n ≤ 10000`

``````1000.00
``````

``````10.000000
``````

``````#include
#include

using namespace std;

int main() {
double n;
bool fu = false;
cin >> n;
if (n < 0) {
fu = true;
n *= (-1);
}
double l = 0, r = 10001;
double mid;
while (r - l > 1e-8) {
mid = (l + r) / 2;
if (mid * mid * mid > n)
r = mid;
else
l = mid;
}
if (fu)
mid *= (-1);
printf("%.6f", mid);
return 0;
}
``````

## 前缀和

• 前缀和引流矩阵 S x y = S x − 1 , y + S x , y − 1 − S x − 1 , y − 1 + a x , y S_{xy} = S_{x-1,y} + S_{x,y-1} - S_{x-1,y-1} + a_{x,y} Sxy​=Sx−1,y​+Sx,y−1​−Sx−1,y−1​+ax,y​ （容斥原理）
• 运用前缀和矩阵运算子引流矩阵的和 [ x 1 y 1 , x 2 y 2 ] = S x 2 , y 2 − S x 2 , y 1 − 1 − S x 1 − 1 , y 2 + S x 1 − 1 , y 1 − 1 [x_1y_1,x_2y_2] = S_{x_2,y_2} - S_{x_2,y_1-1} - S_{x_1-1,y_2} + S_{x_1-1,y_1-1} [x1​y1​,x2​y2​]=Sx2​,y2​​−Sx2​,y1​−1​−Sx1​−1,y2​​+Sx1​−1,y1​−1​
##### 1230. K倍区段

`1 ≤ N , K ≤ 100000`

`1 ≤ Ai ≤ 100000`

``````5 2
1
2
3
4
5
``````

``````6
``````

``````#include

using namespace std;
const int N = 100010;
long long int n, k, x, ans = 0;
long long int s[N];
long long int res[N];

int main() {
cin >> n >> k;
res[0] = 1;
//s[0]%k=0,故余数为0的数早已有一个了
for (long long int i = 1; i <= n; i++) {
cin >> x;
s[i] = s[i - 1] + x;
ans += res[s[i] % k];
res[s[i] % k]++;
}
cout << ans << endl;
return 0;
}
``````

• 消灭零回复

## 最新评论

• 01月26日

我是这篇文章的创作本人 请您把文章删了 ...