蓝桥杯之二分与前缀和

二分

1. 数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

输入样例：

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

输出样例：

1
2
3
3 4
5 5
-1 -1

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> q[i];
    }
    
    while (m--) {
        int x;
        cin >> 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[l] == x) { // 如果查询到了起始位置
            cout << l << ' '; // 输出下标
            
            r = n - 1; // 定右边界，此时l为需要寻找的数的起始下标
            while (l < r) { // 在该数的右边进行二分
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) {
                    l = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            cout << r << endl;
        }
        else {
            cout << "-1 -1" << endl;
        }
    }
    
    
    return 0;
}

2. 数的3次方根

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

输入样例：

1
1000.00

输出样例：

1
10.000000

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    double x;
    cin >> x;
    
    double l = -10000, r = 10000;
    while (r - l > 1e-8) { // 浮点大小比较做差小于1e-8即可
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) {
            r = mid;
        }
        else {
            l = mid; // 因为是浮点数，无需+1
        }
    }
    
    printf("%lf", r);
    
    return 0;
}

3. 机器人跳跃问题

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 0 到 N 编号，从左到右排列。

编号为 0 的建筑高度为 0 个单位，编号为 ii 的建筑高度为 H(i) 个单位。

起初，机器人在编号为 0 的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1)的能量值。

游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 N。

第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

输入样例1：

1
2
5
3 4 3 2 4

输出样例1：

1
4

输入样例2：

1
2
3
4 4 4

输出样例2：

1
4

输入样例3：

1
2
3
1 6 4

输出样例3：

1
3

AC

E的取值从0~10000之间，二分查找

判断能量是否满足，只需要判断跳远后的能量是不是大于建筑的能量上限，若大于，则之后所有的能力值都满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int h[N];

bool check(int e) {
    for (int i = 1; i <= n; i++) {
        e = e * 2 - h[i];
        if (e >= 1e5) { // 若n大于建筑高度的最大值
            return true;
        }
        else if (e < 0) { // 若能量为负
            return false;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    
    int l = 0, r = 1e5;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    
    cout << r << endl;
    
    return 0;
}

4. 四平方和

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

比如：

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

0≤a≤b≤c≤d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入格式

输入一个正整数 N。

输出格式

输出4个非负整数，按从小到大排序，中间用空格分开。

数据范围

输入样例：

1
5

输出样例：

1
0 0 1 2

AC

暴力解会超时，所以利用结构体来做哈希表，存放所有的枚举可能性

结构体存 c、d 两个数，直接二重循环枚举 a、b 两个数，然后二分判断结构体下标，即对应的 c 、d 的平方和与 n - a a - b b 是否相等，从而减少时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 2500010;

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;
    }
}sum[N];

int main() {
    cin >> n;
    
    for (int c = 0; c * c <= n; c++) {
        for (int d = c; c * c + d * d <= n; d++) {
            sum[m++] = {c * c + d * d, c, d};
        }
    }
    
    sort(sum, sum + m);
    
    for (int a = 0; a * a <= n; a++) {
        for (int b = a; a * a + b * b <= n; b++) {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (sum[mid].s >= t) {
                    r = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            
            if (sum[l].s == t) {
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }
    
    return 0;
}

5. 分巧克力

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 ii 块是 Hi×Wi 的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足：

  1. 形状是正方形，边长是整数
  2. 大小相同

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

数据范围

输入样例：

1
2
3
2 10
6 5
5 6

输出样例：

1
2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100010;

int n, k;
int h[N], w[N];

bool check(int mid) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += (h[i] / mid) * (w[i] / mid); // 求第i块的巧克力的
        if (res >= k) {
            return true;
        }
    }
    
    return false;
}

int main() {
    cin >> n >> k;
    
    for (int i = 0; i < n; i++) {
        cin >> 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. 前缀和

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

数据范围

输入样例：

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

输出样例：

1
2
3
3
6
10

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

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

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { // 读入
        cin >> q[i];
    }
    
    for (int i = 1; i <= n; i++) { // 求前缀和
        s[i] = s[i - 1] + q[i]; // 第i项的前缀和 = 第i-1项的前缀和 + 第i项
    }
    
    while (m--) {
        int l, r;
        cin >> l >> r;
        
        cout << s[r] - s[l - 1] << endl;  // 打印 l~r 之间的和
    }
    
    return 0;
}

2. 子矩阵的和

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

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

数据范围

输入样例：

1
2
3
4
5
6
7
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

1
2
3
17
27
21

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, t;
int s[N][N];

int main() {
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> s[i][j];
        }
    }
    
    // 求对应子矩阵的和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i -1][j - 1];
        }
    }
    
    while (t--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl; // 如图所示
    }
    
    return 0;
}

3. 激光炸弹

地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

输入样例：

1
2
3
2 1
0 0 1
1 1 1

输出样例：

1
1

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5010;

int s[N][N];

int main() {
    int cnt, R;
    cin >> cnt >> R;
    R = min(5001, R); // 炸弹半径超过地图范围没什么意义
    
    int n = R, m = R; // 初始化目标范围边界
    while (cnt--) {
        int x, y, w;
        cin >> x >> y >> w;
        
        x++, y++; // 坐标+1，对应矩阵下标
        n = max(n, x), m = max(m, y); // 获取目标范围最大边界
        s[x][y] += w; // 因为不同目标可能在同一位置
    }
    
    // 预处理前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    
    int res = 0;
    
    // 枚举所有边长是R的矩形，枚举(i, j)为右下角
    for (int i = R; i <= n; i++) {
        for (int j = R; j <= m; j++) {
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]); // 取最大值，即总价值最大
        }
    }
    
    cout << res << endl;
    
    return 0;
}

4. K倍区间

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j][i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式

输出一个整数，代表 K 倍区间的数目。

数据范围

输入样例：

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

输出样例：

1
6

AC

核心：一段区间的和等于 s[i] - s[j]，若该区间是 K 的倍数，则 (s[i] - s[j]) % k == 0，将等式变形，即s[i] % k == s[j] % k。如果这段区间满足要求，即以这一段区间的左右下标对应的前缀和的余数应该相等。

由此，可以用哈希表来存对应余数的个数，但此题用一个计数数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL; // int长度不够

const int N = 1000010;

int n, k;
LL s[N], cnt[N];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) { // 构造前缀和
        cin >> s[i];
        s[i] += s[i - 1];
    }
    
    LL res = 0;
    cnt[0] = 1; // cnt[0]存的是s[]中等于0的数的个数，由于s[0] = 0，所以最初等于0的有1个数，所以cnt[0] = 1
    
    for (int i = 1; i <= n; i++) {
        res += cnt[s[i] % k]; // res等于前缀中出现过的和s[i]余k相等的计数之和并加上自己
        cnt[s[i] % k]++; // 将计数数组更新
    }
    
    cout << res << endl;
    
    return 0;
}