知识汇总-基本算法

位运算,递推与递归,前缀和与差分,二分,排序,倍增,贪心

位运算

移位运算

  • 快速幂,快速乘(1e18),状态压缩,成对变换,lowbit。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //快速乘
    ll mul(ll a,ll b,ll p){
    ll ans=0;
    while(b){
    if(b&1) a=(ans+a)%p;
    a=a*2%p;
    b>>=1;
    }
    return ans;
    }

递推与递归

  • 递推:以已知的“问题边界”为起点向“原问题”正向推导
  • 递归:以“原问题”为起点尝试寻找把状态空间缩小到已知的“问题边界”的路线,再通过路线反向回溯

前缀和与差分

  • 前缀和:s[i]=∑(a[1]~a[i])
  • 差分:b[i]=a[i]-a[i-1]。前缀和与差分为互逆运算,b的前缀和序列就是a,可将原序列上的区间操作转化为差分序列上的单点操作。

二分

  • 整数域:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //1 大的可以则小的可以
    while(l<r){
    int mid=(l+r)>>1;
    if(check(mid)) r=mid;
    else l=mid+1;
    }
    //2 小的可以则大的可以
    while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid)) r=mid-1;
    else l=mid;
    }
  • 实数域:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(l+1e-5<r){
    double mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid;
    }
    //当精度不容易确定或表示时,可采用固定循环次数的方法,这种方法得到的精度通常更高
    for(int i=0;i<100;i++){
    double mid=(l+r)/2;
    if(check(mid)) r=mid;
    else l=mid;
    }
  • 三分:有一类函数被称为单峰函数,它们拥有唯一的极大值点,在极大值左侧严格单点上升,右侧严格单调下降;或者唯一的极小值点,左侧严格单调下降,右侧严格单调上升。可用三分法求极值。
    • 在函数域[l,r]上任取两点lmid和rmid
    • 若f(lmid) < f(rmid),则lmid与rmid要么同时处于极大值左侧,要么两侧,无论如何,极大值一定在lmid右侧,令l=lmid
    • 同理,若f(lmid)>f(rmid),令r=mid。
      如果函数不严格单调,即在韩式中存在一段值相等的部分,就无法判断定义域的左右边界如何缩小,三分法不再适用。
  • 二分答案:在答案与原问题具有单调性时,对答案进行二分,然后每次进行check()。

排序

  • 离散化:sort+unique,将数值较大但分散的数映射为有限集合以便于统计。
  • 中位数:我们要在一个一维序列上找一个点,使得其他点到它的距离之和最小时,中位数即为答案。证明:把序列排序,选择第x个点,则x左侧有P个点,右侧有Q个点。若P < Q,则每把x向右移动一个单位距离,距离之和就会变小Q-p;同理,若P > Q,则没把x向左移动会使距离和变小,当P=Q时为最优解。即:∑|s[i]-s[k]|,找到一个s[k]使式子最小,这个s[k]就是s的中位数。
  • 第k大数:给定区间,求第k大。排序至少O(nlgn)。利用快排的思想,在每次选取基准值后,统计出大于基准值的数量cnt,如果k<=cnt,则去左边找,否则在右边找第k-cnt大,时间复杂度为O(n)
  • 逆序对:利用归并排序进行求解。区间[l,r]中,mid=(l+r)/2,i从l到mid,j从mid+1到r,当a[i]>a[j]的时候,a[i~mid]一定都大于a[j],因为单独看左右区间是已经排好序的,sum+=mid-i+1即可。

倍增

  • 当通常的线性递推无法满足时间和空间复杂度的要求时,就可以通过成倍增长的方式,只递推状态空间在2的整数次幂上的值作为代表。当需要其他位置上的值时,我们可以通过“任意整数可以表示为若干个2的次幂项的和”这一性质,使用之前求出的代表值拼成想要的值。这个算法要求我们递推的问题的状态空间关于2的次幂具有可划分性
    • 试想这样一个问题:给出长为N的数列,每次给出一个T,求最大的整数k使得∑(a[1]~a[k])<=T.
    • 常规做法两种,第一种是直接O(n)扫过去,显然效率很慢;第二种是O(n)预处理出前缀和,然后二分k,每次询问O(lgn)。第二种在平均情况下表现很好,但是假如每次给的T都很小,那么k一定也很小,那么此时二分可能还不如直接扫过去来的快。
    • 我们可以设计这样一种倍增算法:
      • 令p=1,k=0,sum=0,预处理处前缀和S;
      • 比较A数组中k之后p个数的和与T的关系。如果sum+S[k+p]-S[k]<=T,则令sum+=S[k+p]-S[k],k+=p,p*=2,即加上这p个数的和,然后把跨度增长一倍。如果sum+S[k+p]-S[k]>T,则令p/=2.
      • 重复上诉步骤,知道p的值为0,此时k就是答案
  • ST算法:利用倍增求RMQ问题以及树上倍增求LCA。

贪心

  • 贪心法要求问题的整体最优性可以有局部最优性推导出,且需要证明,常见的证明方法有:
    • 微扰(邻项交换):证明在任意局面下,任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以排序为贪心策略的证明。例题:国王游戏
    • 范围缩放:证明任何对局部最优策略作用范围的扩展不会造成整体结果变差。
      例题:雷达设备
    • 决策包容性:证明在任意局面下,作出局部最优决策以后,在问题状态空间中的可达集合包含了作出其他决策后的可达集合。换言之,这个局部最优策略提供的可能性包含其他所有策略提供的可能。
    • 反证法。
    • 数学归纳法。
Donate comment here