基础算法 – YZircon's Blog

位运算

基础操作

字面意思，直接对数的二进制位进行操作，常与其它算法结合使用

目的	操作
移位	<<或>>，就是把原数的二进制表示像对应方向移动，丢掉的就没了(除2向下取整)，空出来就补零(乘2)
取n在二进制下的第k位	(n >> k) & 1，把第k位移到第一位，然后和1做&
取n在二进制下的0~k-1位	n & ((1 << k) – 1) ，(1<<k) – 1是一个k位全为1的数，前面全是0，把它和n按位与后前面的就丢掉了(和0与都是0)，剩下后面k位
取反n在二进制下的第k位	n xor (1 << k) ，1 << k的二进制是1后面k个0，即一个只有第k位为1的数，由于任何数异或0是不变的，故只有第k位被取反
把n在二进制下的第k位赋值为1	n \| (1 << k)，同上理，跟1或的结果就是1
把n在二进制下的第k位赋值为0	n & (~(1<<k)) ，同上理，跟0与的结果是0
取最低位1与其后面的0构成的数值(Lowbit)	n & (-n)，推理：先给n取反，那么最低位1变成了0，且后面全是1，给它+1，那么最低位1和它后面的所有位都变回了取反前的状态（进位），由于取过反，故只有最低位1与后面的0是跟n的二进制一样的，与起来就只剩下了这部分（前面全不一样，都变成0了）
成对变换	对于非负整数n，当n为偶数时，n xor 1 = n + 1，当n为奇数时，n xor 1 = n – 1，这一操作可以很方便的找到邻接表中相反边的存储位置（因为是连在一起存的，所以head的下标相邻，如果每次加的都是无向边，那么两条边还一定分别在2n和2n+1位置）

内置函数因为跟编译环境有关所以不讲了

Bitset

由于内存地址是按字节即 byte 寻址，而非比特 bit，一个 bool 类型的变量，虽然只能表示 0/1，但是也占了 1 byte 的内存。bitset就是通过优化使得一个byte 的8个 bit能储存8位0/1，这样就赚翻了

bitset<1000> bs;  // a bitset with 1000 bits

构造函数

bitset()：全部设为false

bitset(unsigned long val)：设为val的二进制表示

bitset(const string& str)：设为01串str

运算符

bitset只能和bitset位运算，如果要跟整型位运算，需要先将整型转换为bitset
能进行二进制移位操作
用[]访问某一位
==/!= 比较
可以用cin/cout输入输出

从OI Wiki扒下来的成员函数

count(): 返回 true 的数量。
size(): 返回 bitset 的大小。
test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。
any(): 若存在某一位是 true 则返回 true，否则返回 false。
none(): 若所有位都是 false 则返回 true，否则返回 false。
all():C++11，若所有位都是 true 则返回 true，否则返回 false。
1. set(): 将整个 bitset 设置成 true。
1. set(pos， val = true): 将某一位设置成 true/false。
1. reset(): 将整个 bitset 设置成 false。
1. reset(pos): 将某一位设置成 false。相当于 set(pos， false)。
1. flip(): 翻转每一位。（，相当于异或一个全是的 bitset）
1. flip(pos): 翻转某一位。
to_string(): 返回转换成的字符串表达。
to_ulong(): 返回转换成的 unsigned long 表达（long是多少跟操作系统有关）
to_ullong():C++11，返回转换成的 unsigned long long 表达。

被二分爆杀了，来贴个板子

while(l < r){//整数的,check(mid)为true时是动r还是l看要求的目标此时应该在哪边(因为二分要求单调,所以此时mid的一边一定都合法但不优,移动l或r的目的是让mid移到更优但不一定合法的那边),如果范围内不一定有答案循环结束后要再check(l),如果死循环了就把mid改成(l + r + 1) >> 1;
    int mid = (l + r) >> 1;
    if(check(mid)){
        r = mid;
    }else l = mid + 1;
}
while(fabs(l - r) > eps){//小数的,eps至少选择题目对精度的要求,但也不要选得过小不然可能会被卡得T掉
    double mid = (l + r) / 2.0;
    if(check(mid)){
        l = mid + eps;//加不加似乎无所谓
    }else r = mid;
}

三分

同二分一样，搞两个指针，只是mid变成了左右两个mid，用来求单峰/谷函数的极值，下面给出一点思路

