算法竞赛实用板子

一、声明

        自用版参考acwing，致力于实用、好用，板子中有个人理解，持续更新。

二、开板

---

        1.快排

void quick_sort(int q[],int l,int r)
{if(l>=r)return;              //出口int i=l-1,j=r+1,x=q[l+r>>1]; //分治方法while(i<j){do i++;while(q[i]<x);do j--;while(q[j]>x);if(i<j)swap(q[i],q[j]);}quick_sort(q,l,j);           //递归实现   quick_sort(q,j+1,r);
}

        2.差分

for(int i=1;i<=n;i++)b[i] = a[i] - a[i - 1];   //区别于前缀和/*  1 2 3  -->  1 1 1  */ b[l] += c;     b[r + 1] -= c;

         3.二分

int bin(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;     //注意两种形式，下-1 上+1  if (check(mid)) l = mid;                       else r = mid - 1;             //             下+1 上}                                 return l;                         //             return any
}

         4.分数取模（快速幂）

        主函数中（可实现 求解 (a / b) % M  ）：

ll ans = a * ksm(b, M - 2) % M;

        定义快速幂函数： 

ll ksm(ll a, ll b){ll res = 1;while(b) {if(b & 1)                    // 如果当前b的二进制数字为1，即存在res = res * a % M;       // 结果乘上当前aa = a * a % M;               // 下一位的a的值（开平方）b >>= 1;                     // b的下一位二进制数}return res;
}

 具体原理讲解可参考：C++分数取模【固定模板+讲解】

---

to be continued !