算法

晋以次纪念我的算法学习

正则表达

正则学习网站

基本通配符

符号	解释
.	任意字符
*	0个或多个
+	一个或多个
?	0个或1个

字符集

表达式	解释
[bdf]eer(字符集中加入^表否定)	括号里其中一个字符与后面匹配
[a-z]	匹配a到z之间的所有字母
[0-9]	匹配0到9之间的所有数字

大括号

表达式	解释
be{2}r	表示e只能出现两次
be{3,}r	表示e至少出现三次
be{1,3}r	表示e出现1到3次

转义字符\

表达式	解释
*	匹配*
^[0-9]	^匹配字符串的开始
html$	查找仅在末尾出现的html
\w	单词字符\w：字母,数字,下划线
\W	非单词字符
\d	数字字符
\D	非数字字符
\s	空白字符
\S	非空白字符

基础算法

快速排序

不稳定的排序

P1177 【模板】快速排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N];

void quick_sort(int l, int r) {
	if (l >= r) {
		return;
	}
	int left = l;
	int right = r;
	int mid = a[l + (r - l) / 2];	//这里一定要取的当前区间数组的中点对应的值
	while (left <= right) {
		while (a[left] < mid) {	//找比中点值大的数,不能取=，假如要排序的数有相同的话,会浪费时间,不取=不影响最后的结果
			left++;				//mid左边的数都<=mid
		}
		while (a[right] > mid) {//找比中点值小的数,不能取=，假如要排序的数有相同的话，会浪费时间,不取=不影响最后的结果
			right--;			//mid右边的数都>=mid
		}
		if (left <= right) {
			swap(a[left], a[right]);
			left++;
			right--;
		}
	}
    //最后的结果为0·····right left·····n-1
    //递归左半部分
	quick_sort(l, right);
    //递归右半部分
	quick_sort(left, r);
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	quick_sort(0, n - 1);
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			cout << a[i];
		}
		else {
			cout << " " << a[i];
		}
	}
	return 0;
}

归并排序

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
using namespace std;
const int N = 5e5 + 5;
int a[N], temp[N];
long long ans;

void merge_sort(int l, int r) {
	if (l >= r) {
		return;
	}
	int mid = l + r >> 1;
	int left = l;
	int right = mid + 1;
	int res = l;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	while (left <= mid && right <= r) {
		if (a[left] <= a[right]) {
			temp[res++] = a[left++];
		}
		else {
			ans += mid - left + 1;		//关键位置
			temp[res++] = a[right++];
		}
	}
	while (left <= mid) {
		temp[res++] = a[left++];
	}
	while (right <= r) {
		temp[res++] = a[right++];
	}
	for (int i = l; i <= r; i++) {
		a[i] = temp[i];
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	merge_sort(0, n - 1);
	cout << ans;
	return 0;
}

二分

整数二分

模板

//最后的答案要往左边找时
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    //向左边找 //if判断mid是否满足性质，注意该性质会划分数组的右边部分
        else l = mid + 1;           //向右边找
    }
    return l;   //最后的l和r的值是相同的
}

//最后的答案要往右边找时
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;   // mid 向上取整
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

789. 数的范围 - AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	while (q--) {
		int x;
		cin >> x;
		int l = 0;
		int r = n - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (a[mid] >= x) {
				r = mid;
			}
			else {
				l = mid + 1;
			}
		}
		if (a[l] != x) {
			cout << "-1 -1" << endl;
		}
		else {
			cout << l << " ";
			int l = 0;
			int r = n - 1;
			while (l < r) {
				int mid = l + r + 1 >> 1;
				if (a[mid] <= x) {
					l = mid;
				}
				else {
					r = mid - 1;
				}
			}
			cout << l << endl;
		}
	}
	return 0;
}

浮点数二分

790. 数的三次方根 - AcWing题库

#include<iostream>
using namespace std;

int main() {
	double x;
	scanf("%lf", &x);
	double l = -1e4, r = 1e4;
	while (r - l > 1e-8) {
		double mid = (l + r) / 2;
		if (mid * mid * mid >= x) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	printf("%.6f", l);
	return 0;
}

前缀和

一维前缀和

795. 前缀和 - AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N];
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++) {
		a[i] = a[i - 1] + a[i];
	}
	while (m--) {
		int l, r;
		cin >> l >> r;
		cout << a[r] - a[l - 1] << endl;
	}
	return 0;
}

二维前缀和

796. 子矩阵的和 - AcWing题库

//点看作格子
//格子当作放大无数倍的点,坐标对应的是一个框格,可以联系一维前缀和来想
//二维前缀和可以考虑成一个个的格子，结合一维前缀和来思考

#include<iostream>
using namespace std;
const int N = 1005;
int a[N][N];

int main() {
	int n, m, q;
	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++) {
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
		}
	}
	while (q--) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		printf("%d\n", a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]);
	}
	return 0;
}

差分

一维差分

797. 差分 - AcWing题库

假设 a[] = {1, 3, 2, 1, 4}
我们把 a 数组带入代码中走一遍，看看结果(注意 b数组是全局变量，所以默认值全为0)
b1 = b1 + a1 = 0 + 1 = 1  ~~~
b2 = b2 - a1 = 0 - 1 = -1

b2 = b2 + a2 = -1 + 3 = 2 ~~~
b3 = b3 - a2 = 0 - 3 = -3

b3 = b3 + a3 = -3 + 2 = -1 ~~~
b4 = b4 - a3 = 0 - 2 = -2

b4 = b4 + a4 = -2 + 1 = -1 ~~~
b5 = b5 - a4 = 0 - 1 = -1

b5 = b5 + a5 = -1 + 4 = 3 ~~~
b6 = b6 - a5 = 0 - 4 = -4

请注意带~~~的就是构造出来的b差分数组,可以将b数组求前缀和

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];

void insert(int l, int r, int d) {
	b[l] += d;
	b[r + 1] -= d;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		insert(i, i, a[i]);
	}
	/*
	for (int i = 1; i <= n; i++) {
		b[i] = a[i] - a[i - 1];
	}
	*/
	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;
}

二维差分

798. 差分矩阵 - AcWing题库

我们可以先假想a数组为空，那么b数组一开始也为空，但是实际上a数组并不为空，因此我们每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作，就成功构建了差分b数组.

#include<iostream>
using namespace std;
const int N = 1005;
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;
	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]);
			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]);
		}
		printf("\n");
	}
	return 0;
}

双指针

799. 最长连续不重复子序列 - AcWing题库

时间复杂度O(2n)

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], s[N];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int maxx = -1;
	for (int i = 1, j = 1; i <= n; i++) {
		s[a[i]]++;
        //将所维护的区间中那个重复的去掉
		while (s[a[i]] > 1) {
			s[a[j]]--;
			j++;
		}
		maxx = max(maxx, i - j + 1);
	}
	cout << maxx;
	return 0;
}

800. 数组元素的目标和 - AcWing题库

//使用双指针
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int main() {
	int n, m, x;
	cin >> n >> m >> x;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0, j = m - 1; i < n; i++) {
		while (a[i] + b[j] > m) {
			j--;
		}
		if (a[i] + b[j] == x) {
			cout << i << " " << j;
		}
	}
	return 0;
}


//使用二分
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int main() {
	int n, m, x;
	cin >> n >> m >> x;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n; i++) {
		int t = x - a[i];
		int l = 0, r = m - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (b[mid] >= t) {
				r = mid;
			}
			else {
				l = mid + 1;
			}
		}
		if (b[l] != t) {
			continue;
		}
		else {
			cout << i << " " << l;
			break;
		}
	}
	return 0;
}

位运算

801. 二进制中1的个数 - AcWing题库

#include<iostream>
using namespace std;


