[学习笔记]二分与分治

二分

二分法常用来查找单调序列或单调函数上的答案．

当问题的答案具有单调性时，可以考虑通过二分求解．

先思考一个简单问题

A心里想一个1-1000之间的数，B来猜，B可以问问题，A只能回答是或者不是，怎么猜才能问的问题次数最小？

是1吗？是2吗?……平均要问500次
大于500吗?大于750吗?大于625吗?……每次缩小猜测范围到上次的一半，只需要10次($log_21000$)

这就是二分法的一个简单运用．

二分的实现方法有很多种，对于整数集合上的二分，需要注意终止边界，左右区间取舍时的开闭，避免漏掉答案或造成死循环；对于实数域上的二分，需要注意精度的取舍．

这里推荐大家采用＜算法进阶指南＞上的二分写法．

整数集合上的二分

下面代码摘自＜算法进阶指南＞P24 　亲测好用，比赛时一直采用这种二分写法．

在单调递增序列$a$中查找$\geq x $的数中最小的一个

  while(l<r){
      int mid = (l+r)>>1;/*右移运算 相当于除2并且向下取整*/
      if(a[mid]>=x) r=mid;
      else l=mid+1;
  }
  return a[l];

在单调递增序列$a$中查找$\leq x$的数中最大的一个

  while(l<r){
      int mid = (l+r+1)>>1;
      if(a[mid]<=x) l=mid;
      else r=mid-1;
  }
  return a[l];

注意，这里的单调是广义的单调，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种单调，比如把满足条件看做1 ，不满足看做 0．故这里的单调序列也可以换成单调函数，下面会详细解释．

使用上面代码的时候要注意考虑问题到底属于哪种情况．

上面模板二分结束条件恰好位于答案所处的位置，不需要再额外判断．希望同学们能采用这种写法，少走一些弯路．

先完成一个模板题

例题A:二分查找

STL的二分查找

对于一个有序的 array 你可以使用 std::lower_bound() 来找到第一个大于等于你的值的数， std::upper_bound() 来找到第一个大于你的值的数。

如：

int l = std::lower_bound(a+1,a+1+n,x)-a;
return a[l];

详细内容后面的讲座会详细介绍，这里不再赘述．

如果自学会了，可以尝试用STL解决例题A，巧用STL可以减少很多代码量．

实数域上的二分

有关实数的题一般都会给出精度要求，只要在题目允许的精度范围内就是对的．

所以需要确定好所需的精度$eps$，太小会超时，太大又不符合要求．

一般$eps$取1e-6或者1e-7　根据题目要求灵活变化

对于精度的问题，可以看这篇博客：https://www.cnblogs.com/oyking/p/3959905.html

while(l + 1e-6 <r){
    double mid=(l+r)/2;/*这里不能再用右移运算了*/
    if(calc(mid))r=mid;//一般运用于单调函数上
    else l=mid;
}

二分+check

二分的作用不只是查找某个值，在算法竞赛中二分常常与其他算法相结合．最广泛的用途还是解决单调函数的相关问题．

标题的check可以理解为函数，返回值为bool类型．（即0或者1）

0代表不符合条件，1代表符合条件．

当函数的返回值随着x的变化呈现单调性，如：0 0 0 0 0 1 1 1 这样的序列

可以采用二分解决．通过二分可以找出满足条件最小位置，像上面的序列答案就是6．

与单调函数一样有实数域和整数域之分：

例题B:木材加工

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定了。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。
木头长度的单位是厘米。原木的长度都是正整数，我们要求切割得到的小段木头的长度也要求是正整数。

#include <bits/stdc++.h>
const int maxn = 1e4 + 5;
int s[maxn], n, k;

bool check(int x) {
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res += s[i] / x;
        if (res >= k) return 1;
    }
    return 0;
}

int main() {
    scanf("%d%d", &n, &k);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        ans += s[i];
    }
    int r = ans / k;//上限
    int l = 0;
    while (l < r) {//相当于在1 1 1 0 0 0 这种序列找最大的1
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", l);
    return 0;
}

例题C: POJ1064

最大化最小值

在做题过程中如果有让最小值最大，让最大值最小这种问题

十有***需要二分．

什么叫最大化最小值问题呢？看下面的例题就知道了：

例题D:跳石头

http://icpc.upc.edu.cn/problem.php?id=1752

输入输出样例 1 说明：将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

