【记录】算法 - 算法基础c++
一、基础算法
（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);// 找到第一个>=x的数
do j--; while(q[j] > x);// 找到第一个<=x的数
if(i < j) swap(q[i], q[j]);
}
// (l, i)为<=x的数，(j, r)为>=x的数
// quick_sort(q, l, i - 1), quick_sort(q, i, r);// 注意x=q[l]存在边界问题，死循环
quick_sort(q, l, j), quick_sort(q, j+1, r);// 注意x=q[r]存在边界问题，死循环
}
// AcWing 786. 第k个数
// 用快排思想划分
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, k;
int quick_sort(int l, int r, int k){
if(l == r) return a[l];
int i = l - 1, j = r + 1, x = a[l];
while(i < j){
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
}
int sl = j - l + 1;// <=x的元素个数
if(sl >= k) return quick_sort(l, j, k);
return quick_sort(j+1, r, k-sl);
}// 时间复杂度O(n)，n+n/2+n/4+....
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d", quick_sort(0, n-1, k));
return 0;
}
归并排序
void merge_sort(int q[], int l, int r){
if(l >= r) return;
int m = l + r >> 1;
merge_sort(q, l, m), merge_sort(q, m+1, r);
int k = 0, i = l, j = m + 1; // 合并
while(i <= m && j <= r)
if(q[i] <= q[j]) temp[k++] = q[i++];
else temp[k++] = q[j++];
while(i <= m) temp[k++] = q[i++];
while(j <= r) temp[k++] = q[j++];
for(i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}
// AcWing 788. 逆序对的数量
// 一边归并排序，一边计算逆序对数量
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int q[N], tmp[N];
int n;
ll merge_sort(int l, int r){
if(l >= r) return 0;
int m = l + r >> 1;
ll res = merge_sort(l, m) + merge_sort(m+1, r);// 逆序对只在左边or只在右边
int k = 0, i = l, j = m + 1;
while(i <= m && j <= r){
if(q[i] <= q[j]) tmp[k++] = q[i++];
else{
tmp[k++] = q[j++];
res += m - i + 1;// 逆序对一个在左，一个在右；与当前j构成的逆序对数量=i～m的个数（qi～qm都>qj）
}
}
while(i <= m) 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;
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
cout << merge_sort(0, n-1);
return 0;
}
堆排序
void down(int u){
int t = u;
// 当左孩子存在，且左孩子比u还小
if(u*2 <= cnt && h[u*2] < h[t]) t = u * 2;
// 当右孩子存在，且右孩子比t还小
if(u*2+1 <= cnt && h[u*2+1] < h[t]) t = u * 2 + 1;
// 最小的不是节点u
if(t != u){
swap(h[u], h[t]);
down(t);
}
}
void up(int u){
// 当爹存在，且u比爹小
while(u/2 && h[u/2] > h[u]){
swap(h[u/2], h[u]);
u /= 2;
}
}
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N];// 小根堆，从下标为1开始存储
int n, m, cnt;// cnt记录堆的大小
void down(int u){
int t = u;
if(u*2 <= cnt && h[u*2] < h[t]) t = u * 2;
if(u*2+1 <= cnt && h[u*2+1] < h[t]) t = u * 2 + 1;
if(t != u){
swap(h[u], h[t]);
down(t);
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
// 从n/2的地方（倒数第二层）开始down，时间复杂度降到O（n）
for(int i = n/2; i; i--) down(i);
while(m--){
printf("%d ", h[1]);
h[1] = h[cnt--];
down(1);
}
return 0;
}
（2）二分
整数二分
// 找右边界（1、红色部分）
int bsearch1(int l, int r){
while(l < r){
int mid = l + r + 1 >> 1;// +1防止死循环
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
// 找左边界（2、绿色部分）
int bsearch2(int l, int r){
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
浮点数二分
double bsearch(double l, double r){
const double eps = 1e-8;// 题目要求n位小数则多精确两位
while(r - l > eps){
double mid = (l + r) / 2;
if(check(mid)) r = mid;// 不用考虑边界
else l = mid;
}
return l;
}
// AcWing 790. 数的三次方根
#include <iostream>
using namespace std;
int main(){
double x; cin >> x;
double l = -10000, r = 10000;
while(r - l > 1e-8){
double m = (l + r) / 2;
if(m * m * m >= x) r = m;
else l = m;
}
printf("%lf\n", l);
return 0;
}
（3）高精度
A+B
vector<int> add(vector<int> &A, vector<int> &B){
vector<int> c;
int t = 0;// 本位和
for(int i = 0; i < A.size() || i < B.size(); i++){
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
c.push_back(t % 10);
t /= 10;
}
if(t) c.push_back(1);
return c;
}
A-B
// 比较A是否>B
bool cmp(vector<int> &A, vector<int> &B){
if(A.size() != B.size()) return A.size() > B.size();
for(int i = A.size() - 1; i >= 0; i--)
if(A[i] != B[i])
return A[i] > B[i];
return true;
}
// 默认A>B
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();// 去掉前导0
return c;
}
Axb
vector<int> mul(vector<int> &A, int b){
vetcor<int> c;
int t = 0;
for(int i = 0; i < A.size() || t; i ++){ // 最后t进位
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();
}
A/b
// 余数r通过引用传递
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;
}
（4）前缀和与差分
一维前缀和
S(l-1) = a1 + a2 + … + a(l-1)
Sr = a1 + a2 + … + a(l-1) + al + … + ar
区间和S[l, r] = Sr - S(l-1)
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], s[N];
int main(){
// 数据>1e6用scanf，否则cin
// ios::sync_with_stdio(false);// 取消cin同步，加快cin读取速度，但不能使用scanf
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];// 求前缀和
while(m--){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l-1]);// 求部分和
}
return 0;
}
二维前缀和
// AcWing 796. 子矩阵的和
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
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", &a[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] + a[i][j];// 求前缀和
while(q--){
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);// 求部分和
}
return 0;
}
一维差分
a1, a2, … , ai
构造ai = b1 + b2 + … + bi，数组b为a的差分，数组a为b的前缀和。
// AcWing 797. 差分
#include <iostream>
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];// a前缀和，b差分
// 使得a[l]+c, ..., a[r]+c
void insert(int l, int r, int c){
b[l] += c;
b[r+1] -= c;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
// 初始化差分，相当于在[i,i]使得a[i] += c
for(int i = 1; i <= n; i++) insert(i, i, a[i]);
while(m--){
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
for(int i = 1; i <= n; i++) b[i] += b[i-1];// 求前缀和
for(int i = 1; i <= n; i++) printf("%d ", b[i]);
return 0;
}
二维差分
// AcWing 798. 差分矩阵
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
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(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &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;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
insert(x1, y1, x2, y2, 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]);
puts("");
}
return 0;
}
（5）双指针
把O(n^2)的朴素算法优化到O(n)
for(i = 0, j = 0; i < n; i++){
while(j < i && check(i, j)) j++;
...
}
// AcWing 799. 最长连续不重复子序列
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int s[N];// s[i]表示i出现的次数
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int res = 0;
for(int i = 0, j = 0; i < n; i++){
s[a[i]] ++;// a[i]加入序列
while(s[a[i]] > 1){// j～i序列里有重复元素
s[a[j]]--;
j++;// j向前移动
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
（6）位运算
n >> k & 1
- 表示n的二进制表示第k位（从右往左）上的数字
lowbit(n)
- = n & -n（n&n的补码，-n=～n+1）
- 返回n的二进制表示最右一个1（1010返回0010）
// AcWing 801. 二进制中1的个数
#include <iostream>
using namespace std;
int n;
int lowbit(int x){
return x & -x;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
int x; cin >> x;
int cnt = 0;
while(x) x -= lowbit(x), cnt ++;
cout << cnt << " ";
}
return 0;
}
（7）离散化
数据值域跨度大，但用到的不多
// 存储所有待离散的值
vector<int> alls;
// 排序
sort(alls.begin(), alls.end());
// 去除重复元素
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 二分找出x对应的离散化的值（返回第一个>=x的位置）
int find(int x){
int l = 0, r = alls.size()-1;
while(l < r){
int m = l + r >> 1;
if(alls[m] >= x) r = mid;
else l = mid + 1;
}
return r + 1;// 映射到1, 2, ...n
}
// AcWing 802. 区间和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300000 + 10;
// 把插入and查询操作的下标alls 离散化处理映射到 a，不离散会超时，因为要开2*10^9大小的数组
int a[N], s[N];// 数（映射后，总大小为n+2m=300000），前缀和
vector<int> alls;// 所有的插入和查询操作的下标（待映射的n+2m个坐标）
vector<PII> add, query;// 插入操作，查询操作
int n, m;
int find(int 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
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++){
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for(int i = 0; i < m; i ++){
int l, r;
cin >> l >> r;
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
// 去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 插入
for(auto item : add){
int x = find(item.first);// 找到去重后映射的下标
a[x] += item.second;
}
// 处理前缀和，这里的alls.size()是去重后的
for(int i = 1; i <= alls.size(); i ++) s[i] = s[i-1] + a[i];
// 询问
for(auto item : query){
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l-1] << endl;
}
return 0;
}
（8）区间合并
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for(auto seg : segs)
if(seg.first > ed){
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;
}
// AcWing 803. 区间合并
// 类似会议安排
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
int n;
int main(){
cin >> n;
while(n--){
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
// pair排序默认以pair.first
sort(segs.begin(), segs.end());
int cnt = 0, ed = -2e9;
for(auto item : segs){// 不需要知道区间的具体值，所以只需要更新ed
if(item.first > ed) cnt ++;
ed = max(ed, item.second);
}
cout << cnt << endl;
return 0;
}
（9）递归
// 汉诺塔问题
#include <iostream>
using namespace std;
void move(int n, char from, char to){ // 把编号为n的盘子从from移到to
printf("%d: %c -> %c\n", n, from, to);
}
void hanoi(int n, char A, char B, char C){ // 把n个盘子从A移到C，B是辅助盘子
if(n == 1){
move(n, A, C);
return;
}
hanoi(n-1, A, C, B); // 把上面n-1个盘子从A移到B
move(n, A, C); // 把最底下的盘子从A移到C
hanoi(n-1, B, A, C); // 把n-1个盘子从B移到C
}
int main(){
int n; cin >> n;
hanoi(n, 'A', 'B', 'C');
}
二、数据结构
（1）链表与邻接表
单链表
用静态链表模拟单链表
// AcWing 826. 单链表
#include <iostream>
using namespace std;
const int N = 100010;
// head表示头指针
// e[i]表示节点i的值
// ne[i]表示节点i的next指针
// idx表示尾节点的下一个未使用的位置
int head, e[N], ne[N], idx;
// 初始化
void init(){
head = -1;
idx = 0;
}
// 将x插到头节点
void add_to_head(int x){
e[idx] = x, ne[idx] = head, head = idx++;
}
// 将x插到下标是k的点后面
void add(int k, int x){
e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
// 将下标是k的点后面的点删掉
void remove(int k){
ne[k] = ne[ne[k]];
}
int main(){
int m; cin >> m;
init();
while(m--){
char op;
int k, x;
cin >> op;
if(op == 'H'){
cin >> x;
add_to_head(x);
}else if(op == 'D'){
cin >> k;
if(k) remove(k-1);
else head = ne[head];// 删除头节点
}else{
cin >> k >> x;
add(k-1, x);
}
}
for(int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
return 0;
}
双链表
// AcWing 827. 双链表
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
void init(){
// 下标为0的点做左边界点，下标为1的点做右边界点
r[0] = 1; l[1] = 0;
// 初始idx从2开始
idx = 2;
}
// 将x插入到下标为a的点右边
void insert(int a, int x){
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++;
}
// 删除下标为a的点
void remove(int a){
l[r[a]] = l[a];
r[l[a]] = r[a];
}
int main(){
cin >> m;
init();
while(m--){
string op;cin >> op;
int k, x;
if(op == "L"){
cin >> x;
insert(0, x);
}else if(op == "R"){
cin >> x;
insert(l[1], x);
}else if(op == "D"){
cin >> k;
remove(k+1);
}else if(op == "IL"){
cin >> k >> x;
insert(l[k+1], x);
}else{
cin >> k >> x;
insert(k+1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
return 0;
}
邻接表
见树与图
（2）栈与队列
栈
用数组模拟栈
// tt栈顶
int stk[N], tt = -1;
// 插入x
stk[++t] = x;
// 弹出栈顶
tt--;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if(tt == -1) return true;
else false;
// 判断栈是否为满
if(tt == N-1) return true;
else false;
// 栈的长度
tt + 1;
队列
用数组模拟队列
// 普通队列
// hh队头，tt队尾
int q[N], hh = 0, tt = -1;
// 插入
q[++tt] = x;
// 队头出队
hh++;
// 队头的值
q[hh];
// 判断队列是否为空
if(hh <= tt) return false;
else return true;
// 循环队列
// hh队头，tt队尾的下一个位置
int q[N], hh = 0, tt = 0;
// 插入
q[tt] = x;
tt = (tt + 1) % N;
// 从队头弹出
hh = (hh + 1) % N;
// 队头的值
q[hh];
// 判断队列是否为空
if(hh == tt) return true;
else return false;
// 判断队列是否为满(以队头在队尾指针的下一位作为标志)
if((tt+1)%N == hh) return true;
else return false;
// 队列长度
(hh - tt + N) % N
单调栈
// AcWing 830. 单调栈
// 输出每个数左边第一个比它小的数
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int stk[N], tt;
int main(){
cin >> n;
while(n--){
int x; cin >> x;
// 当栈不为空and栈顶元素>=x，栈顶弹出（保持栈顶为最近的最小值）
while(tt && stk[tt] >= x) tt--;
if(tt) cout << stk[tt] << " ";
else cout << "-1 ";
// 当前x入栈
stk[++tt] = x;
}
return 0;
}
单调队列
// AcWing 154. 滑动窗口
#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N], q[N];// a保存数值；q双端队列，保存下标
int hh = 0, tt = -1;
int n, k;
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
// 找滑动窗口的最小值
for(int i = 0; i < n; i++){
// 队头元素不在窗口内（队头在数组中的下标<当前窗口的最小下标），队头出队
// 用if是因为每次只有一个元素进队，一个元素出队
if(hh <= tt && q[hh] < i-k+1) hh++;
// 队尾>=当前元素，队尾出队（保持队列单调递增，队头为当前窗口最小值）
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
// 当前i入队
q[++tt] = i;
// 凑足k个数才开始输出
if(i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
hh = 0, tt = -1;
// 找滑动窗口的最大值
for(int i = 0; i < n; i++){
if(hh <= tt && q[hh] < i-k+1) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if(i >= k - 1) printf("%d ", a[q[hh]]);
}
return 0;
}
（3）kmp
// 朴素模式匹配
// 时间复杂度O（nm）
void search(string p, string s){
// 模式串p，字符串s
// 从下标1开始匹配
// i指向模式串，j指向字符串，两个一起移动
for(int i = 1; i <= s.size(); i++){
bool flag = true;
for(int j = 1; j <= p.size(); j++){
if(s[i+j-1] != p[j]){// 注意是i + j-1，不是j
flag = false;
break;
}
}
}
}
// kmp
// 时间复杂度O（n+m）
// 利用已知s串后缀匹配p串的情况，减少s串在匹配p串时存在的回溯的情况
#include <iostream>
using namespace std;
const int N = 1e5+10, M = 1e6+10;
char p[N], s[M];
int ne[N];
int n, m;
int main(){
// p和s从下标1开始存储
cin >> n >> p+1 >> m >> s+1;
// 求next数组
// i从2开始，因为ne[1]恒=0；ne[i]=j表示模式串p的[i-j+1~i]=[1~j]（后缀=前缀）
for(int i = 2, j = 0; i <= n; i++){
while(j && p[i] != p[j+1]) j = ne[j]; // 不断尝试扩展匹配长度j，如果扩展失败，j=next[j]，直到j=0
if(p[i] == p[j+1]) j++; // 如果匹配成功，j长度+1
ne[i] = j;
}
// 匹配字符串
// i从1开始，j从0开始
for(int i = 1, j = 0; i <= m; i++){
// s[i]和p[j+1]是否匹配，不匹配，j递归=ne[j]，不断地使s串的后缀=p串的前缀，直到s[i]=p[j+1]或者j=0
while(j && s[i] != p[j+1]) j = ne[j];
// 匹配，j往后移一位
if(s[i] == p[j+1]) j++;
// 完全匹配
if(j == n) printf("%d ", i-n);
}
return 0;
}
（4）前缀树Trie
// AcWing 835.Trie字符串统计
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// son[x][y]=z表示节点x第y个儿子下标为z
// cnt[]表示以该节点结尾的单词有几个
// idx表示当前用到哪个节点
int son[N][26], cnt[N], idx;
int n;
char str[N];
void insert(char str[]){
int p = 0;
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';// 转化成数字
if(!son[p][u]) son[p][u] = ++idx;// 如果没有这个字母则插入
p = son[p][u];
}
cnt[p]++;
}
int query(char str[]){
int p = 0;
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main(){
cin >> n;
while(n--){
char op;
cin >> op >> str;
if(op == 'I') insert(str);
else cout << query(str) << endl;
// 如果是用scanf，建议用%s配合char[]读；用%c会把前一行的换行、空格读入
/*
char op[2];
scanf("%s%s", op, str);
if(*op == "I") ...
*/
}
return 0;
}
// AcWing 143. 最大异或对
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 31 * N;
int a[N], son[M][2], idx;
int n;
void insert(int x){
int p = 0;
for(int i = 30; i >= 0; i--){
int u = x >> i & 1;// 第i+1位上的数字
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x){
int p = 0, res = 0;
for(int i = 30; i >= 0; i--){
int u = x >> i & 1;
if(son[p][!u]){// 从最高位开始，每次尽量走与当前位相反的路
p = son[p][!u];
res = res*2 + !u;
}else{
p = son[p][u];
res = res*2 + u;
}
}
return res;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
insert(a[i]);
}
int res = 0;
for(int i = 0; i < n; i ++) res = max(res, query(a[i]));
printf("%d", res);
return 0;
}
（5）并查集
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N];
int n, m;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);// 路径压缩
return p[x];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) p[i] = i;
while(m--){
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if(*op == 'M') p[find(a)] = find(b);
else{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
// AcWing 837. 连通块中点的数量
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N];
int n, m;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);// 路径压缩
return p[x];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) p[i] = i, cnt[i] = 1;
while(m--){
char op[5];
int a, b;
scanf("%s", op);
if(op[0] == 'C'){
scanf("%d%d", &a, &b);
a = find(a), b = find(b);
if(a == b) continue;// 注意a和b可能已经在同一个集合里
p[a] = b;
cnt[b] += cnt[a];
}else if(op[1] == '1'){
scanf("%d%d", &a, &b);
if(find(a) == find(b)) puts("Yes");
else puts("No");
}else{
scanf("%d", &a);
printf("%d\n", cnt[find(a)]);
}
}
return 0;
}
（6）堆
（7）Hash表
开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, INF = 0x3f3f3f3f;
// 开放寻址法中，hash表表长一般为表中元素个数的2～3倍的质数
int h[N];
int n;
// 要么返回x的位置，要么返回k后第一个空的位置。
int find(int x){
int k = (x % N + N) % N;
while(h[k] != INF && h[k] != x){
k++;
if(k == N) k = 0;// 循环找
}
return k;
}
int main(){
scanf("%d", &n);
memset(h, 0x3f, sizeof(h));// 按字节赋值
while(n--){
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'I') h[find(x)] = x;
else{
if(h[find(x)] == INF) puts("No");
else puts("Yes");
}
}
return 0;
}
0x3f3f3f3f
在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。
比如对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。
而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。
所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：
0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即109数量级，而一般场合下的数据都是小于109的。
0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。
拉链法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003;// hash表表长最好为质数
int h[N], e[N], ne[N], idx;
int n;
void insert(int x){
int k = (x % N + N) % N;// 散列化，+N防止负数
/*
一般余数应为正数。
在c++中，-10%3=-1；正确计算应该10=-4*3+2，-10%3=2。
不能（x+N）%N，会溢出。
*/
e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}
bool find(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i])
if(e[i] == x) return true;
return false;
}
int main(){
scanf("%d", &n);
memset(h, -1, sizeof(h));
while(n--){
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'I') insert(x);
else{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
字符串哈希
// AcWing 841. 字符串哈希
#include <iostream>
using namespace std;
typedef unsigned long long ULL;// unsigned用来mod Q（=2^64）
const int N = 1e5 + 10, P = 131;// P为P进制，一般取131或者13331，不容易冲突
int n, m;
char str[N];
ULL h[N], p[N];// 哈希值前缀和；p[i]表示p^i
ULL get(int l, int r){
return h[r] - h[l-1] * p[r-l+1]; // 前缀和
/*
h[r]为1到r位字符串的哈希值
h[l-1]为1到l-1位字符串的哈希值
* p[r-l+1]为了让 1到l-1位 左边对齐到 1到r位
*/
}// 返回[l, r]区间内字符串的哈希值
int main(){
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
// 打表
p[0] = 1;
for(int i = 1; i <= n; i++){
h[i] = h[i-1] * P + str[i];// str[i]自动转化为ascii码，128个
p[i] = p[i-1] * P;
}
while(m--){
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
三、搜索与图论
（1）DFS与BFS
DFS
// AcWing 842. 排列数字
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];// path[i]表示第i位上的数字，从0开始
bool st[N];// st[i]表示i是否被用过
void dfs(int u){// u表示当前走到第i位
// 递归结束的条件
if(u == n){
for(int i = 0; i < n; i++) printf("%d ", path[i]);
puts("");
return;
}
for(int i = 1; i <= n; i++)
if(!st[i]){// 如果i还没有被使用过
path[u] = i;
st[i] = true;// 状态标记
dfs(u+1);
st[i] = false;// 递归后恢复
}
}
int main(){
scanf("%d", &n);
dfs(0);
return 0;
}
BFS
// AcWing 844. 走迷宫
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII; // 坐标
const int N = 110;
int n, m;
int g[N][N], d[N][N];
// g迷宫；
// d标记状态，d[x][y]表示(x, y)到原点的距离
int bfs(){
// bfs队列
queue<PII> q;
q.push({0, 0});
// 初始化数组
memset(d, -1, sizeof d);
d[0][0] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// (-1, 0)(0, 1)(1, 0)(0, -1)表示⬅️⬆️➡️⬇️
while(q.size()){
// 弹出队头
auto t = q.front();
q.pop();
// 遍历邻近节点
for(int i = 0; i < 4; i++){
int x = t.first + dx[i], y = t.second + dy[i];
// x、y合法 且 有路 且 没走过
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
return d[n-1][m-1];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j++)
scanf("%d", &g[i][j]);
printf("%d", bfs());
return 0;
}
（2）树与图的遍历
深度优先遍历
// AcWing 846. 树的重心
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
// 用邻接表表示(以边为主体节点)
// e[i]，i是边编号，值是i这条边终点的结点编号
int ans = N;// 最终结果
bool st[N];// dfs标记，st[i]表示编号为i的节点是否遍历过
// 添加从a到b的单向边
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 求以u为根的子树中包含的节点数量
int dfs(int u){
st[u] = true;
int sum = 1, res = 0;// 整棵树的节点数；删除该节点后子树中各连通块节点数最大值
for(int i = h[u]; i != -1; i = ne[i]){// 遍历该节点的邻接表
int j = e[i];
if(!st[j]){// 如果j这个点没有搜过
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);// 比较节点的子树中各连通块节点数、除了以u节点为根的树以外的节点总数
ans = min(ans, res);// 比较最小值
return sum;
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
// 输入n-1条边
for(int i = 0; i < n-1; i ++){
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
宽度优先遍历
// AcWing 847. 图中点的层次
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int bfs(){// 返回最短路径
queue<int> q;
q.push(1);
memset(d, -1, sizeof d);
d[1] = 0;
while(q.size()){
int t = q.front();
q.pop();
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(d[j] == -1){
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
// AcWing 848. 有向图的拓扑序列
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];// d存储每个点的入度
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 返回是否存在拓扑序列
bool topsort(){
int hh = 0, tt = -1;
// 入度为0的点入队
for(int i = 1; i <= n; i++)
if(!d[i]) q[++tt] = i;
while(hh <= tt){
int t = q[hh++];// 队头出队
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(--d[j] == 0) q[++tt] = j;// 入度为0的点入队
}
}
return tt == n - 1;// 所有点都入队了==存在拓扑序列
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++){
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;
}
if(!topsort()) puts("-1");
else{
for(int i = 0; i < n; i++) cout << q[i] << ' ';
}
return 0;
}
（3）最短路径
Dijkstra
朴素的Dijkstra
- 稠密图用邻接矩阵存储
// AcWing 849. Dijkstra求最短路 I
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n, m;
// 以下下标都从1开始
int g[N][N];// 图的邻接矩阵
int dist[N];// 各点到1号的最短距离
bool st[N];// 某点是否已确定最短路径
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 需要进行n-1次的求最短路径
for(int i = 0; i < n-1; i++){
int t = -1;// 记录目前最短路径下标
// 找到新的最短路径点
for(int j = 1; j <= n; j++)
if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 未确定最短路径 并且 到源点的距离比dist[t]还小
// 用新点更新最短距离
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
// 更新标记
st[t] = true;
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
cin >> n >> m;
// 初始化邻接矩阵
memset(g, 0x3f, sizeof g);
while(m --){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);// 处理重边
}
cout << dijkstra() << endl;
return 0;
}
堆优化的Dijkstra
- 稀疏图用邻接表存储
// AcWing 850. Dijkstra求最短路 II
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;// 距离，点
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;// 邻接表
int dist[N];
bool st[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while(heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
// 如果已经处理过该点，跳过。
if(st[ver]) continue;
// 如果没有，处理
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
// 更新最短距离
if(dist[j] > dist[ver] + w[i]){
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
st[ver] = true;// 更新标记
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);// 添加重边也没关系，有堆做优化
}
printf("%d", dijkstra());
return 0;
}
Bellman-Ford
/*
有向图中存在负权边，则不一定存在最短路径。如果存在最短路径，则最短路径上肯定没有负环。
假设存在n个点，如果点1到n的最短路径存在，则最短路径的长度等于n-1。
如果存在负环，则第n次时还能进行松弛操作。
*/
for(int i = 0; i < n; i++)
/*
有向图中，如果所有边都满足三角形不等式dist[y]<=dist[x]+c，则dist数组就是所求最短路。
*/
for(int j = 0; j < m; j++){
auto e = edges[j];
dist[e.b] = min(dist[e.b], dist[e.a] + e.c);// 松弛操作
}
// AcWing 853. 有边数限制的最短路
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], last[N];
struct Edge{
int a, b, c;
}edges[M];
void bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 走k步
for(int i = 0; i < k; i++){
memcpy(last, dist, sizeof dist);// 拷贝上一次迭代的结果，避免k步限制失效，发生串联
// 遍历所有的边
for(int j = 0; j < m; j++){
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}
int main(){
cin >> n >> m >> k;
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
bellman_ford();
/*
用大于INF/2判断是否存在最短路径，可能存在未更新的点同样被边更新的情况。
到不了的几个点之间存在负权边。使得到不了的点的距离一定范围内减小，小于了INF。这时可以使用小一点的INF/2来做判断，大于INF/2则认为不存在路径。
*/
if(dist[n] > 0x3f3f3f3f/2) puts("impossible");
else cout << dist[n];
return 0;
}
SPFA
Shortest Path Fast Algorithm
队列优化的Bellman-Ford算法
- 图中没有负环才能用SPFA
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];// 标记点的遍历状态
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;// 解除标记，曾经加入过队列的点出队后，会再次被加入队列，再次加入后继续更新与它联通的点
// 扫描该节点的所有出边
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
/*
bellman-ford是不管这条边是否满足不等式，都要进行处理。
spfa通过队列、该点的出边、不满足不等式，进行扩展处理。避免对不需要扩展的节点的冗余扫描。
*/
// 如果不满足不等式
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
// 如果没有处理过
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
/*
spfa是基于拓扑序列的，不存在bellman-ford算法中未更新的点同样被边更新的情况。所以用==0x3f3f3f3f来判断是否存在最短路径。
*/
if(t == 0x3f3f3f3f) puts("impossible");
else cout << t;
return 0;
}
// AcWing 852. spfa判断负环
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2010, M = 10010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];// cnt记录到1到n的最短路径长度
bool st[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa(){
// 找负环无需初始化dist数组，因为dist数组一开始已经是0了，所以接下来只会更新小于0的边权，也就是负权边，存在负环的话就会不停的更新
queue<int> q;
// 第一个点可能没有负环，则把所有点放进去。找的最短路径不一定从起点1开始
for(int i = 1; i <= n; i++){
st[i] = true;
q.push(i);
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
// 最短路径超过n条边
if(cnt[j] >= n) return true;
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}
Floyd
#include <iostream>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, k;
int d[N][N];
void floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
/*
d[k, i, j]表示从i出发，只经过1～k点，到达j的最短路径。
dp。确定d[i][k]，枚举找最小的d[k][j]。
*/
}
int main(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) // 初始化邻接矩阵
for(int j = 1; j <= n; j++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m--){
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c); // 处理重边
}
floyd();
while(k--){
int a, b;
cin >> a >> b;
int t = d[a][b];
if(t > INF/2) puts("impossible");
else cout << t << endl;
}
return 0;
}
（4）最小生成树
Prim
朴素的Prim
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N]; // 记录点到集合的距离
bool st[N];
int prim(){ // 返回最小生成树边权重之和
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 0; i < n; i++){ // 遍历n次，找n个点加入集合
int t = -1;
for(int j = 1; j <= n; j++) // 找到集合外距离集合最近的点
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
if(i && dist[t] == INF) return INF; // 不是第一个点 且 t到集合的距离是INF（说明当前集合是不连通的）
if(i) res += dist[t]; // 不是第一个点，加入集合
st[t] = true;
for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]); // 更新所有点到集合的距离
}
/*
注意先累加再更新，避免t身上有自环时，更新了dist[t]后，再累加时dist[t]值已经错误。
*/
return res;
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m--){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图建立两条边；去重边
}
int t = prim();
if(t == INF) puts("impossible");
else cout << t << endl;
return 0;
}
堆优化的Prim
Kruskal
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int p[N]; // 并查集
struct Edge{
int a, b, w;
bool operator< (const Edge &e)const{
return w < e.w;
}
}edges[M];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal(){
sort(edges, edges + m); // 利用sort对所有的边进行排序
for(int i = 1; i <= n; i++) p[i] = i; // 初始化并查集
int res = 0, cnt = 0; // 最小生成树的树边权重之和，包含的边数
for(int i = 0; i < m; i++){
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if(a != b){ // 如果a和b不在一个集合里，合并a、b
p[a] = b;
res += w;
cnt ++;
}
}
if(cnt < n-1) return INF; // 最小生成树的边有n-1条
return res;
}
int main(){
cin >> n >> m;
for(int i = 0; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
int t = kruskal();
if(t == INF) puts("impossible");
else cout << t << endl;
return 0;
}
（5）二分图
染色法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int n, m;
int h[N], ne[M], e[M], idx;
int color[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c){ // 返回是否无冲突发生
color[u] = c; // 从u开始，u染c种颜色
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!color[j]){ // 如果j点没有染过颜色
if(!dfs(j, 3 - c)) return false; // dfs染j点为c的异种颜色
}
else if(color[j] == c) return false;
}
return true;
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--){
int a, b;
cin >> a >> b;
add(a, b), add(b, a); // 无向图
}
bool flag = true;
for(int i = 1; i <= n; i++)
if(!color[i]) // 如果i点没有染过颜色
if(!dfs(i, 1)){ // 如果发生冲突
flag = false;
break;
}
if(flag) puts("Yes");
else puts("No");
return 0;
}
匈牙利算法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 1e5 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx; // 左边点的邻接表
int match[N]; // 右边的点对应左边哪个点
bool st[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool find(int x){
for(int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j]){
st[j] = true; // 设为true防止find(match[j])无限递归
if(match[j] == 0 || find(match[j])){ // 如果没有匹配过or对应匹配的点能找到下家
match[j] = x;
return true;
}
}
}
return false;
}
int main(){
cin >> n1 >> n2 >> m;
memset(h, -1, sizeof h);
while(m--){
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
for(int i = 1; i <= n1; i++){
memset(st, false, sizeof st); // 每次更新为false，否则除了第一次匹配的，后面的都无法挖墙脚达到最大匹配
if(find(i)) res ++;
}
cout << res;
return 0;
}
四、数学知识
（1）质数
// 试除法判断质数
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2; i <= n / i; i++)
if(n % i == 0) return false;
return true;
}
（2）约数
// 欧几里得算法 求最大公约数
int gcd(int a, int b){
return b ? gcb(b, a % b) : a;
}
（3）欧拉函数
（4）快速幂
（5）扩展欧几里得算法
（6）中国剩余定理
（7）高斯消元
（8）组合计数
（9）容斥原理
（10）简单博弈论
五、动态规划
（1）背包问题
01背包
每个物品只有一个，最多选一次
// 二维
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v, w;
int f[N][N]; // f[i][j]表示 只选前i个物品 且 总体积<=j 的最大总价值
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){ // f[0][?]都为0，所以i从1开始
cin >> v >> w;
for(int j = 0; j <= m; j++){
f[i][j] = f[i - 1][j]; // 不含第i个物品的情况
if(j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + w); // 如果含第i个物品的情况存在的话，比较不含、含第i个物品的情况
}
}
cout << f[n][m];
return 0;
}
// 一维优化
// 利用滚动数组
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v, w;
int f[N]; // 总体积<=j的最大总价值
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> v >> w;
for(int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
完全背包
每个物品有无限个，可以选无限次
// 三维
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v, w;
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v >> w;
for(int j = 0; j <= m; j ++)
for(int k = 0; k * v <= j; k ++) // 选k个第i个物品
f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w); // 比较f[i-1][j-k*v]+k*w中的最大值
}
cout << f[n][m];
return 0;
}
// 二维优化
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v, w;
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v >> w;
for(int j = 0; j <= m; j ++){
f[i][j] = f[i - 1][j];
if(j >= v) f[i][j] = max(f[i][j], f[i][j - v] + w);
}
}
cout << f[n][m];
return 0;
}
// 一维优化
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v, w;
int f[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v >> w;
for(int j = v; j <= m; j ++)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m];
return 0;
}
多重背包
每个物品有Si个，最多选Si次
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v, w, s;
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> v >> w >> s;
for(int j = 0; j <= m; j ++)
for(int k = 0; k <= s && k * v <= j; k ++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
}
cout << f[n][m];
return 0;
}
// 二进制优化
#include <iostream>
using namespace std;
const int N = 12010, M = 2010; // N物品数=1000*log2000+10；M体积
int n, m;
int v[N], w[N];
int f[M];
int main(){
cin >> n >> m;
int cnt = 0; // 标记打包下标
for(int i = 1; i <= n; i ++){
int a, b, s;
cin >> a >> b >> s;
int k = 1; // 从每个包里装1个物品开始打包
while(k <= s){ // 每次把k个物品装成一个01背包
v[++cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0){ // 还剩c=s个没装
v[++cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j-v[i]]+w[i]);
cout << f[m];
return 0;
}
分组背包
每组物品有Si个，最多选一个
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> s[i];
for(int j = 0; j < s[i]; j ++)
cin >> v[i][j] >> w[i][j];
}
for(int i = 1; i <= n; i ++)
for(int j = m; j >= 0; j --)
for(int k = 0; k < s[i]; k++)
if(j >= v[i][k]) // 不能写在j循环里，因为v[i][k]随着k改变而动态变化
f[j] = max(f[j], f[j-v[i][k]]+w[i][k]);
cout << f[m];
return 0;
}
（2）线性DP
// AcWing 898. 数字三角形
#include <iostream>
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
cin >> a[i][j];
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= i + 1; j ++) // 边界的右上角也要初始化
f[i][j] = -INF; // 初始化状态
f[1][1] = a[1][1];
for(int i = 2; i <= n; i ++)
for(int j = 1; j <= i; j++)
f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j] + a[i][j]); // 来自左上角or来自右上角
int res = -INF;
for(int i = 1; i <= n; i++) res = max(res, f[n][i]); // 遍历最后一行找最大路径
printf("%d", res);
return 0;
}
// AcWing 895. 最长上升子序列
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N]; // 以a[i]结尾的子序列长度
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
f[i] = 1; // 只有a[i]一个数
for(int j = 1; j < i; j++) // 从a[1]~a[i-1]找<a[i]的数
if(a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res, f[i]);
cout << res;
return 0;
}
// AcWing 897. 最长公共子序列
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N]; // 所有由第一个序列的前i个字母、第二个序列的前j个字母构成的公共子序列个数
int main(){
scanf("%d%d", &n, &m);
scanf("%s%s", a+1, b+1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
f[i][j] = max(f[i-1][j], f[i][j-1]); // f[i-1][j]和f[i][j-1]，它们都包含f[i-1][j-1]的情况
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
}
printf("%d", f[n][m]);
return 0;
}
（3）区间DP
// AcWing 282. 石子合并
#include <iostream>
using namespace std;
const int N = 310, INF = 1e8;
int n;
int s[N];
int f[N][N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
for(int i = 1; i <= n; i++) s[i] += s[i-1]; // 计算前缀和
for(int len = 2; len <= n; len++) // 枚举区间长度
for(int l = 1; l + len - 1 <= n; l++){ // 枚举左端点
int r = l + len -1;
f[l][r] = INF;
for(int k = l; k < r; k++) // 枚举分界点k
f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
}
printf("%d", f[1][n]);
return 0;
}
（4）计数类DP
（5）数位统计DP
// AcWing 338. 计数问题
（6）状态压缩DP
（7）树形DP
（8）记忆化搜索