int low_bit(int x) {
	return x & -x;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		int res = 0;
		while (x) {
			x -= low_bit(x);
			res++;
		}
		cout << res << " ";
	}
	return 0;
}

离散化

unique函数的实现(前提排好序)
vector<int>::iterator unique(vector<int> &a){
    int j=0;
    for(int i=0;i<a.size();i++){
        //是第一个或者a[i]不等于a[i-1]
        if(!i || a[i]!=a[i-1])
            a[j++]=a[i];
    }
    return a.begin()+j;
}
unique函数底层是将后面没有重复的向前面有重复的进行覆盖

802. 区间和 - AcWing题库

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 3e5 + 5;

typedef pair<int, int> PII;
vector<int> all;
vector<PII> alls, query;
int a[N], s[N];

int find(int x) {
	int l = 0, r = all.size() - 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (all[mid] >= x) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l + 1;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int x, c;
		cin >> x >> c;
		alls.push_back({ x,c });
		all.push_back(x);
	}
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		query.push_back({ l,r });
		all.push_back(l);
		all.push_back(r);
	}
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	for (auto t : alls) {
		int x = find(t.first);
		a[x] += t.second;
	}
	for (int i = 1; i <= all.size(); i++) {
		s[i] = s[i - 1] + a[i];
	}
	for (auto t : query) {
		cout << s[find(t.second)] - s[find(t.first) - 1] << endl;
	}
	return 0;
}

区间合并

803. 区间合并 - AcWing题库

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> v;
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		v.push_back({ l,r });
	}
	sort(v.begin(), v.end());
	int ed = 0xc0c0c0c0;	//ed定义为无穷小
	int ans = 0;
    //遍历着n段区间
	for (int i = 0; i < n; i++) {
        //当前区间的左端点比ed大
		if (v[i].first > ed) {
            //ed则取当前区间和原来的ed中最大的那个
			ed = v[i].second;
           //ans加一
			ans++;
		}
		else {
			ed = max(ed, v[i].second);
		}
	}
	cout << ans;
	return 0;

}

Manacher算法(马拉车)

视频推荐

184 Manacher(马拉车)_哔哩哔哩_bilibili

题目详情 - L2-008 最长对称子串 (pintia.cn)

#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
char a[N], s[N];
int d[N];
int main() {
	ios::sync_with_stdio(false);
	int k = 0, res = -1;
	string a;
	getline(cin, a);
	int n = a.length();
	s[0] = '$';
	s[++k] = '#';
	for (int i = 0; i < n; i++) {
		s[++k] = a[i];
		s[++k] = '#';
	}
	d[1] = 1;
	int l, r = 1;
	for (int i = 2; i <= k; i++) {
		if (i <= r) {
			d[i] = min(d[r - i + l], r - i + 1);
			res = max(res, d[i]);
		}
		while (s[i - d[i]] == s[i + d[i]]) {
			d[i]++;
			res = max(res, d[i]);
		}
		if (i + d[i] - 1 > r) {
			l = i - d[i] + 1;
			r = i + d[i] - 1;
		}
	}
	cout << res - 1;
	return 0;
}

也可看洛谷的模板题

P3805 【模板】manacher 算法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2.2e7 + 5;
char a[N], s[N];
int d[N];

int main() {
	scanf("%s", &a);
	int n = strlen(a);
	int k = 0;
	s[0] = '$';
	s[++k] = '#';
	for (int i = 0; i < n; i++) {
		s[++k] = a[i];
		s[++k] = '#';
	}
	d[1] = 1;
	int l, r = 1;
	int res = -1;
	for (int i = 2; i <= k; i++) {
        //在盒内有两种情况
        //1.d[r-i+l]<r-i+1	对称点且还在盒内
        //d[i] = d[r-i+l]
        //2.d[r-i+l]>=r-i+1 对称点在盒外
        //令d[i]=r-i+1,从r+1往后暴力枚举
		if (i <= r) {
			d[i] = min(d[r - i + l], r - i + 1);
        }
		while (s[i + d[i]] == s[i - d[i]]) {
			d[i]++;
            res = max(res, d[i]);
		}
		if (i + d[i] - 1 > r) {
			l = i - d[i] + 1;
			r = i + d[i] - 1;
		}
	}
	printf("%d", res - 1);
	return 0;
}

数据结构

单链表

tot相当于一个分配器，如果需要加入新的结点就用tot++分配出一个下标

826. 单链表 - AcWing题库

#include<iostream>
using namespace std;

const int N = 1e5 + 5;

int head = -1, e[N], ne[N], tot = 1;

//头插
void insert_head(int x) {
	e[tot] = x;
	ne[tot] = head;
	head = tot++;
}
//删除,让第k个结点的下一位直接指向下一个结点的下一位
void delete_k(int k) {
	ne[k] = ne[ne[k]];
}

void insert_x(int k, int x) {
	e[tot] = x;
	ne[tot] = ne[k];
	ne[k] = tot++;
}

int main() {
	
	int m;
	cin >> m;
	while (m--) {
		char op;
		cin >> op;
		if (op == 'H') {
			int x;
			cin >> x;
			insert_head(x);
		}
		else if (op == 'D') {
			int k;
			cin >> k;
            //删除头结点
			if (k == 0) {
				head = ne[head];
			}
			else {
				delete_k(k);
			}
		}
		else {
			int k, x;
			cin >> k >> x;
			insert_x(k, x);
		}
	}
	for (int i = head; ~i; i = ne[i]) {
		cout << e[i] << " ";
	}
	return 0;
}

双链表

827. 双链表 - AcWing题库

#include<iostream>
#include<string>
using namespace std;

const int N = 1e5 + 5;
int l[N], r[N], e[N], tot;

//第k个数的右边进行插入
void insert_x(int k, int x) {
	e[tot] = x;
	r[tot] = r[k];
	l[tot] = k;
	l[r[k]] = tot;
	r[k] = tot++;
}

void remove_k(int k) {
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

int main() {
    //头指针	//尾指针
	r[0] = 1, l[1] = 0;
    //tot从2开始,注意此时的"第k个数"
	tot = 2;
	int m;
	cin >> m;
	while (m--) {
		string op;
		cin >> op;
		int k, x;
		if (op == "L") {
			cin >> x;
			insert_x(0, x);
		}
		else if (op == "R") {
			cin >> x;
			insert_x(l[1], x);
		}
		else if (op == "D") {
			cin >> k;
			remove_k(k + 1);
		}
		else if (op == "IL") {
			cin >> k >> x;
			insert_x(l[k + 1], x);
		}
		else {
			cin >> k >> x;
			insert_x(k + 1, x);
		}
	}
	for (int i = r[0]; i != 1; i = r[i]) {
		cout << e[i] << " ";
	}
	return 0;
}

栈

#include<iostream>
using namespace std;
const int N = 1e5 + 5;

int stk[N], tt;

int main() {
	int m;
	cin >> m;
	while (m--) {
		string s;
		cin >> s;
		int x;
		if (s == "push") {
			cin >> x;
			stk[++tt] = x;
		}
		else if (s == "pop") {
			tt--;
		}
		else if (s == "empty") {
			if (tt > 0) {
				cout << "NO" << endl;
			}
			else {
				cout << "YES" << endl;
			}
		}
		else {
			cout << stk[tt] << endl;
		}
	}
	return 0;
}

队列

829. 模拟队列 - AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5 + 5;

int que[N], hh, tt = -1;

int main() {
	int m;
	cin >> m;
	while (m--) {
		string s;
		cin >> s;
		if (s == "push") {
			int x;
			cin >> x;
			que[++tt] = x;
		}
		else if (s == "pop") {
			hh++;
		}
		else if (s == "empty") {
			if (hh <= tt) {
				cout << "NO" << endl;
			}
			else {
				cout << "YES" << endl;
			}
		}
		else {
			cout << que[hh] << endl;
		}
	}
	return 0;
}

单调栈

Q: 为什么要保持栈内元素大小的单调递增特性？
A: 由于栈内元素是递增的，所以比较次数一定是最少的，这就实现了优化。
Q: 如何保持栈内元素大小的递增性？
A: 在依次出栈比较栈顶元素和当前数组元素大小的时候，如果栈顶元素小，那么找到目标值，将当前数组元素入栈，这样保持了栈内元素大小的递增性；如果栈顶元素大，那么栈顶指针左移，直到找到目标值，再将当前数组元素入栈，这样就保持了栈内元素大小的递增性。我们不必在意这个过程破坏了栈的结构，因为之前的数已经找到之前数组元素对应的目标值了。

P5788 【模板】单调栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>

using namespace std;
const int N = 3e6 + 5;
int a[N];
int b[N];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	stack<int> st;
	for (int i = 0; i < n; i++) {
		while (!st.empty() && a[i] > a[st.top()]) {    //当前数字比栈顶元素大，下标加入b数组，弹出栈顶元素
			b[st.top()] = i + 1;
			st.pop();
		}
		st.push(i);
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", b[i]);
	}
	return 0;
}

