第一讲 基础算法
快速排序
void quick_sort(int q[],int l,int r){
if(l>=r)return;
int x=q[l+r>>1],i=l-1,j=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);
}
归并排序(及求逆序对)
long long merge_sort(int q[],int l,int r){
if(l>=r)return 0;
long long res=0;
int mid=l+r>>1;
res+=merge_sort(q,l,mid);
res+=merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]>q[j]){tmp[k++]=q[j++];res+=(mid-i+1);}
else tmp[k++]=q[i++];
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
return res;
}
二分
整数二分
情况一:将区间分为 $[l,mid-1]$ 与 $[mid,r]$,即找左边最右的
int search(int l,int r){
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
return l;
}
情况二:将区间分为 $[l,mid]$ 与 $[mid+1,r]$,即找右边最左的
int search(int l,int r){
while(l<r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
return l;
}
小数二分
double search(double l,double r){
while(r-l>eps){
double mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
return l;
}
三分
整数三分
int l = 1,r = 100;
while(l < r) {
int lmid = l + (r - l) / 3;
int rmid = r - (r - l) / 3;
lans = f(lmid),rans = f(rmid);
// 求凹函数的极小值
if(lans <= rans) r = rmid - 1;
else l = lmid + 1;
// 求凸函数的极大值
if(lasn >= rans) l = lmid + 1;
else r = rmid - 1;
}
// 求凹函数的极小值
cout << min(lans,rans) << endl;
// 求凸函数的极大值
cout << max(lans,rans) << endl;
小数三分
const double EPS = 1e-9;
while(r - l < EPS) {
double lmid = l + (r - l) / 3;
double rmid = r - (r - l) / 3;
lans = f(lmid),rans = f(rmid);
// 求凹函数的极小值
if(lans <= rans) r = rmid;
else l = lmid;
// 求凸函数的极大值
if(lans >= rans) l = lmid;
else r = rmid;
}
// 输出 l 或 r 都可
cout << l << endl;
高精度
高精 $+$ 高精
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
高精 $-$ 高精
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精 $×$ 低精
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精 $÷$ 低精
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
前缀和与差分
一维
S[i] = a[1] + a[2] + ... + a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
给区间[l, r]中的每个数加上c:b[l] += c, b[r + 1] -= c
二维
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
b[x1, y1] += c, b[x2 + 1, y1] -= c, b[x1, y2 + 1] -= c, b[x2 + 1, y2 + 1] += c
位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n
离散化
保序
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}
不保序
//开放寻址法
int h[N];
//如果x在哈希表中,返回 x 的下标;如果 x 不在哈希表中,返回 x 应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}