另：对于 20%的数据,0 ≤ M ≤ N ≤ 10。对于50%的数据,0 ≤ M ≤ N ≤ 100。

对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。

令check(x):最小距离不小于x是否满足题意．

check(x)值大致为 1 1 1 0 0 0 故选取第二种二分方式

#include <bits/stdc++.h>
const int maxn = 5e4+10;
int s[maxn],n,m;
bool check(int k){
    int ans=0,last=0;
    for(int i=1;i<=n;++i){
        if(s[i]-s[last]>=k){
            last=i;
        }
        else ans++;
    }
    if(s[n+1]-s[last]<k) return 0;
    return ans<=m;
}
int main(){
    int l;
    std::cin>>l>>n>>m;
    for(int i=1;i<=n;++i){
        std::cin>>s[i];
    }
    s[n+1]=l;
    int L=0,R=l+10;
    while(L<R){
        int mid=(L+R+1)>>1;
        if(check(mid)){
            L=mid;
        }else{
            R=mid-1;
        }
    }
   std::cout<<l;
}

最大化平均值

有$n$个物品的重量和价值分别是$w_i$和$v_i$，从中选出$k$个物品使得单位重量价值最大。

假设我们选的物品集合为S，那么他们的单位重量价值为

\[\frac{\sum_{i\in S}{v_i}}{\sum_{i\in S}{w_i}} \]

我们是不是可以贪心地从大到小选取$\frac{v_i}{w_i}$最大的前k个呢

很明显不可以:

\[\frac{\sum_{i\in S}{v_i}}{\sum_{i\in S}{w_i}}\neq \sum_{i\in S} \frac{v_i}{w_i} \]

令check(x):可以选择使得单位重量的价值不小于x

\[\frac{\sum_{i\in S}{v_i}}{\sum_{i\in S}{w_i}} \geq x \]

很明显x越小越容易满足

现在就是怎么check的问题

所以我们转换一下

\[\sum_{i\in S}{v_i-x*w_i}\geq 0 \]

由(3)易得，我们可以对(3)进行排序贪心地选取．

因此变成

\[check(x)=(\sum_{i\in S}{v_i-x*w_i}从小到大前k个的\geq0) \]

因为平均值是浮点型，所以需要采用实数域上的二分

int n, k;
int w[550], v[550];
double y[550];