例题

描述：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2

#include<bits/stdc++.h>
using namespace std;

const int N = 3e6 + 5;
int a[N];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	a[n] = 0x7fffffff;	//保证最后的人数被加上
	int sum = 0;
	stack<int> st;
	for (int i = 0; i <= n; i++) {
		while (!st.empty() && a[i] > a[st.top()]) {
			sum += i - st.top() - 1;
			st.pop();
		}
		st.push(i);
	}
	cout << sum;
}

830. 单调栈 - AcWing题库

#include<iostream>
using namespace std;

const int N = 1e5 + 5;
int stack[N], tt;

int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int x;
		scanf("%d", &x);
		//栈中有元素且栈顶元素的值比x大,栈顶指针tt--
		while (tt && stack[tt] >= x) {
			tt--;
		}
		if (tt) {
			cout << stack[tt] << " ";
		}
		else {
			cout << -1 << " ";
		}
		stack[++tt] = x;
	}
	return 0;
}

单调队列

“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理

主要用于解决滑动窗口类问题

可以参考知乎上的解答：算法学习笔记(66): 单调队列 - 知乎 (zhihu.com)

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

//滑动窗口左边为队头，右边为队尾


#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, k;
deque<ll> dq;
ll a[N];

//滑动窗口最小值
void min_de() {
	for (int i = 0; i < n; i++) {
		if (!dq.empty() && i - dq.front() >= k)  //窗口的左边没在窗口后，将队头弹出
			dq.pop_front();
		while (!dq.empty() && a[i] < a[dq.back()])	//当前数比队列的最后一位小的时候，弹出队尾元素
			dq.pop_back();
		dq.push_back(i);
		if (i >= k - 1)		//只有当滑动窗口在第k个才输出最小值
			cout << a[dq.front()] << " ";
	}
}

//滑动窗口最大值
void max_de() {
	for (int i = 0; i < n; i++) {
		if (!dq.empty() && i - dq.front() >= k)
			dq.pop_front();
		while (!dq.empty() && a[i] > a[dq.back()])
			dq.pop_back();
		dq.push_back(i);
		if (i >= k - 1)		//只有当滑动窗口在第k个才输出最大值
			cout << a[dq.front()] << " ";
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	min_de();
	cout << endl;
	dq.clear();		//清空队列
	max_de();
	return 0;
}

使用数组来模拟

//认为 head <= tail 时，队列不为空，head初始化为0，tail初始化为-1
//左为head,右为tail

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int a[N];
int que[N], head, tail = -1;
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
    //最小
	for (int i = 0; i < n; i++) {
		if (head <= tail && i - que[head] >= k) { //不在窗口内的弹出，队头指针++
			head++;
		}
		while (head <= tail && a[que[tail]] > a[i]) {  //a[i] 比队列尾小，把队列尾弹出,队尾指针--
			tail--;
		}
		que[++tail] = i;
		if (i >= k - 1) {
			cout << a[que[head]] << " ";
		}
	}
	cout << endl;
	memset(que, 0, sizeof(que));
	head = 0;
	tail = -1;
    //最大
	for (int i = 0; i < n; i++) {
		if (head <= tail && i - que[head] >= k) {
			head++;
		}
		while (head <= tail && a[que[tail]] < a[i]) {
			tail--;
		}
		que[++tail] = i;
		if (i >= k - 1) {
			cout << a[que[head]] << " ";
		}
	}
	return 0;
}

KMP

算法学习笔记(13): KMP算法 - 知乎 (zhihu.com)

831. KMP字符串 - AcWing题库

暴力做法

#include<iostream>
#include<string>
using namespace std;
const int N = 1e6 + 5;
char a[N], b[N];
int main() {
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	string p;
	cin >> p;
	int m;
	cin >> m;
	string s;
	cin >> s;
	int t = 0;
	for (int i = 0; i < m - n + 1; i++) {
		int flag = 0;
		for (int j = 0; j < n; j++) {
			if (s[i + j] != p[j]) {
				flag = 1;
			}
		}
		if (flag) {
			continue;
		}
		else {
			cout << i << " ";
		}
	}
	return 0;
}

KMP算法

时间复杂度：O(n+m)

#include<iostream>
using namespace std;

const int N = 1e5 + 5, M = 1e6 + 5;
char p[N], s[M];
int ne[N];	//后缀与前缀相同时的最大长度,ne数组的下标从1开始

int main() {
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> p + 1 >> m >> s + 1;
	for (int i = 2, j = 0; i <= n; i++) {
		//当模式串不为第一个且第i个和第j+1个不相等时,找j的ne[j]
		while (j && p[i] != p[j + 1]) {
			j = ne[j];
		}
		if (p[i] == p[j + 1]) {
			j++;
		}
		ne[i] = j;
	}
	for (int i = 1, j = 0; i <= m; i++) {
		while (j && s[i] != p[j + 1]) {
            ////j与最大长度相等,可以想成此时的模式串中的下标其实就是最大的那个长度
            //此时 1 ~ j 与 i-j+1 ~ i是一样的
			j = ne[j];
		}
		if (s[i] == p[j + 1]) {
			j++;
		}
		if (n == j) {
			cout << i - n << " ";
			j = ne[j];
		}
	}
}

使用字符串哈希

#include<iostream>
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 5, M = 1e6 + 5, P = 131;
ll p[M], h[M];
char a[N], b[M];

ll search(int l, int r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
	int n, m;
	scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
	p[0] = 1;
	ll sum = 0;
    //算出模板串的哈希值
	for (int i = 1; i <= n; i++) {
		sum = sum * P + a[i];
	}
	for (int i = 1; i <= m; i++) {
		p[i] = p[i - 1] * P;
		h[i] = h[i - 1] * P + b[i];
	}
	for (int i = 1, j = n; j <= m; i++, j++) {
		if (search(i, j) == sum) {
			printf("%d ", i - 1);
		}
	}
	return 0;
}

Tire

835. Trie字符串统计 - AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
//son数组中的N不是代表数的深度,是代表结点
//son[x][y]代表第x个结点到达y字符对应的结点的编号
//tot保证了所有结点的唯一性
int son[N][26], cnt[N], tot;
char s[N];

