搜索内容

有一个问题?

如果您有任何疑问,可以在下面询问或输入您要寻找的!

二分与前缀和 学习笔记

生成海报
Gettler•Main
Gettler•Main 2021-01-29 21:59
阅读需:0

二分与前缀和

二分

整数金额二分

整数金额二分要留意界限,最好是背过一套模版

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. 数的范畴

给出一个依照升序排序的长短为n的整数金额二维数组,及其 q 个查看。

针对每一个查看,回到一个原素k的起止部位和停止部位(部位从0开始记数)。

假如二维数组中不会有该原素,则回到“-1 -1”。

键入文件格式:

第一行包括整数金额n和q,表明数组长度和了解数量。

第二行包括n个整数金额(均在1~10000范畴内),表明详细二维数组。

下面q行,每排包括一个整数金额k,表明一个了解原素。

輸出文件格式

共q行,每排包括2个整数金额,表明所愿原素的起止部位和停止部位。

假如二维数组中不会有该原素,则回到“-1 -1”。

数据信息范畴:

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. 数的三次方根

给出一个浮点数n,求它的三次方根。

键入文件格式:

共一行,包括一个浮点数n。

輸出文件格式

共一行,包括一个浮点数,表明难题的解。

留意,結果保存6位小数。

数据信息范畴:

−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倍区段

给出一个长短为 N 的数列,A1,A2,…AN,假如在其中一段持续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍率,大家就称这一区段 [ i , j ] 是 K 倍区段。

你可以求出数列中一共有多少个 K 倍区段吗?

键入文件格式:

第一行包括2个整数金额 N 和 K。

下列 N 行每排包括一个整数金额 Ai。

輸出文件格式

輸出一个整数金额,意味着 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;
} 
评论
  • 消灭零回复