算法基础课 (一) 基础算法

进制转换

#include<iostream>
using namespace std;
const int N = 100;
int n,m;
string s;
int x;//记录n进制转化成十进制;
int ans[N];
int main(){cin>>n>>s>>m;int t=1;for(int i=s.size()-1;i>=0;i--){if(s[i]<'A'){x += t*(int)(s[i]-'0');t *= n; }else{x += t*(int)(s[i]-'A'+10);t *= n;}}int st = 0;while(x){ans[st++] = (x%m);x /= m;}for(int i=st-1;i>=0;i--){if(ans[i]>=10)  printf("%c",(char)(ans[i]-10+'A'));else printf("%d",ans[i]);}  return 0;
}

quick_sort

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);
}

​

边界问题 :

因为边界问题只有这两种组合，不能随意搭配；

x不能取q[l]和q[l+r>>1];
quick_sort(q,l,i-1),quick_sort(q,i,r);x不能取q[r]和q[(l+r+1)>>1];
quick_sort(q,l,j),quick_sort(q,j+1,r);

​

merge_sort

void merge_sort(int q[], int l, int r)
{//递归的终止情况if (l >= r) return;//第一步：分成子问题int mid = l + r >> 1;//第二步：递归处理子问题merge_sort(q, l, mid);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[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];//第四步：复制回原数组for (i = l, j = 0; i <= r; i ++, j ++ ) q[i]=tmp[j];
}

​

整数二分

• 对于lower_bound : >= x的第一个元素的位置

• 对于upper_bound : >x的第一个元素的位置

模板 :

bool check(int x) {/* ... */} // 检查x是否满足某种性质
​
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r){while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid; // check()判断mid是否满足性质else l = mid + 1;//左加右减}return l;
}
​
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;//如果下方else后面是l则这里加1if (check(mid)) l = mid;else r = mid - 1;//左加右减}return l;
}

浮点数二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质
​
double bsearch_3(double l, double r)
{const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}return l;
}

高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &a,vector<int> &b){//c为答案vector<int> c;//t为进位int t=0;for(int i=0;i<a.size()||i<b.size();i++){//不超过a的范围添加a[i]if(i<a.size())t+=a[i];//不超过b的范围添加b[i]if(i<b.size())t+=b[i];//取当前位的答案c.push_back(t%10);//是否进位t/=10;}//如果t!=0的话向后添加1if(t)c.push_back(1);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为进位t = A[i] - t;//不超过B的范围t=A[i]-B[i]-t;if (i < B.size()) t -= B[i];//合二为一，取当前位的答案C.push_back((t + 10) % 10);//t<0则t=1if (t < 0) t = 1;//t>=0则t=0else 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;//t为进位int t = 0;for (int i = 0; i < A.size() || t; i ++ ){//不超过A的范围t=t+A[i]*bif (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;
}

高精度乘高精度

char a1[10001], b1[10001];
int a[10001], b[10001], i, x, len, j, c[10001];
int main () {cin >> a1 >> b1; //不解释，不懂看前面int lena = strlen(a1); //每个部分都很清楚int lenb = strlen(b1); //这只是方便你们复制for (i = 1; i <= lena; i++)a[i] = a1[lena - i] - '0';//倒序存储for (i = 1; i <= lenb; i++)b[i] = b1[lenb - i] - '0';//倒序存储for (i = 1; i <= lenb; i++)for (j = 1; j <= lena; j++)c[i + j - 1] += a[j] * b[i];//存每位答案for (i = 1; i < lena + lenb; i++)if (c[i] > 9) {c[i + 1] += c[i] / 10;//进位c[i] %= 10;//取当前位答案}len = lena + lenb;while (c[len] == 0 && len > 1)//去除前导零len--;for (i = len; i >= 1; i--)//输出答案cout << c[i];return 0;
}

高精度除低精度

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)//高精度A，低精度b，余数r
{vector<int> C;//答案r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];//补全r>=bC.push_back(r / b);//取当前位的答案r %= b;//r%b为下一次计算}reverse(C.begin(), C.end());//倒序为答案while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导零return C;
}

一维前缀和

前缀和能够快速计算一个序列的区间和，也有很多个问题里面不是直接用前缀和，但是借用了前缀和的思想；

预处理 : s[i] = a[i] + a[i-1]
求区间[l,r] : sum == s[r]-s[l-1]
“前缀和数组” 和 "原数组" 可以合二为一

应用 :

const int N=100010;
int a[N];
int main(){int n,m;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) a[i]=a[i-1]+a[i];scanf("%d",&m);while(m--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",a[r]-a[l-1]);}return 0;
}

二维前缀和

计算矩阵的前缀和：s[x][y] = s[x - 1][y] + s[x][y -1] - s[x-1][y-1] + a[x][y]
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
计算子矩阵的和：s = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 -1]

应用 :

int s[1010][1010];
int n,m,q;
int main(){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&s[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];while(q--){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);}return 0;
}

一维差分

差分是前缀和的逆运算，对于一个数组a，其差分数组b的每一项都是a[i]的前一项a[i-1]的差。

注意 : 差分数组和原数组必须分开存放!!!!!

给区间[l,r]中的每一个数加上c,B[l]+=c,B[r+1]-=c

应用 :

using namespace std;
int a[100010],s[100010];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) s[i]=a[i]-a[i-1];// 读入并计算差分数组while(m--){int l,r,c;cin>>l>>r>>c;s[l]+=c;s[r+1]-=c;// 在原数组中将区间[l, r]加上c}for(int i=1;i<=n;i++){s[i]+=s[i-1];cout<<s[i]<<' ';}// 给差分数组计算前缀和，就求出了原数组return 0;
}

​

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}
int main()
{int n, m, q;cin >> n >> m >> q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)insert(i, j, i, j, a[i][j]); //构建差分数组while (q--){int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);//加c}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //二维前缀和}}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){printf("%d ", b[i][j]);}printf("\n");}return 0;
}

位运算

求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的位置
{int l = 0, r = alls.size() - 1;while (l < r){int mid = l + r >> 1;if (alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1; // 映射到1, 2, ...n
}

区间合并

题 : acwing803

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{vector<PII> res;
​sort(segs.begin(), segs.end());
​int st = -2e9, ed = -2e9;for (auto seg : segs)if (ed < seg.first){if (st != -2e9) res.push_back({st, ed});st = seg.first, ed = seg.second;}else ed = max(ed, seg.second);
​if (st != -2e9) res.push_back({st, ed});
​segs = res;
}

快速加 :

LL qadd(LL a , LL b , int p){LL res = 0;while(b){if(b&1) res = (res + a) % p;a = (a + a) % p;b >>= 1;}return res;
}