void insert(char str[]) {
    //p相当于是第几个结点,son[p][u]相当于是编号为p的结点到达u的结点的下标(值表示目标结点的下标)
	int p = 0;
	for(int i=0; str[i];i++){
		int u = str[i] - 'a';
        //如果子结点不存在,新建一个结点
		if (!son[p][u]) son[p][u] = ++tot;
        //p指向子结点
		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.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	while (n--) {
		char c;
		cin >> c >> s;
		if (c == 'I') {
			insert(s);
		}
		else {
			cout << query(s) << endl;
		}
	}
	return 0;
}

143. 最大异或对 - AcWing题库

最大异或对

//异或的话与当前位不同能让异或值更大
//例如：若当前位是1，则选择0对应的结点，异或值能更大
//时间复杂度O(31*n)
#include<iostream>
using namespace std;

const int N = 1e5 + 5, M = 31 * N;
int son[M][2], tot;

void insert(int x) {
	int p = 0;
	for (int i = 30; i >= 0; i--) {
		int u = x >> i & 1;
		if (!son[p][u]) {
			son[p][u] = ++tot;
		}
		p = son[p][u];
	}
}

int query(int x) {
	int p = 0;
	int res = 0;
	for (int i = 30; i >= 0; i--) {
		int u = x >> i & 1;
        //与u相反的结点若存在,选在该结点
		if (son[p][!u]) {
			p = son[p][!u];
			res = (res << 1) + !u;
		}
        //否则走与u相同的结点
		else {
			p = son[p][u];
			res = (res << 1) + u;
		}
	}
	return res;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int res = -1;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		insert(x);
		int t = query(x);
		res = max(res, t ^ x);
	}
	cout << res;
	return 0;
}

并查集

题目链接,洛谷P1551

并查集

对于一个集合，秩指的就是这个集合中元素的个数。在并查集的合并操作中，如果我们将秩较小的集合合并到秩更大的集合上，那么比起将秩较大的集合合并到秩更小的集合上，在每一次查询操作中，前者总能花费更少的时间。

值得一提的是，按秩合并也被称为启发式合并。它是数据结构相关问题的一种重要思想，就是把“小的结构”合并到“大的结构”中，并且只增加“小的结构”的查询代价。所以在并查集中，我们把所有集合合并起来后，增加的总代价也不会超过NlogN。也就是说，单次查询的平均时间复杂度为O(logN)。

那么同时使用路径压缩和按秩合并的优化呢？如果我们这么做的话，单次查询操作的时间复杂度会变成一个奇怪的东西：O(α(N))。其中α(N)为反阿克曼函数，它是一个比logN增长得还要慢的函数。

import java.util.Scanner;

public class Main {
    static int[] f = new int[5005];
    static int[] size = new int[5005];
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int p = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            f[i] = i;
            size[i] = 1;
        }
        for (int i = 0; i < m; i++) {
            merge(scanner.nextInt(),scanner.nextInt());
        }
        for (int i = 0; i < p; i++) {
            if(find(scanner.nextInt()) != find(scanner.nextInt())){
                System.out.println("No");
            }else{
                System.out.println("Yes");
            }
        }
        scanner.close();
    }
    static int find(int x){
        if(x == f[x]){
            return x;
        }
        return f[x] = find(f[x]);		 //将每个元素都直接指向其父亲结点
    }
    static void merge(int x,int y){      //按秩合并
        int a = find(x);
        int b = find(y);
        if(size[a] <= size[b]){
            f[a] = b;
            size[b] += size[a];
        }else{
            f[b] = a;
            size[a] += size[b];
        }
    }
}

题目详情 - L2-013 红色警报 (pintia.cn)

//并查集的一个妙用，可以用来求联通区域的个数

#include<bits/stdc++.h>
using namespace std;
const int N = 505, M = 5005;
bool vis[N];
int e[M], ne[M];
int f[N];
int n, m;

int find(int x) {
	if (x == f[x]) {
		return x;
	}
	return f[x] = find(f[x]);
}

void merge(int x, int y) {
	int m = find(x);
	int n = find(y);
	f[m] = n;
}

void init() {
	for (int i = 0; i < n; i++) {
		f[i] = i;
	}
}

int count() {
	int counts = 0;
	for (int i = 0; i < n; i++) {
		if (find(i) == i) {
			counts++;
		}
	}
	return counts;
}

int main() {
	cin >> n >> m;
	init();
	for (int i = 0; i < m; i++) {
		cin >> e[i] >> ne[i];
		merge(e[i], ne[i]);
	}
	int k1 = count();
	int k;
	cin >> k;
	while (k--) {
		int t;
		cin >> t;
		vis[t] = true;
		init();
		for (int i = 0; i < m; i++) {
			if (!vis[e[i]] && !vis[ne[i]]) {
				merge(e[i], ne[i]);
			}
		}
		int k2 = count();
		if (k1 + 1 == k2 || k1 == k2) {
			cout << "City " << t << " is lost." << endl;
		}
		else {
			cout << "Red Alert: City " << t << " is lost!" << endl;
		}
		k1 = k2;
	}
	if (k1 == n) {
		cout << "Game Over.";
	}
	return 0;
}

带权并查集

240. 食物链 - AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int f[N], d[N];

//d[x]：x到父节点的距离
int find(int x) {
	if (x == f[x]) {
		return x;
	}
	int t = find(f[x]);
	d[x] += d[f[x]];
	f[x] = t;
	return f[x];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	int res = 0;
	while (k--) {
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if (x > n || y > n)res++;
		else {
			int fx = find(x), fy = find(y);
            //为同类时
			if (t == 1) {
                //父节点相同说明在同一颗树上
				if (fx == fy && (d[x] - d[y]) % 3 != 0)res++;
                //不相同说明在不同的树上
				else if (fx != fy) {
                    //合并
					f[fx] = fy;
					d[fx] = d[y] - d[x];
				}
			}
            //吃与被吃的关系时
			else {
                //父节点相同说明在同一颗树上
				if (fx == fy && (d[x] - d[y] - 1) % 3 != 0)res++;
                //不相同说明在不同的树上
				else if (fx != fy) {
                    //合并
					f[fx] = fy;
					d[fx] = d[y] - d[x] + 1;
				}
			}
		}
	}
	cout << res;
	return 0;
}

种类并查集

P1525关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 4e4 + 5, M = 1e5 + 5;
int f[N];

struct Node {
	int a;
	int b;
	int c;
}node[M];

int find(int x) {
	if (x == f[x]) {
		return x;
	}
	return f[x] = find(f[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		f[x] = y;
	}
}

bool cmp(Node a, Node b) {
	return a.c > b.c;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
    //1~n为朋友,n+1~2n为敌人
	for (int i = 1; i <= 2 * n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> node[i].a >> node[i].b >> node[i].c;
	}
	sort(node, node + m, cmp);
	for (int i = 0; i < m; i++) {
		int a = node[i].a;
		int b = node[i].b;
		int c = node[i].c;
        //当a,b两个朋友是敌人的时候，说明此时就是答案
		if (find(a) == find(b)) {
			cout << c;
			break;
		}
		merge(a, b + n);
		merge(b, a + n);
		if (i == m - 1) {
			cout << 0;
		}
	}
	return 0;
}

堆排序

838. 堆排序 - AcWing题库

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int h[N], siz;

void down(int x) {
    //t表示3个点中最小值的编号
	int t = x;
	//左儿子更小,t等于左儿子
	if (2 * x <= siz && h[2 * x] < h[t]) t = 2 * x;
	//右儿子更小,t等于右儿子
	if (2 * x + 1 <= siz && h[2 * x + 1] < h[t]) t = 2 * x + 1;
	if (t != x) {
		swap(h[x], h[t]);
		down(t);
	}
}

void up(int x) {
	while (x / 2 && h[x / 2] > h[x]) {
		swap(h[x / 2], h[x]);
		x /= 2;
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &h[i]);
	}
	siz = n;
	//从非叶子结点的最后一个开始进行堆调整,时间复杂度O(n)
	for (int i = n / 2; i >= 1; i--) {
		down(i);
	}
	while (m--) {
		cout << h[1] << " ";
        //根结点等于最后一个结点的值
		h[1] = h[siz--];
        //从第一个结点开始堆调整
		down(1);
	}
	return 0;
}

