Chapter 2 二分与前缀和

+++

• 二分

• 套路

如果更新方式写的是R = mid， 则不用做任何处理，如果更新方式写的是L = mid，则需要在计算mid是加上1。

1.数的范围 789

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

//整数二分

using namespace std;

int st[100005];

int n, q;

int u;

int main()

{

    scanf("%d%d", &n, &q);

    for(int i = 0; i < n; i++)

        scanf("%d", &st[i]);

    while(q--)

    {

        int L = 0; int R = n - 1;

        scanf("%d", &u);

        while(L < R)

        {

            int md = L + R >> 1;

            if(st[md] >= u) R = md;//注意边界问题

            else L = md + 1;

        }

        if(st[R] == u)

        {

            cout << R << " ";

            R = n - 1;

            while(L < R)

            {

                int md = L + R + 1 >> 1;//注意边界问题

                if(st[md] <= u) L = md;

                else R = md - 1;

            }

            cout << L << endl;

        }

        else    cout << "-1 -1" << endl;

    }

    return 0;

}

2.数的三次方根 790

#include <iostream>

//实数二分

using namespace std;

int main()

{

    double n;

    cin >> n;

    double l = -10000, r = 10000;

    while(r - l > 1e-8)

    {

        double mid = (l + r) / 2;

        if(mid * mid * mid >= n)   r = mid;

        else l = mid;

    }

    printf("%f\n", l);

    return 0;

}

3.机器人跳跃问题 730

//AC code

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

int h[maxn], temp, n;

int main()

{

    cin >> n;

    for(int i = 0; i < n; i++)

        scanf("%d", h + i);

    int l = 0, r = 1e5;

    while(l < r)

    {

        int mid =(l + r) >> 1;//注意边界问题

        temp = mid;

        for(int i = 0; i < n && mid >= 0; i++)

        {

            mid = mid * 2 - h[i];

            if(mid >= 1e5)  break;   //没有这句ac不了，防止中间过程爆掉

        }

        if(mid >= 0)

            r = temp;

        else

            l = temp + 1;

    }

    cout << r << endl;

    return 0;

}

4.四平方和 1221

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 5e6;//注意

int n, m;

struct Sum{

    int s, c, d;

    bool operator< (const Sum &t)const

    {

        if(s != t.s)    return s < t.s;

        if(c != t.c)    return c < t.c;

        return d < t.d;

    }

}p[maxn];

int main()

{

    cin >> n;

    for(int c = 0; c * c <= n; c++ )

        for(int d = c; d * d + c * c <= n; d++ )

            p[m++] = {c * c + d * d, c, d};

    sort(p, p + m);

    for(int a = 0; a * a <= n; a++ )

        for(int b = a; b * b + a * a <= n; b++ )

        {

            int t = n - a * a - b * b;

            int l = 0, r = m - 1;

            while(l < r)

            {

                int mid = (l + r) >> 1;

                if(p[mid].s >= t)  r = mid;

                else l = mid + 1;

            }

            if(p[l].s == t)

            {

                printf("%d %d %d %d\n", a, b, p[l].c, p[l].d);

                return 0;

            }

        }

}

5.分巧克力 1227

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 100010;

int n, k;

int h[maxn], w[maxn];

bool check(int u)

{

    int sum = 0;

    for(int i = 0; i < n; i++)

        sum += (h[i] / u) * (w[i] / u);

    if(sum >= k)    return true;

    return false;

}

int main()

{

    cin >> n >> k;

    for(int i = 0; i < n; i++)

        scanf("%d%d", 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;

}

+++

• 前缀和

1.前缀和 795

//一维数组前缀和

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 100010;

int a[maxn], s[maxn];

int n, m;

int main()

{

    cin >> n >> m;

    for(int i = 1; i <= n; i++ )

    {

        scanf("%d", a + i);

        s[i] = s[i - 1] + a[i];//存储前i个数的和

    }

    while(m--)

    {

        int x, y;

        scanf("%d%d", &x, &y);

        printf("%d\n", s[y] - s[x - 1]);

    }

    return 0;

}

2.子矩阵的和 796

// 二维数组前缀和

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 1010;

int a[maxn][maxn], s[maxn][maxn];

int n, m, q;

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;

}

3.激光炸弹 99

4.K倍区间 1230

//优化时间复杂度

//O(n)

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 100010;

int s[maxn], cnt[maxn];

int n, k, temp;

LL res;

int main()

{

    cnt[0] = 1;

    cin >> n >> k;

    for(int i = 1; i <= n; i++ )

    {

        scanf("%d", &temp);

        s[i] = (s[i - 1] + temp) % k;

        res += cnt[s[i]];

        cnt[s[i]]++;

    }

    printf("%lld\n", res);

    return 0;

}

K倍区间学习到的经验：

1.首先因为知道考的是前缀和，我就用O(n²)的复杂度的二重for循环暴力枚举，果不其然超时，然后就没有了进一步的简化思路。

2.好的思路是从简单暴力的方法中优化出来的，就如本题的AC code，把复杂度降到了O(n)，成功AC。

3.找到右端点后遍历前面所有前缀和，符合K倍区间性质的其实就是mod k后与右端点前缀和mod k后余数相等的点。（★）