Acwing二分和前缀和（一）

WuShF

发布于 2024-02-17 09:13:53

1410

发布于 2024-02-17 09:13:53

文章被收录于专栏：笔记分享笔记分享

数的范围

原题链接：https://www.acwing.com/problem/content/791/

整数二分步骤，找一个区间，使得答案一定在区间中。
找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点。
分析终点在该判断条件下是否成立，根据是否成立，考虑在哪个区间。
如果更新方式写的是R=Mid，则不用做任何处理。如果写的是L=Mid，则需要在计算Mid时+1。

在本题中：

判断条件就是左右区间的边界。两个端点会划分三个区间，不具二段性。但可以先找左端点，再找右端点。

左端点的判断条件是mid>=x，因为是升序的，如果成立，说明左端点l只会在mid上或mid左侧。将右端点调整为mid，这样mid只会不变或变小。现在变小了，说明目前的l并非答案的左区间，中间掺杂了更小的数列，此时需要使左区间l+1。左端点是通过l查找，l从0累加，不会产生遗漏。左端点确定之后，右端点从n-1，也就是最右端开始，累减，确定答案的右端点。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using 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/

#include<iostream>
#include<cstdio>

using 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_2,y_2}-S_{x_2,y_1-1}-S_{x_1-1,y_2}+S_{x_1-1.y_1-1}

#include<iostream>
#include<cstdio>

using 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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-02-17，如有侵权请联系 cloudcommunity@tencent.com 删除

include