839. 模拟堆 - AcWing题库

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
//ph[x]数组表示插入的第x个数对应堆的下标
//hp[x]数组表示堆的下标为x的点对应插入的第几个数
int h[N], ph[N], hp[N], tot;

//接受两个数在h数组中的下标
void heap_swap(int a, int b) {
	swap(ph[hp[a]], ph[hp[b]]);
	swap(hp[a], hp[b]);
	swap(h[a], h[b]);
}

void up(int u) {
	while (u / 2 && h[u / 2] > h[u]) {
		heap_swap(u / 2, u);
		u /= 2;
	}
}

void down(int u) {
	int t = u;
	if (u * 2 <= tot && h[u * 2] < h[t]) t = u * 2;
	if (u * 2 + 1 <= tot && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
	if (u != t) {
		heap_swap(u, t);
		down(t);
	}
}

int main() {
	//m拿来记作第几个数
	int n, m = 0;
	scanf("%d", &n);
	while (n--) {
		char op[5];
		int k, x;
		scanf("%s", op);
		if (!strcmp(op, "I")) {
			scanf("%d", &x);
			m++;
			h[++tot] = x;
			ph[m] = tot, hp[tot] = m;
			up(tot);
		}
		else if (!strcmp(op, "PM")) {
			printf("%d\n", h[1]);
		}
		else if (!strcmp(op, "DM")) {
			heap_swap(1, tot--);
			down(1);
		}
		else if (!strcmp(op, "D")) {
			scanf("%d", &k);
			k = ph[k];
			heap_swap(k, tot--);
			up(k);
			down(k);
		}
		else {
			scanf("%d%d", &k, &x);
			k = ph[k];
			h[k] = x;
			up(k);
			down(k);
		}
	}
	return 0;
}

哈希表

840. 模拟散列表 - AcWing题库

拉链法(链地址法)

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;

int head[N], e[N], ne[N], tot;

void insert(int x) {
	int k = ((x % N) + N) % N;
	e[tot] = x;
	ne[tot] = head[k];
	head[k] = tot++;
}

bool find(int x) {
	int k = ((x % N) + N) % N;
	for (int i = head[k]; ~i; i = ne[i]) {
		if (e[i] == x) {
			return true;
		}
	}
	return false;
}

int main() {
	int n;
	scanf("%d", &n);
	memset(head, -1, sizeof head);
	while (n--) {
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		if (*op == 'I') {
			insert(x);
		}
		else {
			if (find(x)) {
				printf("Yes\n");
			}
			else {
				printf("No\n");
			}
		}
	}
	return 0;
}

开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
//定义null无穷大，说明此处没人
const int N = 200003, null = 0x3f3f3f3f;
int h[N];

int find(int x) {
	int t = ((x % N) + N) % N;
	while (h[t] != null && h[t] != x) {
		t++;
		//t等于N时，循环从0开始找
		if (t == N) {
			t = 0;
		}
	}
	return t;
}

int main() {
	memset(h, 0x3f, sizeof h);
	int n;
	scanf("%d", &n);
	while (n--) {
		char op[2];
		int x;
		scanf("%s %d", op, &x);
		int t = find(x);
		if (op[0] == 'I') {
			h[t] = x;
		}
		else {
			if (h[t] != null) {
				printf("Yes\n");
			}
			else {
				printf("No\n");
			}
		}
	}
	return 0;
}

字符串哈希

快速判断两个字符串是不是相等的时候
本质思想就是确保每个字符串的哈希是不一样的,避免哈希冲突,每个字符串对应唯一一个哈希值

841. 字符串哈希 - AcWing题库

假定人品足够好，不存在哈希冲突，每个字符串对应唯一一个哈希值
一般情况{
    P=131 或 13331
    Q=2^64
}

全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
对形如 X1X2X3⋯Xn−1XnX1X2X3⋯Xn−1Xn 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。

映射公式 (X1×Pn−1 + X2×Pn−2 +⋯+ Xn−1×P1 + Xn×P0) mod Q

求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。

前缀和公式 h[i+1] = h[i]×P+s[i] i∈[0,n−1]i∈[0,n−1] h为前缀和数组，s为字符串数组
区间和公式 h[l,r] = h[r] − h[l − 1] × P ^ (r−l+1)
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上 P² 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

#include<iostream>
using namespace std;

typedef unsigned long long ll;
//表示P进制的数
const int N = 1e5 + 5, P = 131;

char s[N];
ll h[N], p[N];

//朴素做法可以把从l到r进行累加求哈希，但为了简化运算，使用了前缀和，使查询时候的复杂度为O(1)
ll search(int l, int r) {
	return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	p[0] = 1;
	for (int i = 1; i <= n; i++) {
		h[i] = h[i - 1] * P + s[i];
		p[i] = p[i - 1] * P;
	}
	while (m--) {
		int l1, r1, l2, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (search(l1, r1) == search(l2, r2)) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}
	return 0;
}

动态规划

线性dp

普通dp

P1002 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;

int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
int vis[25][25];
long long int dp[25][25];

int main() {
	int n, m, x, y;
	cin >> n >> m >> x >> y;
    //防止数组越界,tips：马那有2
	n += 2;
	m += 2;
	x += 2;
	y += 2;
    //马控制的地方标记为1
	for (int i = 0; i < 8; i++) {
		vis[x + dx[i]][y + dy[i]] = 1;
	}
	vis[x][y] = 1;
	dp[2][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			if (!vis[i][j])
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			else
			    dp[i][j] = 0;
		}
	}
	cout << dp[n][m];
	return 0;
}

P2028 龙兄摘苹果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>

using namespace std;
typedef unsigned long long ll;
const int N = 10005;
ll dp[N][1005];

int main() {
	ios::sync_with_stdio(false);
	ll n, k, p;
	cin >> n >> k >> p;
    //前i-1个苹果放在前j个盘中，此时有：dp[i-1][j] * j种方案
    //前i-1个苹果放在前j-1个盘中，此时有：dp[i-1][j-1]种方案
	for (int i = 1; i <= n; i++) {
		dp[i][1] = 1;
		for (int j = 2; j <= k; j++) {
			dp[i][j] = (((dp[i - 1][j] % p) * (j % p)) % p + (dp[i - 1][j - 1] % p)) % p;
		}
	}
	cout << dp[n][k] % p;
	return 0;
}

898. 数字三角形 - AcWing题库

//可以从下往上思考，过程中一直选出最大的dp[i][j]，最终答案即为dp[1][1]

#include<bits/stdc++.h>
using namespace std;

const int N = 505;
int dp[N][N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> dp[i][j];
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);
		}
	}
	cout << dp[1][1];
	return 0;
}

LIS(最长上升子序列)

dp[i]：所有以第i个数为止，最长上升子序列的长度

[P1091 NOIP2004 提高组] 合唱队形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.普通方法，使用动态规划，时间复杂度n²

#include<bits/stdc++.h>

using namespace std;
int t[105];
int dp[2][105];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i];
	}
    //正向求最长上升子序列
	for (int i = 1; i <= n; i++) {
	    dp[0][i] = 1;
		for (int j = 1; j < i; j++) {
			if (t[j] < t[i]) {
				dp[0][i] = max(dp[0][i], dp[0][j] + 1);
			}
		}
	}
    //反向求最长上升子序列
	for (int i = n; i >= 1; i--) {
	    dp[1][i] = 1;
		for (int j = n; j > i; j--) {
			if (t[j] < t[i]) {
				dp[1][i] = max(dp[1][i], dp[1][j] + 1);
			}
		}
	}
	int maxx = -1;
    //以i为切割点求答案
	for (int i = 1; i <= n; i++) {
		maxx = max(dp[0][i] + dp[1][i], maxx);
	}
	cout << n - maxx + 1;	//重复减，应该加1
	return 0;
}

