蓝桥杯专题备赛—二分

二分问题常用于求具有二段性的某一性质的边界值问题。

只要性质具有二段性或单调性，就可以尝试用二分。二分的复杂度为$O(logn)$，作为一种搜索方法常结合循环等使用。事实上，二分是一种优化暴力方法的常用方法，和暴力思路结合的很紧密。

一些最值问题其实就是性质的边界值问题，此时可以用二分求解。

二分的本质是，根据某一性质将区间左右一分为二，使一部分满足该性质，另一部分不满足该性质。

如果可以找到一个性质使区间左右一分为二（一部分满足，一部分不满足），二分就可以找到性质的边界。

二分问题要满足的条件：

  1. 确定一个区间，使得目标值一定在区间中

  2. 找一个性质，满足：

    • 性质具有二段性
    • 答案是二段性的分界点

整数二分

整数二分步骤

  1. 找一个区间[L, R]，使得答案一定在该区间中

  2. 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点

  3. 分析终点M在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案再哪个区间

    • 如果条件成立（性质满足）的区间在左部，则为<= x型，采用L=mid模板
    • 如果条件成立（性质满足）的区间在右部，则为<= x型，采用R=mid模板

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

整数二分的常见类型

问题形式角度

  1. 数据序列的二段性：问题中的数据序列具有单调性、二段性、适用于排序，在处理数据时进行二分

  2. 解（最值）的二段性：一般适用于最值问题，即求解给定条件下的最值。如果发现，针对题目的约束条件，以最值为边界点具有二段性（一段一定满足约束，一段不满足），即可使用二分对解进行搜索。数据的二段性只是将二段性直接变现出来了，其本质也是解（最值）的二段性。

常见特征词：求”最大值“、”最小值“、”平均值“的最大/最小值

二分重要性质：将假设的解作为已知条件，将问题转化为判定问题

  • 二分搜索解时，假设的解实际上可以作为已知条件进行使用。二分本质上可以让我们多一个条件（假设出解），将问题转化为判断问题（判断当前的解是否成立）。善用这一性质往往能极大化简问题！

二分性质角度

确定为二分问题后就要找到二段性，尽管问题的场景多种多样，但一般二段性只有两类：

两类二分

  • <= x类：check函数<= x时返回真，左半部分都是真，边界点属于左半部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 左半部分满足性质，如<=x的数
int bsearch_left(int l, int r){
    while (l < r){
        // 分界点在左半部分，如小于等于某个数的最大值
        int mid = l + r + 1 >> 1;
        //int mid = l + (r - l + 1) / 2; // 避免溢出问题
        // 当分界点在左半部分时，之所以$mid = \frac{l+r+1}{2}$多加一个1是为了避免mid = l导致更新时l = mid会不发生变化，陷入死循环（这种情况出现在l = r - 1时）。
        if (check(mid)) l = mid;
        // 成立时，对左端点更新且包含mid(分界点在成立区间得右端)
        else r = mid - 1;
        // 不成立时，对右端点更新，且不包含mid
    }
    return l;
    // 最终l==r，l和r都是答案，但mid不一定是答案
}

  • >= x类：check函数>=x时返回真，右半部分都是真，边界点属于右半部分

1
2
3
4
5
6
7
8
9
10
11
12
13
// 右半部分满足性质，如>=x的数
int bsearch_right(int l, int r){
    while (l < r){ // 区间长度大于等于1
        // 分界点在右半部分，如大于等于某个数的最小值
        int mid = l + r >> 1;
        //int mid = l + (r - l) / 2; // 避免溢出问题
        if (check(mid)) r = mid;
        // 成立时，对右端点更新且包含mid(分界点在成立区间得左端)
        else l = mid + 1;
    }
    return l;
    // 最终l==r，l和r都是答案，但mid不一定是答案
}

将二分问题都转化为这两类中的一种

判断函数的确定

二分最难的地方就在于 $ check $ 函数的写法，一般而言首先可以结合时间复杂度进行 $ check $ 函数的形式进行估计。由于二分的时间复杂度是O(logn) ，

  • 当$ n≤10^2 $，总时间复杂度要小于$ O( n^3 logn) $ ，$ check $ 函数中一般只能三重循环

  • 当$ n≤10^3 $，总时间复杂度要小于$ O( n^2 logn) $ ，$ check $ 函数中一般只能两重循环

  • 当$ n≤10^5 $，总时间复杂度要小于$ O( n logn) $，$ check $ 函数中一般只能一重循环

AcWing 730. 机器人跳跃问题

来源：今日头条2019，笔试题题型：二分、递归

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
// 二分 + 递推——AcWing 730. 机器人跳跃问题
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int h[N];