如果f(lmid)<f(rmid)，则两个mid要么都在峰值左边，要么一边一个，但是峰值显然是在lmid右边的，所以可以把l跳到lmid
如果f(lmid) > f(rmid)，同理，把r跳到rmid
如果f(lmid) = f(rmid)，随便取一个即可，如果函数不严格单调（单调性相同的区域存在两个值相等的点），就无法判断怎么收缩边界，不能使用三分

排序

算法竞赛中，一般都会直接使用STL提供的sort和stable_sort函数进行排序，故下面只复习有必要手写的排序方法

快速排序

void qsort(int l,int r){
    int mid = a[(l + r) / 2];//这里是mid的值，因此下面要判断p,q有没有跑过mid这个位置
    int p = l,q = r;
    do{
        while(a[p] < mid) p++; //找到左边第一个非法的数
        while(a[q] > mid) q--; //找到右边第一个非法的数
        if(p <= q){//p,q没跑出对应的半区
            swap(a[p],a[q]);//交换
            p++;//找下一组
            q--;
        }
    }while(p <= q);//保证p,q两个指针不会指到对方半区
    if(l < q) qsort(l,q);//如果还没排完就递归进去排
    if(p < r) qsort(p,r);
}

归并排序

void Solve(int l,int r){
    if(r - l <= 1) return;//边界就是只剩一个数了，显然有序
    int mid = (l + r) / 2;
    Solve(l,mid);
    Solve(mid,r);
    int p = l,q = mid,s = l;//前面已经把[l,mid)和[mid,r)分别搞成有序的了，p是前半部分的第一个元素，q是后半部分的第一个元素
    while(s < r){
        if(p >= mid || (q < r && a[p] > a[q])){//如果前半部分空了或者前半部分有元素大于后半部分没用的的第一个元素，那就把它放到下一个
            t[s++] = a[q++];
            sum += mid - p;//逆序对个数其实就是选排里面的交换次数，归并只是把它一次完成了，不求逆序对不需要这个sum
        }else t[s++] = a[p++];
    }
    for(int i = l; i < r; ++i) a[i] = t[i];
}

离散化

可以用map，不想写了

$O(n)$第k大数

用快排的方式随机选一个基准数，把比它大的放到左边，它和比它小的放到右半边，然后统计出大于基准数/小于基准数的数的数目，由此容易推知第k大数在哪一半(比如小于基准数的数不止k个，那第k大肯定在右半边)，只进入这一半找就可以把复杂度变成$O(n)$

贪心

啥是贪心没啥讲的必要，讲讲证明贪心的手段~~大胆猜想，感性证明~~

微扰：证明在任意局面下，对局部最优策略的微小改变一定会导致整体结果变劣，通常用于贪心策略是排序的情况(比如，求一个全局最优的排列时采用比较相邻两个元素谁前谁后更优的方法排)
范围缩放：证明把局部最优策略用在更大范围时不会导致整体结果劣化
决策包容性：证明在局部选择最优决策不会影响后续决策的可能性
反证法和数学归纳法：没用过，不会

倍增

利用每个整数都能用二进制表示的特点简化状态空间，优化递推时间

以

ST表

为例，我们要维护区间的最值，最暴力的办法就是枚举所有的子区间，显然不可能有人放这种电子垃圾过去。我们能想到区间最值是可以进行二进制拆分的(可以进行二进制拆分指一个大范围下的答案可以由它的两半合并求得)，因此可以通过维护所有长度为2的次幂的区间最值保证对任意区间的查询都能找到。我们设$f[i][j]$为为从i开始的$2^j$个数中的最值，很容易就能得到状态转移方程$f[i][j] = max(f[i][j – 1],f[i + (1 << (j – 1))][j – 1])$（也就是把它从中分开，取左半[i,i + 2^(j – 1)]与右半[i + 2^(j – 1),i + 2^j]的区间最大值中大的那个)

void build_ST(){
    for(int i = 1; i <= n; i++) dp[i][0] = a[i];
    for(int j = 1; j <= 21; j++){
        for(int i = 1; i <= n - (1 << j) + 1; i++){
            dp[i][j] = max(dp[i][j - 1],dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l,int r){
    int tmp = log2(r - l + 1);
    return max(dp[l][tmp],dp[r - (1 << tmp) + 1][tmp]);
}

位运算