2.使用贪心+二分，时间复杂度nlogn

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;

int a[N];
int low[N];
int len;

int binary_search(int x) {
	int l = 1, r = len;
	while (l < r) {
		int mid = (l + r) >> 1;
        //尽量往左边找
		if (low[mid] >= x) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		low[i] = 0x7f7f7f7f;
	}
	low[1] = a[1];
	len = 1;
	for (int i = 2; i <= n; i++) {
		if (a[i] > low[len]) {
			low[++len] = a[i]; 
		}
		else {
			//找出上升子序列第一个>=a[i]的数，用a[i]将其替换
			low[binary_search(a[i])] = a[i];
		}
	}
	cout << len;
	return 0;
}

LCS(最长公共子序列)

[P2543 AHOI2004]奇怪的字符串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>

using namespace std;

const int N = 10005;
int dp[N][N];

int main() {
	string s1, s2;
	cin >> s1 >> s2;
	
	for (int i = 1; i <= s1.length(); i++) {
		for (int j = 1; j <= s2.length(); j++) {
			if (s1[i - 1] == s2[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	cout << dp[s1.length()][s2.length()];
	return 0;
}

01背包

如果除0外初始化为负无穷，那么仅刚好装下的位置是正数(从0加)，其余位置为负数(从负无穷加)，故需要枚举

1.二维数组

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[][] dp = new int[N + 1][V + 1];		//前N个物品在背包体积为V时的最大价值
        for (int i = 1; i <= N; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                if(v[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[N][V]);
        scanner.close();
    }
}

2.一维数组(滚动数组实现)

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] dp = new int[V + 1];
        for (int i = 1; i <= N; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            for (int j = V; j >= v[i]; j--) { 
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[V]);
        scanner.close();
    }
}

完全背包

可以理解成第i层的结果，因为每个物品都是无限的，所以要用第i层的结果使值最大，要使用前面更新的状态，前面的状态可能是选了的，也可能没选第i个物品

f[i,j] = max(f[i-1,j],  f[i-1][j-v[i]]+w[i],f[i-1][j-2v[i]]+2w[i],f[i-1][j-3v[i]]+3w[i]······)
f[i,j-v[i]] = max(		f[i-1][j-v[i]],     f[i-1][j-2v[i]]+w[i], f[i-1][j-3v[i]]+2w[i]······)
    
f[i,j] = max(f[i-1,j],f[i][j-v[i]+w[i]]);

1.二维数组

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[][] dp = new int[N + 1][V + 1];
        for (int i = 1; i <= N; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        //不取：dp[i-1][j]
        //取：dp[i][j-v[i]+w[i]]   物品数量是无限的
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                if(j < v[i])
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[N][V]);
        scanner.close();
    }
}

2.一维数组(滚动数组实现)

​ 通过覆盖原来的数组来实现更新

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        int[] v = new int[N + 1];
        int[] w = new int[N + 1];
        int[] dp = new int[V + 1];
        for (int i = 1; i <= N; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            for (int j = v[i]; j <= V; j++) { 
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[V]);
        scanner.close();
    }
}

多重背包

第i个物品数量为s[i]

f[i,j] = max(f[i-1,j],f[i-1][j-v[i]]+w[i],f[i-1][j-2v[i]]+2w[i],···,f[i-1][j-sv[i]]+sw[i])
    
f[i,j-v[i]] = max(	  f[i-1][j-v[i]],     f[i-1][j-2v[i]]+w[i],···, f[i-1][j-sv[i]]+sw[i],f[i-1][j-(s+1)v[i]+(s+1)w[i]])

模板题

4. 多重背包问题 I - AcWing题库

1.三重循环实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
int v[N], w[N], s[N], dp[N][N];
int main() {
	int n, V;
	cin >> n >> V;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i] >> s[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= V; j++) {
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
                			//取k个之间一直循环比较大小     //相当于取0个，取1个···取k个
			}
		}
	}
	cout << dp[n][V];
	return 0;
}

5. 多重背包问题 II - AcWing题库

2.使用二进制进行优化

#include<bits/stdc++.h>
using namespace std;

const int N = 12005;
int v[N], w[N];
int dp[N];

int main() {
	int n, V;
	cin >> n >> V;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		int k = 1;
		while (k <= c) {
			v[++ans] = k * a;
			w[ans] = k * b;
			c -= k;
			k *= 2;
		}
		if (c) {
			v[++ans] = c * a;
			w[ans] = c * b;
		}
	}
	n = ans;
	for (int i = 1; i <= n; i++) {
		for (int j = V; j >= v[i]; j--) {
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	cout << dp[V];
	return 0;
}

3.使用单调队列进行优化

6. 多重背包问题 III - AcWing题库

9.76 多重背包 单调队列优化——信息学竞赛培训课程_哔哩哔哩

这篇题解推荐一下

AcWing 6. 多重背包问题 III【单调队列优化+图示】 - AcWing

key:当k=j时为不取，只有当k=j+sv之后，滑动窗口才满，下一轮就开始滑动


#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
const int M = 2e4 + 5;

int dp[N][M];
int que[M];

int main() {
	int n, V;
	cin >> n >> V;
	for (int i = 1; i <= n; i++) {
		int v, w, s;
		cin >> v >> w >> s;
		//对物品体积求完全剩余系
		/*
		* 假设 v w s
		*      2 4 3
		*	   背包体积为9
		*  假设：
		* 		f[9] = 14 f[7]+4 = 14
		*		f[9] = 14 f[5]+8 = 13
		*		f[9] = 17 f[3]+12 =17
		* //一个窗口
		*		f[8] = 14 f[6]+4 = 14
		*		f[8] = 14 f[4]+8 = 13
		*		f[8] = 14 f[2]+12 =12
		* //一个窗口
		*		f[7] = 10 f[5]+4 = 9
		*		f[7] = 13 f[3]+8 = 13
		*		f[7] = 13 f[1]+12 =12
		* f数组是由对v取余相同的转换来的
		* f[j]  f[j+v]	f[j+2v] ...
		* 滑动窗口大小为s + 1,因为我们是拿窗口的下一个数来进行分析的
		*/
		for (int j = 0; j < v; j++) {  //分成v个不同余数的类
			int head = 0, tail = -1;
			for (int k = j; k <= V; k += v) {  //每个类使用单调队列
				//不在窗口(k-s*v,k-v)内，注意此时窗口大小实际为s+1,此时的k要比滑动窗口最右边大v个体积
                //不使用>=而使用>的理解：k=j时，是为不取第i个物品
				if (head <= tail && k - que[head] > s * v) {
					head++;
				}
				//比较是否比tail位置的大，tail的最大值应该为i-1个物品的最大加上此时第i个物品
				//dp[i - 1][que[tail]] + (k - que[tail]) / v * w
				while (head <= tail && dp[i - 1][k] > dp[i - 1][que[tail]] + (k - que[tail]) / v * w) {
					tail--;
				}
				que[++tail] = k;
				dp[i][k] = dp[i - 1][que[head]] + (k - que[head]) / v * w;
			}
		}
	}
	cout << dp[n][V];
	return 0;
}

分组背包

1.二维数组

#include<bits/stdc++.h>

using namespace std;
const int N = 105;
int v[N][N], w[N][N], s[N], dp[N][N];

int main() {
	int n, V;
	cin >> n >> V;
	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 = 0; j <= V; j++) {
		    dp[i][j] = dp[i-1][j];
			for (int k = 0; k < s[i]; k++) {
				if(v[i][k] <= j)
                    //要么都不选，要么就选其中的一个max
					dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
			}
		}
	}
	cout << dp[n][V];
	return 0;
}

