写在前面

二分答案和差分构造上我一直是苦手,写这一篇存档记录一下可用的模板。

Problem1

描述:

给定升序排列数组 \(a[n]\) 以及 \(q\) 个查询,每次查询 \(k\) 在数组中的起始位置。

题解:

二分查找,贴一个模板还有一个暴力(前者45ms,后者39ms)

模板:

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];
int n, q;

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    while(q--)
    {
        int k;
        scanf("%d", &k);
        int l = 1, r = n;
        while(l < r)// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
        {
            int mid = l + r >> 1;
            if(a[mid] >= k)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if(a[l] != k)
        {
            printf("-1 -1\n");
            continue;
        }
        else
        {
            printf("%d ", l - 1);
            r = n;
            while(l < r)// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
            {
                int mid = l + r + 1 >> 1;
                if(a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", r - 1);
        }
    }
}

暴力

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];
int n, q;

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    while(q--)
    {
        int k;
        scanf("%d", &k);
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(a[mid] >= k)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if(a[l] != k)
        {
            printf("-1 -1\n");
            continue;
        }
        else
        {
            for(r = l; r <= n && a[r] == k; r ++);
            printf("%d %d\n", l - 1, r - 2);
        }
    }
}

Problem2

描述:

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标,对于每个询问输出子矩阵中所有数的和。

题解:

二维前缀和模板,举个例子画一下就知道怎么做了

模板:

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

int a[N][N], s[N][N];
int n, m, q;

int main()
{
    cin >> 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];
        }
    }
    int x1, y1, x2, y2;
    while(q--)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        printf("%d\n", ans);
    }
}

Problem3

描述:

输入一个长度为n的整数序列,接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c,输出进行完所有操作后的序列。

题解:

一维差分模板,构造数组 \(b[n]\) ,使其满足 \(a[i]\)\(b[i]\) 的前缀和

你当然可以用线段树解决

模板:

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N], b[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", a + i);
        b[i] = a[i] - a[i - 1];
    }
    
    int l, r, c;
    while(m --)
    {
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;
        b[r + 1] -= c;
    }
    
    for(int i = 1; i <= n; i ++)
    {
        b[i] = b[i] + b[i - 1];
        printf("%d ", b[i]);
    }
    return 0;
}

Problem4 机器人跳跃问题

描述:

字节跳动2019校招题,此处代码为\(O(nlogn)\)的二分,还有更优的\(O(n)\)算法下面链接自取

https://www.nowcoder.com/questionTerminal/7037a3d57bbd4336856b8e16a9cafd71

题解:

第一想法就是二分答案,但是被右边界坑了两发,check函数竟然最终会爆long long,所以只要超过范围就直接返回即可。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;

ll n, h[N];

bool check(ll x)
{
    for(int i = 1; i <= n; i ++)
    {
        x += x - h[i];
        if(x < 0) return false;
        if(x > N) return true;
    }
    return true;
}

int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++) scanf("%lld", h + i);
    
    ll l = 0, r = N;
    while(l < r)
    {
        ll mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout<<l<<endl;
}

间歇性踌躇满志,持续性混吃等死