// 二分的主体代码往往相同，不同点在于check()函数
bool check(int e){
    for (int i = 1; i <= n; ++ i){
        e = e * 2 - h[i];
        if (e >= 1e5) return true;
        // 没有这一步会爆int
        // check()函数中能尽早判断出是否满足性质就要尽早
        // 因而要充分研究问题性质，用数学方法放缩出一些显然成立的情况，简化问题
        if (e < 0) return false;
    }
    return true;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &h[i]);

    int l = 0, r = 1e5;
    // 二分的一大关键点在于恰当地确定最初地区间端点

    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", r);
    return 0;
}

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
// 我最初用的暴力硬解的方法，十分不好
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010;

int n;
int h[N];

int main(){
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &h[i]);
    }
    
    int res = 0;
    double sum = 0;
    for (int i = 1;i <= 20 && i <= n; ++ i){
        sum = 2 * sum + h[i];
        res = max(res, (int)ceil(sum / (1 << i)));
        // printf("%f %f\n",sum, sum / (1 << i) + 0.5);
        
    }
    printf("%d\n", res);
    return 0;
}


AcWing 1227. 分巧克力

来源：2017年第八届蓝桥杯省赛C++A/B组题型：二分

本题的一个首先的关键也在于充分理解和挖掘题目性质

首先要明确如果确定对于给定大小的切除巧克力，原巧克力能切除多少块。不难发现满足以下公式：
$$
块数 = \lfloor\frac{H_i}{x} \rfloor*\lfloor \frac{W_i}{x}\rfloor
$$

同时进行数学建模，问题可表述为：
$$
max\ (巧克力大小) \\
s.t.\ \ 数量 >= k
$$

其次研究问题要求解的最值量是否具有二段性或单调性的性质，显然可以发现：能切出的巧克力数量随切除的巧克力大小具有单调递减的变化规律。总量不变时，巧克力越大，数量一定越少。存在一个临界值，满足数量 >= k，且巧克力最大。（注意这里不一定刚好切除数量为k，故约束条件是数量 >= k）。

不难发现，二分研究的性质往往就是约束量随目标量的变化关系，其具有二段性或单调性时，可用二分求解边界值（最值）。

check()的过程往往是一个循环或递推、具体求解问题的过程。

C++

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
// AcWing 1227. 分巧克力  
// 二分
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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);
        if (res >= k) return true; 
    }
    return false;
}