2.优化到一维数组(滚动数组)

和01背包一样，为从后往前遍历，防止选重
    
#include<bits/stdc++.h>

using namespace std;
const int N = 105;
int v[N][N], w[N][N], s[N], dp[N];

int main() {
	int n, V;
	cin >> n >> V;
	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 = V; j >= 0; j--) {
			for (int k = 0; k < s[i]; k++) {
				if(v[i][k] <= j)
					dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
			}
		}
	}
	cout << dp[V];
	return 0;
}

混合背包

7. 混合背包问题 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int v, w, s;
		cin >> v >> w >> s;
        //01背包
		if (s == -1) {
			for (int j = m; j >= v; j--) {
				dp[j] = max(dp[j], dp[j - v] + w);
			}
		}
        //完全背包
		else if (s == 0) {
			for (int j = v; j <= m; j++) {
				dp[j] = max(dp[j], dp[j - v] + w);
			}
		}
        //多重背包，使用二进制进行优化
		else {
			int k = 1;
			while (k <= s) {
				for (int j = m; j >= k * v; j--) {
					dp[j] = max(dp[j], dp[j - k * v] + k * w);
				}
				s -= k;
				k *= 2;
			}
			if (s) {
				for (int j = m; j >= s * v; j--) {
					dp[j] = max(dp[j], dp[j - s * v] + s * w);
				}
			}
		}
	}
	cout << dp[m];
	return 0;
}

二维费用的背包

8. 二维费用的背包问题 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int dp[N][N];

int main() {
	int n, m, c;
	cin >> n >> m >> c;
	for (int i = 1; i <= n; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		for (int j = m; j >= a; j--) {
			for (int k = c; k >= b; k--) {
				dp[j][k] = max(dp[j][k], dp[j - a][k - b] + t);
			}
		}
	}
	cout << dp[m][c];
	return 0;
}

区间dp

树图

链式前向星

视频推荐,讲的很好的up主

//数组模拟链表
static Node[] Edge = new Node[10005];
static int[] Head = new int[100005];
static int tot;

class Node{
    int to;
    int w;
    int next;
}

static void addEdge(int u,int v,int w){
        Edge[tot].to = v;
        Edge[tot].w = w;
        Edge[tot].next = Head[u];
        Head[u] = tot++;
    }

搜索

深度优先搜索(DFS)

stack实现		空间O(h),与树高有关				不具有最短路性

846. 树的重心 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int head[2 * N], e[2 * N], ne[2 * N];
int tot;
int n, ans = N;
bool vis[2 * N];
//建图
void add(int u,int v) {
	e[tot] = v;
	ne[tot] = head[u];
	head[u] = tot++;
}
//返回以u为根的子树中结点的个数
int dfs(int u) {
	int sum = 1;//存储 以u为根的树的节点数, 包括u，如图中的4号节点
	int res = 0;//存储 删掉某个节点之后，最大的连通子图节点数
    //只搜索一次
	vis[u] = true;
	for (int i = head[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (!vis[j]) {
			int t = dfs(j);
            //比较以u为根节点下方的子树
			res = max(res, t);
			sum += t;
		}
	}
    //比较以u为根节点上方的子树
	res = max(res, n - sum);
	ans = min(ans, res);
	return sum;
}

int main() {
	cin >> n;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	dfs(1);
	cout << ans;
	return 0;
}

广度优先搜索(BFS)

queue实现		空间O(2^n),与树的一层元素数量有关	最短路

847. 图中点的层次 - AcWing题库

//树与图的广搜
    
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int d[N];
int head[N], e[N], ne[N], tot;
void add(int u, int v) {
	e[tot] = v;
	ne[tot] = head[u];
	head[u] = tot++;
}


int bfs() {
	int que[N];
	memset(d, -1, sizeof(d));
	int hh = 0, tt = 0;
	que[0] = 1;
	d[1] = 0;
    //数组模拟队列
	while (hh <= tt) {
		int j = que[hh++];
		for (int i = head[j]; ~i; i = ne[i]) {
			int t = e[i];
			if (d[t] == -1) {
				que[++tt] = t;
				d[t] = d[j] + 1;
			}
		}
	}
	return d[n];
}

int main() {
	cin >> n >> m;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	cout << bfs();
	return 0;
}

拓扑排序

848. 有向图的拓扑序列 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int d[N];
int head[N], e[N], ne[N], tot;
int que[N];
void add(int u, int v) {
	e[tot] = v;
	ne[tot] = head[u];
	head[u] = tot++;
}

bool tuopusort() {
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
            //入度为0的点入队
			que[++tt] = i;
		}
	}
	while (hh <= tt) {
		int t = que[hh++];
		for (int i = head[t]; ~i; i = ne[i]) {
			int j = e[i];
            //将t->j这条边删除，j的入度--
			d[j]--;
			if (d[j] == 0) {
				que[++tt] = j;
			}
		}
	}
	return tt == n - 1;
}

int main() {
	cin >> n >> m;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
		d[v]++; //v的入度++
	}
	if (tuopusort()) {
		for (int i = 0; i < n; i++) {
			cout << que[i] << " ";
		}
	}
	else {
		cout << -1;
	}
	return 0;
}

单源最短路问题

1.所有边权都是正数

1.朴素Dijkstra

849. Dijkstra求最短路 I - AcWing题库

//因为所有边权为正，若有自环的话,假设第t个点有自环，dis[t]一定是小于dist[t]+g[t][t]的

#include<bits/stdc++.h>
using namespace std;
const int N = 505;

int g[N][N];
int dist[N];
bool st[N];
int n, m;

int dijkstra() {
	dist[1] = 0;
	for (int i = 0; i < n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
            //所有st[j] = false的点中,dist[]最小的点
			if (!st[j] && (t == -1 || dist[t] > dist[j])) {
				t = j;
			}
		}
		st[t] = true;
		for (int j = 1; j <= n; j++) {
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
	if (dist[n] == 0x3f3f3f3f) {
		return -1;
	}
	else
		return dist[n];
}

int main() {
	cin >> n >> m;
    //邻接矩阵
	memset(g, 0x3f, sizeof(g));
    //存起始点到第i个点的最短路径
	memset(dist, 0x3f, sizeof(dist));
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
        //取重边中最小的那个
		g[a][b] = min(g[a][b], c);
	}
	cout << dijkstra();
	return 0;
}

2.堆优化Dijkstra

850. Dijkstra求最短路 II - AcWing题库

//时间复杂度O(mlogn),n表示点数量，m表示边,稀疏图,链式前向星

#include<bits/stdc++.h>
using namespace std;
const int N = 1.5e5 + 5;
typedef pair<int, int> PII;
int head[N], e[N], ne[N], w[N], tot;
int dist[N];
bool st[N];
int n, m;
void add(int u, int v, int c) {
	e[tot] = v;
	w[tot] = c;
	ne[tot] = head[u];
	head[u] = tot++;
}

int dijkstra() {
	priority_queue<PII, vector<PII>, greater<PII>> h;
	dist[1] = 0;
	h.push({ 0,1 }); //左为距离，右为结点，小顶堆先按距离排序
	while (!h.empty()) {
		auto t = h.top();
		h.pop();
		int ver = t.second;
		int distance = t.first;
		if (st[ver]) continue;
		st[ver] = true;
		for (int i = head[ver]; ~i; i = ne[i]) {
			int j = e[i];
			if (dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				h.push({ dist[j],j });
			}
		}
	}
	if (dist[n] == 0x3f3f3f3f) {
		return -1;
	}
	else
		return dist[n];
}

int main() {
	cin >> n >> m;
	memset(head, -1, sizeof head);
	memset(dist, 0x3f, sizeof dist);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	cout << dijkstra();
	return 0;
}