bool check(double x) {
    for (int i = 0; i < n; ++i) {
        y[i] = v[i] - x * w[i];
    }
    std::sort(y, y + n);
    double sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += y[n - i - 1];
    }
    return sum >= 0;
}
void erfen(){
    double l=0,r=1e6+10;
    while(l + 1e-6 <r){
        double mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    std::cout<<l<<std::endl;
}

分治

分治法通过将问题划分为规模最小的子问题，递归地解决划分后的子问题，再将结果合并从而高效地解决问题．

复杂度一般为$log$级别

分治法运用很多，有些问题比较复杂，这里只介绍数列上的分治．

分治算法可以分三步走：分解 -> 解决(触底) -> 合并(回溯)

分解原问题为结构相同的子问题。
分解到某个容易求解的边界之后，进行递归求解。
将子问题的解合并成原问题的解。

解决分治最重要的一点就是只要明确每个函数能做什么，千万不能试图跳进细节．不然脑子会炸的．

归并排序

归并排序是分治法最典型的运用．

两个有序数列合并的时间复杂度是O(n),n为数列长度大小.

将数列每次划分成两半，有log层

（下图是以后要学的重要数据结构　线段树）

所以总的时间复杂度是O(nlogn)

void Merge(int l, int mid, int r) {
    int i = l, j = mid + 1;
    for (int k = l; k <= r; ++k) {
        if (j > r || (i <= mid && a[i] < a[j])) b[k] = a[i++];
        else b[k] = a[j++];
    }
    for (int k = l; k <= r; ++k) a[k] = b[k];
}

void Sort(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    Sort(l, mid);
    Sort(mid + 1, r);
    Merge(l, mid, r);
}

归并排序的结构是：

void merge_sort(一个数组) {
  if (可以很容易处理) return;
  merge_sort(左半个数组);
  merge_sort(右半个数组);
  merge(左半个数组, 右半个数组);
}

分形

分形是一类很好玩的题，代码简单，但是需要一些思维量

要用到数学归纳的思想，并且需要找到一些规律．

在小范围考虑细节，大范围从整体上思考

例题：Windows Of CCPC

中国大学生程序设计竞赛简称CCPC
CCPC组委会设计了一个名为CCPC Windows的图标。图中的一级CCPC Windows如图所示：

二级CCPC窗口CCPC Windows如图所示：

我们可以清楚地看到，二级图可由四个一级图变化而来，左上，右上还有右下都是一个一级图，左下图是将一级图的'C'改成了'P', 'P'改成了'C'。
三级图也是这样由二级图得到的，四级图、五级图.....同理。
现在，请你输出第k级图的样子。

从细节上考虑：左下角的字符与其他都不同

从整体上考虑：若按照2的幂次划分，左下块的字符与其他都不同

#include <bits/stdc++.h>

int s[2000][2000];

void draw(int x, int y, int st1, int st2, int len) {
    if (len == 0) {
        s[x][y] = st1;
        return;
    }
    draw(x, y, st1, st2, len >> 1);
    draw(x, y + len, st1, st2, len >> 1);
    draw(x + len, y, st2, st1, len >> 1);
    draw(x + len, y + len, st1, st2, len >> 1);
}

int main() {
    int n, _;
    std::cin >> _;
    while (_--) {
        std::cin >> n;
        draw(1, 1, 1, 2, 1 << n);
        int len = 1 << n;
        for (int i = 1; i <= len; ++i) {
            for (int j = 1; j <= len; ++j) {
                if (s[i][j] == 1) {
                    std::cout << "C";
                } else {
                    std::cout << "P";
                }
            }
            std::cout << std::endl;
        }
    }
    return 0;
}

拓展题

题意：求$A^B$的所有约数之和mod9901

知识点：约数和定理[数论]
大于1的正整数：

\[\prod_{i=1}^kp_i^{c_i}=p_1^{c_1}*p_2^{c_2}*....p_k^{c_k} \]

正约数的个数：

\[\prod_{i=1}^k(c_i+1)=(c_1+1)*(c_2+1)*....*(c_k+1) \]

约数和：

\[\prod_{i=1}^k(\sum_{j=0}^{c_i}(p_i)^j)=(1+p^1+p^2+..+p^{c_1})*...*(1+p_k+p_k^2+..+p_k^{c_k}) \]

这题用到约数和　就是把$c_i*B$就好

先分解质因数求出$p_i$和$c_i$

约数和通过等比数列求和来做

等比数列求和可以通过分治递归的方法

将求和分成两部分：当n为偶数时

\[1+p^1+p^2+..p^{n/2-1}+p^{n/2}*(1+p^1+p^2+..+p^{n/2-1}）+p^{n/2} \]

\[\sum_{i=0}^{n/2-1}p^i+p^{n/2}*\sum_{i=0}^{n/2-1}p^i+p^{n/2} \]

每次递归之后　问题规模都会缩小一半　

#include <iostream>
#define ll long long
using namespace std;
const int mod=9901;
const int maxn=1e4;
ll p[maxn],c[maxn],pos;
ll qpow(ll a,ll n){//快速幂
    ll res=1;
    a%=mod;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
ll solve(ll k,ll n){//等比数列求和
        if(n==0) return 1;
        if(n&1){
            ll res=solve(k,n/2);
            return (res+res*qpow(k,n/2+1)%mod)%mod;
        }
        else{
            ll res=solve(k,n/2-1);
            return ((res+res*qpow(k,n/2)%mod)%mod+qpow(k,n))%mod;
        }
}
void divide(ll n){//分解质因数
    for(ll i=2;i*i<=n;++i){
        if(n%i==0){
            pos++;
            p[pos]=i;
            while(n%i==0)n/=i,c[pos]++;
        }
    }
    if(n>1) p[++pos]=n,c[pos]=1;
}
int main(){
    ll n,k,ans=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    divide(n);
    for(int i=1;i<=pos;++i){
        ans=ans*solve(p[i],c[i]*k)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

总结

二分与分治其实都算是一种思想，单纯的模板考题很少．

一般都是和其他知识组合在一块

本文中题目的参考代码尽量先自己思考之后再参考．

因为最近忙于一大堆事，写得比较仓促，忘谅解．

最后希望大家喜欢算法，爱上编程．

参考资料

［1］oi wiki https://oi-wiki.org/intro/icpc/

［2］算法（第四版）

［3］算法竞赛进阶指南

［4］挑战程序设计竞赛