int main(){
    scanf("%d%d", &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;
    }

    printf("%d\n", r);
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# AcWing 1227. 分巧克力  
# 二分
def main():
    n, k = map(int, input().split())
    h, w = [0] * n, [0] * n
    for i in range(n):
        h[i], w[i] = map(int, input().split())
        
    def check(mid):
        cnt = 0
        for i in range(n):
            cnt += (h[i] // mid) * (w[i] // mid)
        return cnt >= k
    
    l, r = 0, max(h)
    while l < r:
        mid = l + r + 1 >> 1
        if check(mid): l = mid
        else: r = mid - 1
    print(r)
        
if __name__ == "__main__":
    main()

AcWing 1221. 四平方和

打表法化三重循环为两个二重循环，再利用搜索求解。

搜索方法可以采用二分法或数组模拟哈希

本题的一个关键问题时排序问题。指定固定排序的问题等价于组合问题。只需按照排序方式求解即可避免排序。

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
/// 打表法 + 二分——AcWing 1221. 四平方和 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

struct Sum{
    int s, c, d;
    // 有多个关键字的排序，按主关键字序排序
    bool operator< (const Sum &t)const{
        if (s != t.s) return s < t.s; // 一定注意 if 语句里要用!=不等号而不能用小于号
        if (c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];

int n, m;

int main(){
    scanf("%d", &n);

    for (int c = 0; c * c <= n; ++ c)
        for (int d = 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 = 0; 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;
}

AcWing 3176. 扫地机器人

难度：简单

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
// AcWing 3176. 扫地机器人
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010;

int n, k;
int s[N];

bool check(int t){
            int l = 0;
    for (int i = 0; i < k; i++)
    {
        if (s[i] - t <= l)
        {
            if (s[i] <= l)  l = s[i] + t - 1;
            else l += t;
        }
        else
            return false;
    }
    if (l >= n)
        return true;
    else
        return false;
}

int main()
{
    scanf("%d%d", &n , &k);

    for (int i = 0; i < k; ++ i)
        scanf("%d", &s[i]);
    
    sort(s, s + k);
    
    int l = 1, r = n;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", 2 * (l - 1));
    return 0;
}

AcWing 3153. 矩阵翻硬币

蓝桥云课链接：矩阵翻硬币 - 蓝桥云课

出处：2014年第五届蓝桥杯省赛JAVAB/C组难度：中等类型：数论（约数）二分

问题思路

本题难点在分析出主要问题。

最后，所有的硬币都是向上的，但是 “聪明” 的小 M 说了，如果再按照 Q 操作玩一次，就可以恢复原状，现在问原来有多少硬币是向下的。明确几点：
1. 从最后开始，先不管 P 操作究竟是怎么样的，只要某个硬币，被翻得次数是奇数次的，那么肯定要变成向下的。
2. 接下来请仔细看 P 操作，对 i × x 和 j × y，注意是 “所有的”，也就是说只要你这个 i*x 不超过最大的 n，那么所有可能的i都得取到。比如说现在最大的 n 是 20，x 现在是 2，那么 i 必须要取 2,3,4,5,6,7,8,9,10, 意思是所有在 n 范围内 x 的倍数都得取到。那么同理，所有在 m 范围内 y 的倍数也必须取到。
3. 明确了第二点，那么分析，对于某个点，假设坐标为（a，b），那么这个点被翻过的次数就是 a 的约数个数 × b 的约数个数。
4. 明确了第三点，那么想找到被翻过次数是奇数个的点，那么 a 和 b 的约数个数的乘积必须是是个奇数，如果 a 和 b 约数个数乘积必须是奇数，那么 a 和 b 他俩任何一个约数的个数都不能有 2，也就意味着，a 和 b 的约数个数都必须也是奇数乘出来才可能是奇数。
5. 明确了第四点，现在要寻找，什么样的数，才有奇数个约数呢？答案是——完全平方数！比如 0,4,9,16,25, 等等这些数字是完全平方数，也就是某个自然数的平方。那么也就是要求 a 和 b 都得是完全平方数。那么一个自然数，究竟包括了多少个完全平方数（不含 0，因为本题要求坐标从 1 开始），需要对这个数开方取整即可。比如 10，开方之后为 3. 几，意思是他包含了 3 个完全平方数，就是 1 4 9。
6. 最后，问题就转化成求 n 和 m 包括的完全平方数的个数再相乘，也就是根号 n 乘 根号 m 的结果，注意先取整再计算。

7. 可以采用给高精度开方，或者采用二分法寻找根。python 和 java 可直接使用高精度数！C++ 需继续搜寻为高精度开方的方法

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import os
import sys

n,m = map(int,input().split())
# 二分法开根
def sqrt(x):
  L = 1
  R = x
  while L < R:
    mid = L + R + 1 >> 1
    if mid ** 2 <= x:
      L = mid
    else:
      R = mid - 1
  return L

print(sqrt(n)*sqrt(m))

AcWing 2556. 第八大奇迹

出处：2019第十届蓝桥杯国赛C++B组难度：困难类型：树状数组 二分

题意

给定一个长度为 N 的序列 A，序列的初始值全为 0。现有 M 次操作，操作分为以下两种：

  • C x y 表示将 Ax 的值改为 y，即 $A[x]=y$

  • Q l r 询问区间 $Al,Al+1,…,Ar $的第八大的数值是多少（若不存在则输出 0）

分析

这显然是道动态区间第 k 大的问题，本题的 k=8，动态为单点修改。

处理动态区间第 k 大的问题，有两种常用方法：

  1. 树套树（树状数组套主席树 or 树状数组套平衡树）

  2. 整体二分

  • 树状数组套主席树： 前置知识：前缀和，树状数组（2014 年 B 组第 10 题，小朋友排队），主席树（可持久化权值线段树，2015 年 A 组 t10 灾后重建和 2017 年 A 组 t10 油漆面积都用到了线段树）。

  1. Q：如果是静态（即没有对序列的数进行修改）求整个序列的第 k 大怎么做呢？

    A：直接对序列 sort（从小到大） 一遍，那么 A[k] 即为所求时间复杂度 O(nlogn)，空间复杂度 O(n)。

  2. Q： 如果是动态（会对序列的数单点修改）求整个序列的第 k 大怎么做呢？

    A：开一棵权值线段树，树上每个位置的值表示这个位置对应的那个数在序列中有多少个，并向上维护和。

    查询时从树的根节点出发，先查询左子树和（记为sum），比较 k 和 sum 的大小关系：若 k≤sum 则说明第 k 小数在左子树中，递归查询左子树；否则，这个数对应的就是右子树中第 k−sum 小的数，令 k−=sum，然后递归查询右子树。

    时间复杂度 O(nlogn)，空间复杂度 O(n)。

  3. Q：如果是静态（即没有对序列的数进行修改）求某个区间的第 k 大怎么做呢？

    A：建立 n 棵前缀权值线段树，那么任意一段区间均可以用两棵权值线段树作差来表示，即区间 [L,R] 的信息可以由第 R 棵权值线段树 - 第 L 棵权值线段树得到。不过每个前缀开一棵权值线段树空间复杂度 O(n2)，无法开出这么大空间，而考虑到后一个位置相比于前一个位置的更改只有 logn 个节点，所以使用主席树来优化空间。

    时间复杂度 O(nlogn) 空间复杂度 O(nlogn)

  4. Q：如果是动态（有对序列的数进行修改）求某个区间的第 k 大怎么做呢（本题）？

    A：还是要想办法维护前缀和。

    我们需要去更新 $tree[x],tree[x+1],…,tree[n] $的信息。更新一个 tree 需要的时间复杂度 O(log)，而 x∼n 最坏有 n 个 tree 需要更新，那么更新的总时间复杂度为 O(nlog)，而这只是一次操作。而本题一共有 m 次操作，如果每次操作都是最坏的情况，那么时间复杂度为$ O(NMlogN)$ ，显然会超时。那有什么办法可以快速维护前缀信息呢？不难想到树状数组。

    通常树状数组是用来维护一个序列的，本题也类似，只不过原来的序列的每个元素都是一个数值，而本题的序列是由 n 棵主席树构成的序列，序列的每个元素都是一棵树。于是要修改 $tree[x],tree[x+1],…,tree[n] $只要 $log×log$ 的复杂度即可(第一个 log 是主席树的，第二个 log 是树状数组的)。

    总时间复杂度为 O(mlog2n)

  • 整体二分：

    前置知识：分治

    按操作的时间顺序排列各个操作，对于修改操作拆为删除和加入操作：

    1. 删除之前插入的数字

    2. 加入新的数字

    整体二分的做法是，对于每一个单独的询问，我们可以很容易设计一个 nlogn 的二分答案的算法，但是我们发现如果我们对每一个询问都这样处理的话会有很多重复的操作，于是我们考虑把所有询问一起二分。

    用 $solve(l,r,x,y)$ 表示 l 到 r 的询问所在的答案的区间为 [x,y]，然后我们每次根据 mid=2(x+y) 把所有的操作分成两份，左边是插入（删除）值小于 mid 的修改和询问，右边是大于 mid 的修改和询问，然后继续分治下去。其中修改我们需要用个数据结构来快速修改（比如树状数组 or 线段树），总时间复杂度为 O(nlog2n)。

解法一（树状数组套主席树）

树状数组套主席树 - OI Wiki

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
`#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , m ;
int a[N] ;
int lowbit(int x) { return x & (-x) ; }
struct Tree
{
    int up , cnt ;
    int lson[N * 100] , rson[N * 100] , sum[N * 100] ;
    int rt[N * 100] ;
     
    vector<int> vx , vy ;
    void init()
    {
        up = 1e9 , cnt = 0 ;
        memset(lson , 0 , sizeof lson);
        memset(rson , 0 , sizeof rson);
        memset(sum  , 0 , sizeof sum);
        memset(rt   , 0 , sizeof rt);
    }
    void update(int &now , int l , int r , int x , int y)
    {
        if(now == 0)  now = ++ cnt ;
        sum[now] += y ;
        if(l == r)  return ;
        int mid = (l + r) >> 1 ;
        if(x <= mid)  update(lson[now] , l , mid , x , y) ;
        else  update(rson[now] , mid + 1 , r , x , y) ;
    }
    void add(int i , int x , int y)
    {
        for(int j = i ; j <= n ; j += lowbit(j))
        update(rt[j] , 0 , up , x , y) ;
    }
    int query(int l , int r , int k)
    {
        if(l == r)  return l ;
        int num = 0 , mid = (l + r) >> 1 ;
        int sizx = vx.size() , sizy = vy.size() ;
        for(auto x : vx)  num -= sum[lson[x]] ;
        for(auto y : vy)  num += sum[lson[y]] ;
        if(k <= num)
        {        
            for(int i = 0 ; i < sizx ; i ++) vx[i] = lson[vx[i]] ;
            for(int i = 0 ; i < sizy ; i ++) vy[i] = lson[vy[i]] ;
            return query(l , mid , k) ;
        }
        else
        {
            for(int i = 0 ; i < sizx ; i ++)  vx[i] = rson[vx[i]] ;
            for(int i = 0 ; i < sizy ; i ++)  vy[i] = rson[vy[i]] ;
            return query(mid + 1 , r , k - num) ;
        }
    }
    int ask(int l , int r , int k)
    {
        vx.clear() , vy.clear();
        for(int j = l - 1 ; j >= 1 ; j -= lowbit(j))  vx.push_back(rt[j]) ;
        for(int j = r ; j >= 1 ; j -= lowbit(j))  vy.push_back(rt[j]) ;
        return query(0 , up , k);
    }
} tree ;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    cin >> n >> m;
    tree.init() ;
    for(int i = 1 ; i <= n ; i ++)  tree.add(i , a[i] , 1) ;
    while(m --)
    {
        char op;
        cin >> op;
        if(op == 'Q')
        {
            int l , r;
            cin >> l >> r;
            int k = r - l + 1 - 8 + 1; 
            if(k <= 0) 
            {
                cout << 0 << '\n';
                continue ;
            }
            int res = tree.ask(l , r , k);
            cout << res << '\n';
        }
        else
        {
            int x , y;
            cin >> x >> y;
            tree.add(x , a[x] , -1) ;
            a[x] = y ;
            tree.add(x , a[x] , 1) ;
        }
    }
    return 0 ;
}

解法二（整体二分）

整体二分 - OI Wiki

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
`#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int lowbit(int x) { return x & (-x) ; }
int n , m , tot = 1 , qid = 1;
struct Query
{
    int x , y , k , id , ch;
} q[N] , q1[N] , q2[N];
int a[N] , ans[N];
struct BIT
{
    int tree[N];
    int maxn;
    void init(int n)
    {
        memset(tree , 0 , sizeof tree);
        maxn = n;
    }
    void add(int pos , int val)
    {
        for(int i = pos ; i <= maxn ; i += lowbit(i))
        {
            tree[i] += val;
        }
    }
    int ask(int pos)
    {
        int ans = 0;
        for(int i = pos ; i ; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
} bit;

void solve(int ql,int qr,int l,int r)
{
    if(ql > qr) return ;
    if(l == r)
    {
        for(int i = ql ; i <= qr ; i ++) if(q[i].ch == 2) ans[q[i].id] = l;
        return ;
    }
    int mid = l + r >> 1;
    int L = 0 , R = 0;
    for(int i = ql ; i <= qr ; i ++)
    {
        if(q[i].ch == 1)
        {
            if(q[i].x <= mid)
            {
                bit.add(q[i].id , q[i].y);
                q1[L ++] = q[i];
            }
            else q2[R ++] = q[i];
        }
        else
        {
            int res = bit.ask(q[i].y) - bit.ask(q[i].x - 1);
            if(res >= q[i].k) q1[L ++] = q[i];
            else q[i].k -= res , q2[R ++] = q[i];
        }
    }
    for(int i = 0 ; i < L ; i ++) if(q1[i].ch == 1) bit.add(q1[i].id, -q1[i].y);
    int now = ql;
    for(int i = 0 ; i < L ; i ++) q[now ++] = q1[i];
    for(int i = 0 ; i < R ; i ++) q[now ++] = q2[i];
    solve(ql , ql + L - 1 , l , mid);
    solve(ql + L , ql + L + R - 1 , mid + 1 , r);
}
signed main()
{
    cin >> n >> m;
    bit.init(n);
    for(int i = 1 ; i <= n ; i ++) q[tot ++] = Query{0 , 1 , 0 , i , 1};
    for(int i = 1 ; i <= m ; i ++)
    {
        char op;
        cin >> op;
        if(op == 'Q')
        {
            int l , r;
            cin >> l >> r;
            int k = r - l + 1 - 8 + 1;
            q[tot++]=Query {l,r,k,qid++,2};
        }
        else
        {
            int x , y;
            cin >> x >> y;
            q[tot ++] = Query{a[x] , -1 , 0 , x , 1};
            a[x] = y;
            q[tot ++] = Query{a[x] , 1 , 0 , x , 1};
        }
    }
    solve(1 , tot - 1 , 0 , 1e9);
    for(int i = 1 ; i < qid ; i ++) cout << ans[i] << '\n';
    return 0;
}

AcWing 519. 跳石头

蓝桥云课链接：跳石头 - 蓝桥云课 (lanqiao.cn)
出处：NOIP2015提高组难度：中等类型：二分+贪心， $O(NlogL)$

问题分析

本题属于二分的标准套路题：最大值最小化，最小值最大化，属于解（最值）的二分。

二段性：如果长度 $Len$ 可以满足，那么当长度小于 $Len$ 时也可以满足，所以我们可以二分出最大的 $Len$。

判定函数确定——贪心策略

本题$ check $ 函数还是稍微要思考一下的。主要还是要把思路从判定问题转变为判定问题来处理。

$check$函数返回真的限制条件是：

  • 至多移走$M$个石头

  • 剩下石头间距离大于等于$Len$

需注意，这里不要被至多移走m个石头所困惑，把问题想的过于复杂。实际上，由于现在是判定问题而不是求解问题，我们不需要从所有约束条件出发去推可行解，完全可以一个一个约束地处理，或从先满足一个约束来推出解，再看其是否满足其他约束。总之，判定问题的思路要灵活！

本题中剩下的问题是如何判断给定 $Len$ 的情况下，能否最多拿走 $M$ 块石头，使得所有相邻两块石头之间的距离不小于 $Len$。

这一步可以贪心来做。从前往后扫描，并记一下上一块石头的位置。

  • 如果当前石头和上一块石头的距离小于 $Len$，则将当前石头拿走。

    这里给出证明：如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。

  • 如果当前石头和上一块石头的距离大于等于 $Len$，则将上一块石头更新成当前这块。

扫描结束后判断拿走的石头数量是否小于等于 $M$。

时间复杂度分析

总共二分 $O(logL)$ 次，每次贪心的计算是 $O(N)$，因此总时间复杂度是 $O(NlogL)$

C++

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
// AcWing 519. 跳石头
// 二分 + 贪心
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;

int L, n, m;
int d[N];

bool check(int mid)
{
    int last = 0, cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (d[i] - last < mid) cnt ++ ;
        else last = d[i];
    return cnt <= m;
}

int main()
{
    scanf("%d%d%d", &L, &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &d[i]);
    d[ ++ n] = L;

    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);
    return 0;
}

Python

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
# AcWing 519. 跳石头
# 二分 + 贪心
def main():
    l, n, m = map(int, input().split())
    d = [int(input()) for _ in range(n)]
    # 易错点：别忘了中间最后一个岩石和终点岩石的距离也要大于等于len
    # 所以要把最后一个岩石也加入距离序列
    d.append(l)
    
    def check(mid):
        cnt = 0 # 移动岩石数
        last= 0 # 当前位置到起点距离
        # 易错点：初始位置是在起点，距离为0而不是d[0]
        for i in range(n + 1):
            # 如果当前位置岩石与下个岩石距离小于mid，就取走下一个岩石
            if d[i] - last < mid:
                cnt += 1
            # 否则更新当前位置，跳到下个岩石上
            else:
                last = d[i]
        # 是否满足数量限制
        return cnt <= m
    
    l, r = 0, max(d)
    # >= x型，左模板
    while l < r:
        mid = l + r + 1 >> 1
        if check(mid):
            l = mid
        else:
            r = mid - 1
    print(r)
    
if __name__ == "__main__":
    main()

AcWing 1460. 我在哪？（每日一题）

本题的本质时确定一个最小长度k，使任意长度为k的子串都互不相同。

直接暴搜的话是四重循环，复杂度为$ O(n^4) $，其实可以过。

我在哪

优化

  • 二分优化：对于最外层循环，可以使用二分进行优化。本题显然具有二段性，只要长度大于等于ans，子串就一定互不相同。

  • 哈希：对于分别枚举任意两个子串进行比较的循环，可以通过哈希打表记录出现次数，用空间换时间。

  • 字符串哈希

C++

string.substr(start<,length>)
start:从string 的start位置开始提取字符串
length:待提取的字符串的长度，若length为一下情况时，返回整个字符串的所有字符。

iterator **find** (const key_type& k);
在容器中搜索键值等于 k 的元素，如果找到，则返回一个指向该元素的迭代器，否则返回一个指向unordered_map :: end的迭代器。

二分 + 哈希，时间复杂度为$O(n^2 logn)$

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
// AcWing 1460. 我在哪？（每日一题）
// 二分 + 哈希
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int N = 110;

int n;
string s;

bool check(int k){
    // unordered_map<string, bool> hash;
    unordered_set<string> hash;
    
    for (int i = 0; i + k - 1 < n; ++ i){
        string t = s.substr(i, k);
        // if (hash.find(t) == hash.end()) m[t] = true;
        // else return false;
        
        if (hash.count(t)) return false; 
        else hash.insert(t); // 复杂度为O(n)
    }
    return true;
}

int main(){
    scanf("%d", &n);
    cin >> s;
    
    int l = 1, r = n;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

二分 + 字符串哈希，时间复杂度为$O(nlogn)$

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
// AcWing 1460. 我在哪？（每日一题）
// 二分 + 字符串哈希
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef unsigned long long ULL;

const int N = 103, P = 131;

int n;
string s;
ULL hs[N], p[N];

ULL get(int l, int r){
    return hs[r] - hs[l - 1] * p[r - l + 1];
}

bool check(int k){
    unordered_set<int> hash;
    for (int i = 0; i + k - 1 < n; ++ i){
        int t = get(i + 1, i + k); // 注意字符串哈希下表下标从1开始，所以这里要加1
        
        if (hash.count(t)) return false;
        else hash.insert(t);
    }
    return true;
}

int main(){
    scanf("%d", &n);
    cin >> s;
    
    p[0] = 1;
    for (int i = 1; i <= n; ++ i){
        p[i] = p[i - 1] * P;
        hs[i] = hs[i - 1] * P + s[i - 1];
    }
    
    int l = 1, r = n;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

Python

集合/哈希

判断字符串是否在集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# AcWing 1460. 我在哪？（每日一题）
# 暴力 + 集合/哈希
def main():
    n = int(input())
    s = input()
    k, hs = 1, set()
    for l in range(1, n + 1): # 枚举长度
        flag = True
        for i in range(n - l + 1):
            tmp = s[i:i+l] # 注意切片:后要是末端下标+1
            if tmp in hs: # 判断字符串是否在集合中
                k = l + 1
                flag = False
                break
            else:
                hs.add(tmp)
        if flag:
            return print(k)
    
if __name__ == "__main__":
    main()

二分 + 集合/哈希

这里使用了一种非常巧妙的方法：不用注意判断子串是否在集合中，直接将所有子串放到集合中，如果没有相同的，则集合中元素数量等于n-k+1，k为子串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# AcWing 1460. 我在哪？（每日一题）
# 二分 + 集合/哈希
def main():
    n = int(input())
    s = input()
    l, r, hs = 1, n, set()
    while l < r:
        mid = l + r >> 1
        # 集合中元素数量等于n-mid+1，说明所有元素互不相同，没有重复子串
        if len(set([s[i:i+mid] for i in range(n - mid + 1)])) == n - mid + 1:
            r = mid
        else:
            l = mid + 1
    print(l)
    
if __name__ == "__main__":
    main()

二分 + 字符串哈希

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
# AcWing 1460. 我在哪？（每日一题）
# 二分 + 字符串哈希
def main():
    n = int(input())
    s = input()
    P, MOD = 131, 2 << 64 - 1
    hs, bs = [0] * (n + 1), [1] * (n + 1) # 注意下标从1开始，需要多开一位
    l, r, hash = 1, n, set()
    
    for i in range(1, n + 1): # 注意下标从1开始，需要多开一位
        bs[i] = (bs[i - 1] * P) % MOD
        hs[i] = (hs[i - 1] * P + ord(s[i - 1])) % MOD
        
    def check(mid):
        for i in range(n - mid + 1):
            l, r = i + 1, i + mid
            # 求字符串哈希值
            v = (hs[r] - hs[l - 1] * bs[r - l + 1]) % MOD
            if v in hash:
                return False
            else:
                hash.add(v)
        return True

    while l < r:
        mid = l + r >> 1
        if check(mid):
            r = mid
        else:
            l = mid + 1
    print(l)
    
if __name__ == "__main__":
    main()

123 - 蓝桥云课

出处：蓝桥杯2021国赛难度：中等类型：二分

善于观察形式特点和性质

双重求和，第一层求和为等差数列公式求和，第二层求和为前缀和求和

确定第i个数所在的区间使用了二分法由
$$
\sum n^2 = 1^2 + 2^2 + 3^2+ \ldots + n^2 = \frac{ n *(n+1) * (2n+1) }{6}
$$
得，

$$
\begin{align}
\sum n * (n+1) & = \sum ( n^2 + n ) \\
& = \frac{ n * (n+1) * (2n+1) }{6} + \frac{ n* (n+1) }{2} \\
& = \frac{ n * (n+1) * (2n+4) }{6} \\
& = \frac{ n * (n+1) * (n+2) }{3} \\
\end{align}
$$

数列中的每一个连续的部分可以看作一个小区间。

每一个小区间都是一个 $ a_1 = 1$， $d=1 $ 的等差数列，且区间的长度也能构成等差数列。

由于$ l, r \leq 1012 $ ，即
$$
2(1+n) \times n \geq 10^{12}
$$
所以最多有 1414214 个小区间构成该数列，满足任意 l，r 都能落在里面。

这意味着虽然我们不能直接查询某一位置的前缀和，但可以通过这些小区间来定位和计算某一位置的前缀和。

  • 第 i 个区间的元素个数为 i。

  • 定义 a[i] 表示前 i 个小区间的元素个数（1 ~ n 的和）。则有：$ a[i] = a[i−1] + i $

  • 定义 s[i] 表示前 i 个小区间的和。则有：$ s[i] = s[i−1] + a[i]$

  • 对于数列中任意位置 i ，一定存在一个最大的j满足 $ a[j] \leq i $，这表示第i个数落在第 j+1 区间内。

  • 对于数列中任意位置 i，当它落在第 j+1 个区间，它是该区间第k个数，则它在数列中的前缀和为：$ s[j] + a[k] $，其中 $ k = i − a[j] $。

时间复杂度：$O(C+T×logC)$，C=1414215 是常数。
空间复杂度：$O ( C ) $

C++

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
// 前缀和 + 二分 + 等差求和公式
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=3e6+10;


ll sum[N];
int t;

ll get(int n){ // 等差数列前n的和
    return 1ll * n * (n+1) / 2;
    // 公式法求解复杂度最小
}

ll solve(ll x){ // 求解区间[1, x]的元素和
    if(x == 0) return 0;
    ll res=0;

    int l = 1,r = N-10; // 二分法搜索
    while(l < r){
        int mid=l + r + 1 >> 1;
        if(get(mid) <= x) l = mid;
        else r = mid - 1;
    }

    res += sum[l];
    int n = x-get(l);
    res += get(n);
    return res;
}

int main()
{
    for(int i=1;i<N;i++){
        sum[i]=get(i);
        sum[i]+=sum[i-1];
        // 求解区间[1, x]的元素和
        // 前缀和的思想
    }
    cin>>t;
    while(t--){
        ll l,r;scanf("%lld %lld",&l,&r);
        ll res=solve(r)-solve(l-1);
        // 前缀和
        printf("%lld\n",res);
    }
}

Python

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
# 123 - 蓝桥云课
# 二分 + 求和公式
import os
import sys

def main():
  def getp(x): return x*(x+1) // 2
  def gets(x): return x*(x+1)*(x+2) // 6
  
  def search(x):
    l, r = 1, int(2e6+1)
    while l < r:
      mid = r + l >> 1
      if getp(mid) >= x: r = mid
      else: l = mid + 1
    return l, x - getp(l-1)
  
  T = int(input())
  for _ in range(T):
    L, R = map(int, input().split())
    pl, nl = search(L-1)
    pr, nr = search(R)
    print(gets(pr - 1) + getp(nr) - gets(pl - 1) - getp(nl))

if __name__ == "__main__":
  main()

区间移位 - 蓝桥云课

出处：蓝桥杯2017国赛难度：困难类型：二分 枚举

问题分析

本题是典型的二分套路题：最大值最小化

区间移位

uid1787145-20220327-1648372878604

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 <bits/stdc++.h>
using namespace std;
const int maxn = 20000;
int n;
struct node
{
	int a;
	int b;
};
vector<node> reg;
bool cmp(node x,node y){
	return x.b < y.b;
}
bool check(int x){
	int k = 0;
	vector<node> tmp(reg);
	while(true){
		bool found = false;
		for(int i = 0; i < tmp.size(); i++){
			node now = tmp[i];
			int ta = now.a;
			int tb = now.b;
			if (ta - x <= k && tb + x >= k){
				found = true;
				int len = tb-ta;
				// if(ta+x>=k) k += len;
				// else k = tb+x;
        			k += min(len, tb + x - k);
				tmp.erase(tmp.begin()+i);
				break;
			}
		}
		if(!found || k>=maxn) break;
	}
	return k >= maxn;
}
int main()
{
	scanf("%d",&n);
	for(int i = 0; i < n;i++){
		int a, b;
		scanf("%d%d",&a,&b);
		a *= 2;
		b *= 2;
		reg.push_back({a, b});
	}
	sort(reg.begin(),reg.end(),cmp);
	int l = 0, r = maxn;
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) 
         	r = mid;
		else 
            l = mid + 1;
	}
    double ans = r / 2.0;
    cout << ans << endl;
	return 0;
}

Python

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
import os
import sys

def main():
  n = int(input())
  
  q = sorted([[int(x) * 2 for x in input().split()] for _ in range(n)], 
  key = lambda x: (x[1]))

  def check(mid):
    s = 0
    cq = q.copy()
    while True:
      flag = False
      for x in cq:
        l, r = x[0], x[1]
        if l - mid <= s <= r + mid:
          s += min(r -  l, r + mid - s)
          # if  q[i][0] + mid >= s:
          #   s += q[i][1] -  q[i][0] 
          # else:
          #   s = q[i][1] + mid
          flag = True
          cq.remove(x)
          break 
      if not flag or s >= 2e4: return s >= 2e4

  l, r = 0, int(2e4)
  while l < r:
    mid = l + r >> 1 
    if check(mid): 
      r = mid
    else: 
      l = mid + 1
  print(l / 2 if l % 2 != 0 else l // 2)
  
if __name__ == "__main__":
  main()
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
import os
import sys

def main():
  n = int(input())
  
  q = sorted([list(map(int, input().split())) for _ in range(n)], 
  key = lambda x: (x[1]))

  def check(mid):
    s = 0
    cq = q.copy()
    while True:
      flag = False
      for x in cq:
        l, r = x[0], x[1]
        if l - mid <= s <= r + mid:
          s += min(r - l, r + mid - s)
          # if  q[i][0] + mid >= s:
          #   s += q[i][1] -  q[i][0] 
          # else:
          #   s = q[i][1] + mid
          flag = True
          cq.remove(x)
          break 
      if not flag or s >= 1e4: return s >= 1e4

  l, r = 0, 1e4
  eps = 1e-3
  while r - l > eps:
    mid = (l + r)/2
    if check(mid): 
      r = mid
    else: 
      l = mid
  x = (l + r) / 2
  if abs(round(x)-x)<0.05:
    print(round(x))
  else:
    print(int(round(x*10))/10)
  
if __name__ == "__main__":
  main()