2.存在负权边

1.Bellman-Ford

松弛的含义可以看看这个的回答

存在负权边

//时间复杂度O(nm)
//n表示结点数，m为总边数
class Node{
    int u;
    int v;
    int w;
}
//第一次松弛操作经过一条边
//一次松弛,从源点不一定只经过一条边
//dis数组初始化为正无穷大
//对所有的边进行n-1轮松弛操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边
for (int i = 1; i < n; i++) {       //表示n-1个结点
        for (int j = 0; j < m; j++) {
            if(dis[v[j]] > dis[u[j]] + w[j])
                dis[v[j]] = dis[u[j]] + w[j]
        }
}
//n个点的时候,第一轮更新不超过1条边，第二轮更新不超过2条边···以此类推，从1~n个点中，最短的路径最多经过n-1条边
//tips:如果出现了负环,我们在第N轮操作的时候也会更新

853. 有边数限制的最短路 - AcWing题库

#include<bits/stdc++.h>
using namespace std;

const int N = 505, M = 1e4 + 5;
int n, m, k;
int dist[N], backup[N];

struct Node {
	int u, v, w;
}node[M];

int bellman_ford() {
	dist[1] = 0;
	for (int i = 0; i < k; i++) {
		memcpy(backup, dist, sizeof dist);  //防止串联
		for (int j = 0; j < m; j++) {
			int u = node[j].u, v = node[j].v, w = node[j].w;
			dist[v] = min(dist[v], backup[u] + w);
		}
	}
	if (dist[n] >= 0x3f3f3f3f / 2) {
		return 0x3f3f3f3f;
	}
	else {
		return dist[n];
	}
}

int main() {
	cin >> n >> m >> k; 
	for (int i = 0; i < m; i++) {
		cin >> node[i].u >> node[i].v >> node[i].w;
	}
	memset(dist, 0x3f, sizeof dist);
	int t = bellman_ford();
	if (t == 0x3f3f3f3f) {
		cout << "impossible";
	}
	else {
		cout << t;
	}
	return 0;
}

2.SPFA

//一般O(m),最坏O(nm)
//关于SPFA，它死了

多源最短路问题

Floyd算法

定义一个三维数组f[k][i][j] 表示从1到k这些点可以作为i到j的中间结点，选出一个k点作为i到j的中间结点,也可以不经过，可推到出状态转移方程，可想为01背包问题
    中间结点k选
    f[k-1][i][k]+f[k-1][k][j]
    中间结点k不选
    f[k-1][i][j]
    
状态转移方程为：
    f[k][i][j] = min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);

//时间复杂度O(n^3)
//n个点,计算u到v的最短距离
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[k][i][j] = Math.min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]);
        }
    }
}


//滚动数组优化
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
        }
    }
}

854. Floyd求最短路 - AcWing题库

#include<bits/stdc++.h>
using namespace std;

const int N = 205;
int n, m, k;
int dp[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++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				dp[i][j] = 0;
			}
			else {
				dp[i][j] = 0x3f3f3f3f;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		dp[x][y] = min(dp[x][y], z);
	}
	floyd();
	while (k--) {
		int x, y;
		cin >> x >> y;
		if (dp[x][y] >= 0x3f3f3f3f / 2) {
			cout << "impossible" << endl;
		}
		else {
			cout << dp[x][y] << endl;
		}
	}
	return 0;
}

打印路径

//pass数组初始化为-1，输入时将有边的pass设置为0,说明这两点之间可以连接
void floyed() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dp[i][j] > dp[i][k] + dp[k][j]) {
					dp[i][j] = dp[i][k] + dp[k][j];
					pass[i][j] = k;
				}
			}
		}
	}
}
void dfs(int i, int j) {
	if (i == j) {
		return;
	}
	if (pass[i][j] == 0) {
		cout << i << "->" << j << endl;
	}
	else {
		dfs(i, pass[i][j]);
		dfs(pass[i][j], j);
	}
}

//求3到1的路径
//pass数组初始化为：pass[i][j] = j,pass数组表示从i到j第一个经过的点
//pass[i][j] = pass[i][k]
for (int i = 0; i < r; i++) {
	int x, y, z;
	cin >> x >> y >> z;
	dp[x][y] = min(dp[x][y], z);	//防止重边
}
floyed();
int k = 3;
while (k != 1) {
	cout << k << "->";
	k = pass[k][1];
}
cout << k;

最小生成树

Prim算法

858. Prim算法求最小生成树 - AcWing题库

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 505, INF = 0x3f3f3f3f;
int g[N][N];
int n, m;
int dist[N];  //集合外的点到集合的最小距离
bool st[N];

int prim() {
	int ans = 0;
	dist[1] = 0;
	for (int i = 0; i < n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || dist[t] > dist[j])) {
				t = j;
			}
		}
		if (dist[t] == INF) {
			return INF;
		}
        //加入集合
		st[t] = true;
		ans += dist[t];
		for (int j = 1; j <= n; j++) {
			dist[j] = min(dist[j], g[t][j]);
		}
	}
	return ans;
}


int main() {
	cin >> n >> m;
	memset(dist, INF, sizeof dist);
	memset(g, INF, sizeof g);
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = min(g[u][v], w);
	}
	int t = prim();
	if (t == INF) {
		cout << "impossible";
	}
	else {
		cout << t;
	}
	return 0;
}

数学

扩展欧几里得算法

如果a，b是整数,那么一定存在整数x,y使得ax+by=gcd(a,b)
扩展欧几里得算法即是为了求出x,y
扩展欧几里得算法可以求同余方程以及逆元
本例通过递归加以实现
    根据欧几里得原理有 gcd(a,b)=gcd(b,a%b);
	即ax1 + by1 = bx2 + (a % b)y2;
	又因为a % b = a - (a / b) * b;
	-> ax1 + by1 = ay2 + b(x2 - (a / b)*y2;
    -> x1 = y2;
       y1 = x2 - (a / b)*y2;

static int x = -1;
static int y = -1;

public static int ex_gcd(int a,int b){
        if(b == 0){
            x = 1;
            y = 0;
            return a;
        }
        int r = ex_gcd(b,a%b);
        int temp = x;
        x = y;                  //通过公式推导本层与下层之间的关系
        y = temp - a / b * y;
        return r;               //返回gcd
    }

博弈论

Nim游戏

891. Nim游戏 - AcWing题库

先手制造一个相同的局面，让后手先动手，先手跟着他必胜
    
先手必胜状态：可以走到某一个后手必败的状态
先手必败状态：走不到任何一个后手必败的状态
    
a1^a2^···^an = 0  先手必败
    		 !=0  先手必胜
    
    
找到x的二进制表示中最高位的1，
假设它就存在于第i堆石子的二进制表示中。
那么我们只需要从第i堆石子中拿走A[i]-A[i]^x个石子
异或值就会变成A[1]^A[2]^……^(A[i]-(A[i]-A[i]^x))^……^A[n],=A[1]^A[2]^……^A[i]^x^……^A[n]

A[1]^A[2]^……^A[n]是等于x的。
所以上述的式子就等于x^x=0

所以当x≠0，该谁走了，这个人就一定可以把x变成0，再推给对手
对手不管怎么取，一定会再次把x变成非0（这个很好理解）
最后因为0^0^……^0=0，所以输掉的一定是对手。

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n;
    int res = 0;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        res^=x;
    }
    if(res){
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;
}

集合-Nim游戏

893. 集合-Nim游戏 - AcWing题库

AcWing 893. 集合-Nim游戏——有图有思路 - AcWing

• Post author: wenyu
• Post link: https://avereed.github.io/2022/03/13/%E7%AE%97%E6%B3%95/
• Copyright Notice: All articles in this blog are licensed under unless otherwise stated.