算法题训练

记录为了保研机试刷的题目

难度：🌕🌖🌗🌘🌚

目录

基础算法

🌕AcWing 785. 快速排序

原题链接
我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int arr[], int l, int r)
{
	if (l >= r) return;

	int p = arr[r];
	int i, j;
	for (i = l - 1, j = l; j <= r; j++)
	{
		if (arr[j] <= p)
		{
			swap(arr[i + 1], arr[j]);
			i++;
		}
	}
	quick_sort(arr, l, i - 1), quick_sort(arr, i + 1, r);
}

🌕AcWing 787. 归并排序

原题链接
我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void merge(int arr[], int l, int r)
{
	if (l >= r) return;

	int mid = l + r >> 1;
	merge(arr, l, mid), merge(arr, mid + 1, r);

	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
		if (arr[i] > arr[j]) tmp[k++] = arr[j++];
		else tmp[k++] = arr[i++];
	while (i <= mid) tmp[k++] = arr[i++];
	while (j <= r) tmp[k++] = arr[j++];

	for (int i = l; i <= r; i++)
		arr[i] = tmp[i - l];
}

🌗AcWing 788. 逆序对的数量

原题链接
我的代码

归并排序的思想，对于一次递归 (arr, left, right)，求解 数组 arr[left, right] 中逆序对的数量。

(arr, left, right) = (arr, left, mid) + (arr, mid + 1, right) + merge:

  1. 第一部分是区间左半的逆序对数量
  2. 第二部分是区间右半的逆序对数量
  3. 第三部分是合并两个升序区间计算得到的逆序对数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long long merge(int arr[], int left, int right)
{
	if (left >= right) return 0;

    // left and right
	int mid = left + right >> 1;
	long long res = merge(arr, left, mid) + merge(arr, mid + 1, right);

    // merge
	int* temp = new int[right - left + 1];
	int i = left, j = mid + 1, k = 0;
	while (i <= mid && j <= right)
		if (arr[i] <= arr[j]) temp[k++] = arr[i++];
		else { res += mid - i + 1; temp[k++] = arr[j++]; }
	while (i <= mid) temp[k++] = arr[i++];
	while (j <= right) temp[k++] = arr[j++];

	for (int i = left, j = 0; i <= right; i++, j++)
		arr[i] = temp[j];
	return res;
}

🌖AcWing 789. 数的范围

原题链接
我的代码

两种二分模板：

  1. 循环条件: while(l < r), 中值: mid = (l + r) >> 1, 迭代: l = mid + 1 || r = mid
    • 查找存在的数 x: 返回左端点的位置
    • 查找不存在的数 x: 返回应该插入的位置
  2. 循环条件: while(l < r), 中值: mid = (l + r + 1) >> 1, 迭代: l = mid || r = mid - 1
    • 查找存在的数 x: 返回右端点的位置
    • 查找不存在的数 x: 返回应该插入的位置的前一位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// template 1
int l = 1, r = n;
while (l < r)
{
	int mid = l + r >> 1;

	if (arr[mid] < k) l = mid + 1;
	else if (arr[mid] >= k) r = mid;
}

// template 2
int l = 1, r = n;
while (l < r)
{
	int mid = l + r + 1 >> 1;

	if (arr[mid] <= k) l = mid;
	else if (arr[mid] > k) r = mid - 1;
}

🌕AcWing 791. 高精度加法

原题链接
我的代码

模板见 高精度除法。

🌕AcWing 792. 高精度减法

原题链接
我的代码

模板见 高精度除法。

🌕AcWing 793. 高精度乘法

原题链接
我的代码

模板见 高精度除法。

🌕AcWing 794. 高精度除法

原题链接
我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class BigNumber
{
public:
    vector<int> nums;
    bool flag;

    BigNumber operator+(BigNumber other) 
    {
        vector<int> A = this->nums;
        vector<int> B = other.nums;

        if (*this < other) swap(A, B);

        vector<int> C;
        int i, t;
        for (i = 0, t = 0; i < A.size(); i++)
        {
            t = A[i] + t;
            if (i < B.size()) t += B[i];
            C.push_back(t % 10);
            if (t >= 10) t = 1;
            else t = 0;
        }
        if (t == 1) C.push_back(1);
        return BigNumber(C);
    }
    BigNumber operator-(BigNumber other)
    {
        vector<int> A = this->nums;
        vector<int> B = other.nums;
        bool flag = true;

        if (*this < other) { swap(A, B); flag = false; }

        vector<int> C;
        int i, t;
        for (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();
        this->nums = C;
        return BigNumber(C, flag);
    }
    BigNumber operator*(BigNumber other) 
    {
        vector<int> A = this->nums;
        vector<int> B = other.nums;

        vector<int> C(A.size() + B.size(), 0);

        for (int i = 0; i < A.size(); i++)
            for (int j = 0; j < B.size(); j++)
                C[i + j] += A[i] * B[j];

        for (int i = 0; i < (int)C.size() - 1; i++)
            C[i + 1] += C[i] / 10, C[i] %= 10;

        while (C.size() > 1 && C.back() == 0) C.pop_back();
        return BigNumber(C);
    }
    BigNumber operator/(BigNumber other)
    {
        if (*this < other) return BigNumber({ 0 });

        vector<int> A = this->nums;
        vector<int> B = other.nums;
        vector<int> C;

        BigNumber remainder({ 0 });

        for (int i = A.size() - 1; i >= 0; i--) {
            remainder.nums.insert(remainder.nums.begin(), A[i]);
            while (remainder.nums.size() > 1 && remainder.nums.back() == 0) {
                remainder.nums.pop_back();
            }

            int digit = 0;
            BigNumber temp = other;
            while (remainder >= temp) {
                remainder = remainder - temp;
                digit++;
            }
            C.push_back(digit);
        }

        reverse(C.begin(), C.end());
        while (C.size() > 1 && C.back() == 0) C.pop_back();

        return BigNumber(C);
    }
    bool operator>=(BigNumber& other)
    {
        return !(*this < other);
    }
    bool operator<=(BigNumber& other)
    {
        return !(*this > other);
    }
    bool operator>(BigNumber& other)
    {
        vector<int> A = this->nums;
        vector<int> B = other.nums;

        if (A.size() != B.size())
            return A.size() > B.size();

        for (int i = (int)A.size() - 1; i >= 0; i--)
        {
            if (A[i] != B[i])
                return A[i] > B[i];
        }
        return false;
    }
    bool operator<(BigNumber& other)
    {
        vector<int> A = this->nums;
        vector<int> B = other.nums;

        if (A.size() != B.size())
            return A.size() < B.size();

        for (int i = (int)A.size() - 1; i >= 0; i--)
        {
            if (A[i] != B[i])
                return A[i] < B[i];
        }
        return false;
    }
    bool operator==(BigNumber& other)
    {
        return this->nums == other.nums;
    }

    BigNumber() : flag(true) {}
    BigNumber(vector<int> nums) : nums(nums), flag(true) {}
    BigNumber(vector<int> nums, bool flag) : nums(nums), flag(flag) {}
    BigNumber(string str)
    {
        flag = true;
        if (str[0] == '-')
        {
            flag = false;
            str.erase(str.begin());
        }

        for (int i = (int)str.size() - 1; i >= 0; i--) 
            nums.push_back(str[i] - '0');
    }
    BigNumber(int num) : flag(true)
    {
        while (num)
        {
            nums.push_back(num % 10);
            num /= 10;
        }
    }
};

ostream& operator<<(ostream& os, BigNumber big) {
    if (!big.flag) os << "-";
    for (int i = big.nums.size() - 1; i >= 0; i--)
        os << big.nums[i];
    return os;
}

🌖AcWing 795. 前缀和

原题链接
我的代码

核心逻辑: 一维前缀和

1
2
3
4
5
6
int main()
{
	// ...
	for (int i = 1; i <= n; i++)
        sum[i] += sum[i - 1];
}

🌖AcWing 796. 子矩阵的和

原题链接
我的代码

核心逻辑: 二维前缀和。

1
2
3
4
5
6
int main()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}

🌖AcWing 797. 差分

原题链接
我的代码

数组 A 的差分数组 B: B[0] = A[0], B[i] = A[i] - A[i - 1]。

对于 [l, r] 区间内的数加上 c，对于差分数组的改变只有两个端点: A[l] += c, A[r + 1] -= c

差分恢复成原来数组只需要求前缀和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main
{
	// 计算差分
	brr[0] = arr[0];
	for (int i = 1; i < n; i++)
		brr[i] = arr[i] - arr[i - 1];

	// 处理 (l, r, c) 操作
	for (int i = 0; i < m; i++)
	{
		int l, r, c;
		cin >> l >> r >> c;

		brr[l] += c;
		brr[r + 1] -= c;
	}
	 
	// 求前缀和将差分恢复为原数组
	for (int i = 1; i < n; i++)
		brr[i] += brr[i - 1];
}

🌖AcWing 798. 差分矩阵

原题链接
我的代码

数组 A 的差分数组 B: B[i][j] = A[i][j] - A[i - 1][j] - A[i][j - 1] + A[i - 1][j - 1]。

对于 [x1, y1] -> [x2, y2] 区间内的数加上 c，差分数组的改变只有四个端点: B[x1][y1] += c, B[x1][y2 + 1] -= c, B[x2 + 1][y1] -= c, B[x2 + 1][y2 + 1] += c。

差分恢复成原来数组只需要求前缀和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	// ...
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			B[i][j] = A[i][j] - A[i - 1][j] - A[i][j - 1] + A[i - 1][j - 1];

	while (q--)
	{
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;

		B[x1][y1] += c;
		B[x1][y2 + 1] -= c;
		B[x2 + 1][y1] -= c;
		B[x2 + 1][y2 + 1] += c;
	}
}

🌖AcWing 799. 最长连续不重复子序列

原题链接
我的代码

双指针思想，l, r 指向当前区间的左右两端，每次循环 r++：

  1. 若 num[r] 未重复，则继续
  2. 若 num[r] 重复，则 l++ 直至 num[r] 未重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
    // ...

    int l = 0, r = 0, res = 0;
    for (int r = 0; r < n; r++)
    {
        // st[i] = true => i 出现在区间里
    	if (st[num[r]])
    	{
    		while (num[l] != num[r]) { st[num[l++]] = false; }
    		l++;
    	}
    	else st[num[r]] = true;
    	res = max(res, r - l + 1);
    }
}

🌖AcWing 800. 数组元素的目标和

原题链接
我的代码

双指针思想: i 指向 A 头部, j 指向 B 尾部

  1. A[i] + B[j] > t => j--
  2. A[i] + B[j] < t => i++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	// ...
    int i = 0, j = m - 1;
    while (i < n && j >= 0)
    {
        int res = A[i] + B[j];
        
        if (res == t)
        {
            cout << i << " " << j << endl;
            break;
        }
        
        if (res > t) j--;
        else i++;
    }
}

🌖AcWing 2816. 判断子序列

原题链接
我的代码

略。

1
2
3
4
5
6
7
8
9
10
int main()
{
	// ...
	int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) i++;
        j++;
    }
}

🌕AcWing 801. 二进制中1的个数

原题链接
我的代码

运用位运算的思想。

1
2
3
4
5
6
7
8
9
10
11
int main()
{
	// ...
	int res = 0;
	while (arr[i])
	{
		if (arr[i] & 1) res++;
		arr[i] >>= 1;
	}
	cout << res << " ";
}

🌗AcWing 802. 区间和

我的代码
原题链接

核心逻辑：10^9 长度的区间，实际有值的点只有 10^5 个，采取离散化思路。

步骤：

  1. 有值的点是 1, 3, 100, 90000，将其映射到 0, 1, 2, 3
  2. 输入区间 4, 180，找到最后一个比该值小的数 (4-1) => 3, 180 => 100
  3. 映射: 3 => 1, 100 => 2
  4. 通过前缀和计算: sum[2] - sum[1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
vector<int> nums, relations;

int find(int x)
{
	auto it = upper_bound(relations.begin(), relations.end(), x);
	return it - relations.begin() - 1;
}

int main()
{
	int n, m, x, c;
	cin >> n >> m;

	map<int, int> map1;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> c;
		if (map1[x]) map1[x] += c;
		else map1[x] = c;
	}

	int cnt = 0;
	for (auto it = map1.begin(); it != map1.end(); it++, cnt++)
	{
		relations.push_back(it->first);
		nums.push_back(it->second);
	}

	for (int i = 1; i < nums.size(); i++)
		nums[i] += nums[i - 1];

	for (int i = 0; i < m; i++)
	{
		int l, r;
		cin >> l >> r;

		l = find(l - 1), r = find(r);

		int nl = l < 0 ? 0 : nums[l], nr = r < 0 ? 0 : nums[r];
		cout << nr - nl << endl;
	}
	return 0;
}

🌖AcWing 836. 合并集合

原题链接
我的代码

并查集的核心要素：

  1. father[N]: father[i] 为 i 的父节点的下标
  2. find(x): 查找 x 的父节点
  3. merge(x, y): 合并 x 和 y 所在的两个集合
1
2
3
4
5
6
7
8
9
10
int find(int x)
{
	if (father[x] == x)return x;
	return father[x] = find(father[x]);
}

void merge(int a, int b)
{
	father[find(a)] = find(b);
}

🌖AcWing 837. 连通块中点的数量

原题链接
我的代码

在并查集的基础上记录每个根节点的集合内元素数目即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
int find(int x)
{
	if (father[x] == x)
		return x;
	return father[x] = find(father[x]);
}

void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	if (fx != fy)num[fy] += num[fx];
	father[fx] = fy;
}

🌘AcWing240. 食物链

原题链接
我的代码

核心逻辑: 利用并查集，维护某个动物到根动物的 距离 d。

  1. d % 3 == 0: 说明该动物和根动物是同一种生物
  2. d % 3 == 1: 说明该动物吃根动物
  3. d % 3 == 2: 说明该动物被根动物吃
1
2
3
4
5
6
7
8
9
10
11
12
13
const int N = 50010;
int f[N], d[N];

int find(int n)
{
	if (f[n] != n)
	{
		int p = find(f[n]);
		d[n] += d[f[n]];
		f[n] = p;
	}
	return f[n];
}

🌖AcWing 803. 区间合并

原题链接
区间合并

核心逻辑: 将区间按照左端点升序排序，逐个判断合并后的区间最右端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{	
	// ...
	sort(nums.begin(), nums.end(), compare);

    int curR = -1e9-1, res = 0;
    for (int i = 0; i < n; i++)
    {
        res += nums[i].first > curR;
        curR = max(curR, nums[i].second);
    }
    cout << res << endl;
}

数据结构

🌕AcWing 828. 模拟栈

原题链接
我的代码

略。

🌗AcWing 3302. 表达式求值

原题链接
我的代码

三个步骤：

  1. 字符串式中缀表达式转成字符串数组中缀表达式
  2. 中缀表达式转成后缀表达式
  3. 通过后缀表达式求表达式值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// 1. 字符串式中缀表达式转成字符串数组中缀表达式
vector<string> split(string expr)
{
	vector<string> strs;
	for (int i = 0; i < expr.size(); i++)
	{
		string str = "";
		if (isdigit(expr[i]))
		{
			while (i < expr.size() && isdigit(expr[i]))
			{
				str += expr[i];
				i++;
			}
			strs.push_back(str);
		}
		if (i < expr.size())
		{
			str = expr[i];
			strs.push_back(str);
		}
	}
	return strs;
}


bool priority(string left, string right)
{
	if (left == "(" || right == "(") return false;
	if (left == "*" || left == "/") return true;
	if (left == "+" || left == "-") return right == "+" || right == "-";
}

// 2. 中缀表达式转成后缀表达式
void middle2back(vector<string>& strs)
{
	stack<string> s;

	vector<string> new_strs;

	for (int i = 0; i < strs.size(); i++)
	{
		if (isdigit(strs[i][0]))
		{
			new_strs.push_back(strs[i]);
		}
		else
		{
			if (strs[i] == "(") { s.push("("); }
			else if(strs[i] == ")")
			{
				while (s.top() != "(")
				{
					new_strs.push_back(s.top());
					s.pop();
				}
				s.pop();
			}
			else
			{
				while (!s.empty() && priority(s.top(), strs[i]))
				{
					new_strs.push_back(s.top());
					s.pop();
				}
				s.push(strs[i]);
			}
		}
	}

	while (!s.empty())
	{
		new_strs.push_back(s.top());
		s.pop();
	}
	strs = new_strs;
}

// 3. 通过后缀表达式求表达式值
int calculate(vector<string> strs)
{
	stack<int> s;
	for (int i = 0; i < strs.size(); i++)
	{
		if (isdigit(strs[i][0]))
		{
			s.push(stoi(strs[i]));
		}
		else
		{
			int num1 = s.top(); s.pop();
			int num2 = s.top(); s.pop();
			if (strs[i] == "+") s.push(num2 + num1);
			else if (strs[i] == "-") s.push(num2 - num1);
			else if (strs[i] == "*") s.push(num2 * num1);
			else if (strs[i] == "/") s.push(num2 / num1);
		}
	}

	return s.top();
}

🌕AcWing 829. 模拟队列

原题链接
我的代码

略。

🌖AcWing 830. 单调栈

原题链接
我的代码

单调队列，可以用 stack 辅助实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 以升序栈为例
class MonotoneStack
{
public:
	stack<int> s;

    // 核心逻辑：保证栈从底到顶是升序的，插入元素时，如果栈顶元素大于当前元素则出栈。
	int push(int k)
	{
		while (!s.empty() && s.top() >= k)
			s.pop();
		
		int res = s.empty() ? -1 : s.top();
		s.push(k);

		return res;
	}
};

🌖AcWing 154. 滑动窗口

原题链接
我的代码

单调队列，可以用 deque 辅助实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 以维护最大值为例
class MonotoneQueue
{
public:
	deque<int> nums;

	void push(int num)
	{
        // 核心逻辑：当 i < j && arr[i] < arr[j] 时，保留 arr[i] 没有意义。 
        // 此处注意不能写成 <=，因为有可能 push arr[j] 时，将 arr[i] 剔除，pop arr[i] 时，将 arr[j] 剔除。
		while (!nums.empty() && nums.front() < num)
			nums.pop_front();

		nums.push_front(num);
	}

	void pop(int num)
	{
        // 核心逻辑：如果 num 不是最大值，则一定被其后面更大的值剔除掉。
		if (nums.back() == num)
			nums.pop_back();
	}
};

🌖AcWing 835. Trie字符串统计

原题链接
我的代码

核心逻辑: 一棵树，每个节点是一个字符。

适用场景: 在字符种类少的情况下，快速查找指定字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int N = 100010;
int son[N][26], cnt[N], idx = 0;

void insert(string str)
{
    int p = 0;
    for (auto c : str)
    {
        int u = c - 'a';
        if (!son[p][u]) son[p][u] = ++idx;

        p = son[p][u];
    }
    cnt[p]++;
}

int query(string str)
{
    int p = 0;
    for (auto c : str)
    {
        int u = c - 'a';
        if (!son[p][u]) return 0;

        p = son[p][u];
    }
    return cnt[p];
}

🌗AcWing 143. 最大异或对

原题链接
我的代码

核心逻辑: 将十进制数以二进制串的形式存成 Trie 树，O(n) 的复杂度遍历所有整数，尽可能在 Trie 树中反方向走找到最大的异或结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N = 100010;
int A[N], son[N * 31][2], idx = 0;

void insert(int n)
{
	int p = 0;
	for (int i = 31; i >= 0; i--)
	{
		bool u = n & (1 << i);
		if (!son[p][u]) son[p][u] = ++idx;

		p = son[p][u];
	}
}

long long search(int n)
{
	int p = 0;
	long long res = 0;
	for (int i = 31; i >= 0; i--)
	{
		bool u = !(n & (1 << i));
		if (son[p][u]) { res += pow(2, i); p = son[p][u]; }
		else { p = son[p][!u]; }
	}
	return res;
}

🌕AcWing 840. 模拟散列表

原题链接
我的代码

略。

1
2
3
4
5
6
7
8
9
10
11
switch (op)
{
case 'I':
	map[x] = true;
	break;
case 'Q':
	cout << (map[x] ? "Yes" : "No") << endl;
	break;
default:
	break;
}

🌗AcWing 841. 字符串哈希

原题链接
我的代码

核心逻辑：把字符串视作一个 P 进制数 (P = 131)，利用前缀和快速求解任意子串对应 P 进制数的值。

例子：字符串 ABCD

  1. 前缀和数组 h[0] = 0, h[1] = hash("A"), h[2] = hash("AB"), h[3] = hash("ABC"), h[4] = hash["ABCD"]
  2. 求解子串 hash("BC") = hash("ABC") - hash("A00") = h[3] - h[1] * P^2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// h => 前缀和数组
// p => 存放 P 次方的数组
h[0] = 0;
p[0] = 1;
for (int i = 0; i < n; i++)
{
	h[i + 1] += h[i] * P + str[i];
	p[i + 1] = p[i] * P;
}

// 求解子串哈希值
// ULL <=> usigned long long
int len = r1 - l1 + 1;
ULL num1 = h[r1] - h[l1 - 1] * p[len];
ULL num2 = h[r2] - h[l2 - 1] * p[len];

搜索与图论

🌖AcWing 842. 排列数字

原题链接
我的代码

核心逻辑: 深度优先搜索算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 10;
int path[N];

void dfs(int cur, int n, int state)
{
	if (cur == n)
	{
		for (int i = 0; i < n; i++)
			cout << path[i] << " ";
		cout << endl;
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (state >> i & 1) continue;

		path[cur] = i;
		dfs(cur + 1, n, state + (1 << i));
	}
}

🌖AcWing 843. n-皇后问题

原题链接
我的代码

核心逻辑: 深度优先搜索算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int n;
const int N = 10;
char map[N][N];

struct State
{
	bool b1[N + N], b2[N + N];
	bool c[N];
	int num;
}state;

bool check(int row, int col, State& s)
{
	if (s.c[col]) return false;
	if (s.b1[row - col + N])return false;
	if (s.b2[row + col])return false;

	return true;
}

State push(int row, int col, State s)
{
	s.c[col] = true;
	s.b1[row - col + N] = true;
	s.b2[row + col] = true;
	s.num++;
	return s;
}

void dfs(int row, int col, State s)
{
	if (row >= n || col >= n)
	{
		if (s.num != n)return;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
				cout << map[i][j];
			cout << endl;
		}
		cout << endl;
		return;
	}

	if (row > s.num) return;

	if (check(row, col, s))
	{
		State sn = push(row, col, s);
		map[row][col] = 'Q';
		dfs(row + 1, 0, sn);
		map[row][col] = '.';
	}

	if (col == n - 1) dfs(row + 1, 0, s);
	else dfs(row, col + 1, s);
}

🌖AcWing 844. 走迷宫

原题链接
我的代码

核心逻辑: 广度优先搜索算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main()
{
	// ...
	queue<State> q;
	q.push(State(1, 1, 0));
	st[1][1] = true;

	while (!q.empty())
	{
		State s = q.front(); q.pop();
		int x = s.x, y = s.y, t = s.t;

		if (x == n && y == m)
		{
			cout << t << endl;
			break;
		}

		for (int i = 0; i < 4; i++)
		{
			int nx = x + offsets[i].first, ny = y + offsets[i].second;
			if (st[nx][ny] || !map[nx][ny]) continue;

			st[nx][ny] = true;
			q.push(State(nx, ny, t + 1));
		}
	}
}

🌖AcWing 845. 八数码

原题链接
我的代码

核心逻辑: 广度优先搜索算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int main()
{
	// ...
	queue<State> q;
	unordered_map<string, bool> m;
	
	q.push(State(str, 0));
	m[str] = true;
 	
	while(!q.empty())
	{
		State s = q.front(); q.pop();
		
		string str = s.s;
		int t = s.t;
	
		if (str == endstr)
		{
			cout << t << endl;
			return 0;
		}

		int pos = 0;
		while (pos < 9 && str[pos] != 'x') pos++;
	
		for (int i = 0; i < 4; i++)
		{
			if (pos - offsets[i] < 0 || pos - offsets[i] > 8)
				continue;
			if (offsets[i] == 1 && pos % 3 == 0)
				continue;
			if (offsets[i] == -1 && pos % 3 == 2)
				continue;
			
			string nstr = str;
			swap(nstr[pos], nstr[pos - offsets[i]]);
			if (m[nstr])continue;
			
			m[nstr] = true;
			q.push(State(nstr, t + 1));
		}
	}
	cout << -1 << endl;
}

🌖AcWing 848. 有向图的拓扑序列

原题链接
我的代码

维护一个队列，初始元素是所有入度为 0 的点。每次取队头元素并出队，将其能直通的所有点入度减一，若减一后入度为 0 则将其入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	for (int i = 1; i <= n; i++)
		if (degs[i] == 0)q.push(i);

	while (!q.empty())
	{
		int idx = q.front(); q.pop();
		ans.push_back(idx);
		Point& p = points[idx];

		for (auto next : p.edges)
		{
			degs[next]--;
			if (degs[next] == 0) { q.push(next); }
		}
	}
}

🌖849. Dijkstra求最短路 I

原题链接
我的代码

核心逻辑: 维护 dist[n], dist[i] 表示点 1 到点 i 的最短路径，迭代更新

  1. 找到 dist 数组的最小值并将其标记（标记的点不参与迭代）
  2. 遍历标记点 i 的所有边，进行更新: dist[j] = min(dist[j], dist[i] + w(i, j))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int main()
{
	// ...
	vector<int> dist(n + 1, INF);
	vector<bool> st(n + 1, false);

	dist[1] = 0;
	while (true)
	{
		// find min
		int minI = -1, minN = INF;
		for (int i = 1; i <= n; i++)
		{
			if (st[i]) continue;
			if (dist[i] < minN)
			{
				minN = dist[i];
				minI = i;
			}
		}

		if (minI == -1) break;
		st[minI] = true;

		// update
		Point& p = points[minI];
		for (auto e : p.edges)
			dist[e.idx] = min(dist[e.idx], minN + e.w);
	}

	if (dist[n] > INF / 2) cout << -1 << endl;
	else cout << dist[n] << endl;
}

🌖AcWing 851. spfa求最短路

原题链接
我的代码

核心逻辑:

  1. 建立一个队列，初始时队列里只有起始点
  2. 再建立一个数组记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为 0）
  3. 队头不断出队，计算始点起点经过队头到其他点的距离是否变短，如果变短且被点不在队列中，则把该点加入到队尾
  4. 重复执行直到队列为空
  5. 在保存最短路径的数组中，就得到了最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
	// ...
	vector<int> dist(n + 1, INF);
	queue<int> q;

	dist[1] = 0, q.push(1);

	while (!q.empty())
	{
		Point& p = points[q.front()]; q.pop();

		for (auto next : p.edges)
		{
			if (dist[next.first] > dist[p.index] + next.second)
			{
				dist[next.first] = dist[p.index] + next.second;
				q.push(next.first);
			}
		}
	}
}

🌖AcWing 858. Prim算法求最小生成树

原题链接
我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int main()
{
	vector<int> dist(n + 1, INF);
	vector<bool> st(n + 1, false);

	int curIndex = 1, i;
	int res = 0;
	dist[curIndex] = 0, st[curIndex] = true;
	for (i = 1; i < n; i++)
	{
		// update
		for (auto next : points[curIndex].edges)
		{
			int p = next.first, w = next.second;
			dist[p] = min(dist[p], w);
		}

		// find min
		int minN = INF, minI = -1;
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] && dist[j] < minN)
			{
				minN = dist[j];
				minI = j;
			}
		}

		// ans
		if (minI == -1) break;
		st[minI] = true, res += minN, curIndex = minI;
	}
}

数学知识

🌕AcWing 866. 试除法判定质数

原题链接
我的代码

核心逻辑: 如果一个数 x 不能被 2 ~ sqrt(x) 中的任意一个数整除，则其为质数（1 除外）。

1
2
3
4
5
6
7
8
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

🌖AcWing 868. 筛质数

原题链接
我的代码

核心逻辑是：希望合数 k 被最小质因子 j 筛掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
	// ...
	for (int i = 2; i <= n; i++)
	{
		// 如果没被筛掉，是质数
		if (flags[i] == false)
			primes.push_back(i);

		// 筛掉和所有质数的乘积
		for (int j = 0; i * primes[j] <= n; j++)
		{
			flags[i * primes[j]] = true;

			// 保证一个合数只被其最小质因子筛掉，避免重复
			if (i % primes[j] == 0) break;

		}
	}
}

🌖AcWing 870. 约数个数

原题链接
我的代码

核心逻辑：把每个数都转换为最小质因子相乘的形式。

1
2
3
4
5
6
7
8
9
10
11
12
void process(int n, unordered_map<int, int>& m)
{
	for (int i = 2; i <= n / i; i++)
	{
		while (n % i == 0)
		{
			n /= i;
			m[i]++;
		}
	}
	if (n > 1) m[n]++;
}

🌖AcWing 871. 约数之和

原题链接
我的代码

核心逻辑：把每个数都转换为最小质因子相乘的形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	// ...
	long long res = 1;
	for (auto t : m)
	{
		long long sum = 1;
		long long temp = 1;
		for (int i = 1; i <= t.second; i++)
			temp = temp * t.first % E, sum = (sum + temp) % E;
		res = res * sum % E;
	}
}

🌖AcWing 872. 最大公约数

原题链接
我的代码

求 a 和 b 的最大公约数，有两种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 算法一：欧几里得算法
int gcd1(int a, int b)
{
	if (b == 0) return a;
	return gcd1(b, a % b);
}

// 算法二：逐步相减算法
int gcd2(int a, int b)
{
	while (a != b)
	{
		if (a > b)
			a = a - b;
		else b = b - a;
	}
	return a;
}

🌖AcWing 873. 欧拉函数

原题链接
我的代码

核心逻辑: 若 N = p1^a1 * p2^a2 * ... * pm^am，则 Φ(N) = N * (p1 - 1) / p1 * (p2 - 1) / p2 * ... * (pm - 1) / pm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LL phi(int x)
{
    LL res = x;

    unordered_map<int, int> m;
    for (int i = 2; i <= x / i; i++)
    {
        while (x % i == 0)
        {
            x /= i;
            m[i]++;
        }
    }
    if (x > 1) m[x]++;

    for (auto n : m)
        res = res * (n.first - 1) / n.first;

    return res;
}

🌖AcWing 875. 快速幂

原题链接
我的代码

核心逻辑：求解 a ^ b 时，把 b 看成二进制。

例如：b = 10010 => b = a^2 * a^32，而 a^(2^k) 可以在 O(logn) 内求解

1
2
3
4
5
6
7
8
9
10
11
12
int calculate(LL a, LL b, LL p)
{
	long long res = 1;
	while (b)
	{
		if (b & 1) res = res * a % p; 

		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}

🌖AcWing 885. 求组合数 I

原题链接
我的代码

状态设计：f[i][j] 表示 Cij

状态转移：f[i][j] = f[i - 1][j - 1] + f[i - 1][j]

1
2
3
4
5
6
memset(f, 0, sizeof f);
for (int i = 0; i <= 2000; i++)
	for (int j = 0; j <= i; j++)
		if (j)
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % E;
		else f[i][j] = 1;

🌖AcWing 877. 扩展欧几里得算法

原题链接
我的代码

扩展欧几里得算法解决的问题：任意正整数 a, b，存在一组整数 x, y 使得 ax + by = gcd(a, b)，扩展欧几里得可以求出这么一组 x, y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int exgcd(int a, int b, int& x, int& y)
{
	// 当 b == 0 时，显然 a * 1 + b * 0 = a = gcd(a, b)
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}

	// d = gcd(a, b)
	int d = exgcd(b, a % b, y, x);
	
	// 经过上述递归，可以保证等式：
	// 		by + (a % b)x = d
	//  <=>	by + (a - a / b)x = d
	//  <=>	ax + b(y - (a / b) * x) =  d
	// 故 x 不变，y => y - (a / b) * x
	y -= a / b * x;
	
	return d;
}

🌖AcWing 878. 线性同余方程

原题链接
我的代码

核心逻辑: a * x ≡ b (mod m) <=> ax = my + b <=> ax + my' = b。

可以利用扩展欧几里得算法求解 x 和 y’，当 b 是 gcd(a, m) 的倍数时有解 x_final = b / d * x，反之无解。

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
	// ...
	int a, b, m;
	cin >> a >> b >> m;

	int x, y, d;
	d = exgcd(a, m, x, y);

	if (b % d) cout << "impossible" << endl;
	else cout << (long long)x * b / d % m << endl;
}

🌖AcWing 891. Nim游戏

原题链接
我的代码

先手必胜状态: 一定可以经过一次操作变成必败状态

先手必败状态: 无论如何操作都无法变成必败状态

设 ai 为第 i 个石堆的石头数量。

  1. 状态 A: a1 ^ a2 ^ ... ^ an = 0
  2. 状态 B: a1 ^ a2 ^ ... ^ an ≠ 0

可以证明:

  1. A 无论如何操作，无法到达 A
  2. B 存在一种操作，可以到达 A
  3. 石头一定会越来越少，石头全部没有时是先手必败状态，也是 A 状态

所以：

  1. A 是先手必败状态
  2. B 是先手必胜状态
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        cin >> m;
        res ^= m;
    }
    
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
}

🌖AcWing 892. 台阶-Nim游戏

原题链接
我的代码

先手必胜状态: 一定可以经过一次操作变成必败状态

先手必败状态: 无论如何操作都无法变成必败状态

设 ai 为第 i 个石堆的石头数量。

  1. 状态 A: a1 ^ a3 ^ ... ^ a2k-1 = 0
  2. 状态 B: a1 ^ a3 ^ ... ^ a2k-1 ≠ 0

可以证明:

  1. A 无论如何操作，无法到达 A
  2. B 存在一种操作，可以到达 A
  3. 石头一定会越来越靠下，石头全部在地面时是先手必败状态，也是 A 状态

所以：

  1. A 是先手必败状态
  2. B 是先手必胜状态
1
2
3
4
5
6
7
8
9
10
int main()
{
	// ...
	int t, res = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> t;
        if (i % 2) res ^= t; 
    }
}

动态规划

🌖AcWing 2. 01背包问题

原题链接
我的代码

状态表示：f[i][j] <=> 从 1~i 物品中选，且总重量小于 j 的最大价值

状态转移：f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i])

  1. 选第 i 个物品: f[i][j] = f[i - 1][j - w[i]] + v[i]
  2. 不选第 i 个物品: f[i][j] = f[i - 1][j]
1
2
3
4
5
6
7
int main()
{
	// ...
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= w[i]; j--)
			f[j] = max(f[j], f[j - w[i]] + v[i]);
}

🌖AcWing 3. 完全背包问题

原题链接
我的代码

状态表示：f[i][j] <=> 从 1~i 物品中选，且总重量小于 j 的最大价值

状态转移：f[i][j] = max(f[i - 1][j], f[i - 1][j - k * w[i]] + k * v[i])

  1. 选第 i 个物品: f[i][j] = f[i - 1][j - k * w[i]] + k * v[i]
  2. 不选第 i 个物品: f[i][j] = f[i - 1][j]

其中: f[i - 1][j - k * w[i]] + k * v[i] 等价于 f[i][j - w[i]] + v[i]

1
2
3
4
5
6
7
int main()
{
	// ...
	for (int i = 0; i < n; i++)
		for (int j = w[i]; j <= m; j++)
			f[j] = max(f[j], f[j - w[i]] + v[i]);
}

🌖AcWing 4. 多重背包问题 I

原题链接
我的代码

直接将多重背包转化为 01 背包问题。

1
2
3
4
5
6
7
8
int main()
{
	// ...
    int cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < s[i]; j++)
            w[cnt] = wo[i], v[cnt++] = vo[i];
}

🌖AcWing 5. 多重背包问题 II

原题链接
我的代码

利用二进制优化，将多重背包问题转化为 01 背包问题。

核心逻辑：物品个数 s => 1 + 2 + 4 + ... + 2^k + offset，可以保证选择任意个物品都可以用这些二次方数拼凑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main()
{
    // ...
	for (int i = 0; i < n; i++)
	{
        // 重量，价值，个数
		int a, b, c;
		cin >> a >> b >> c;

		int k = 1;
		while (c >= k)
		{
			c -= k;
			v[cnt] = a * k;
			w[cnt] = b * k;

			k *= 2, cnt++;
		}
		if (c > 0)
		{
			v[cnt] = a * c;
			w[cnt] = b * c;
			cnt++;
		}
	}
    // ...
}

🌖AcWing 895. 最长上升子序列

原题链接
我的代码

状态表示：f[i] <=> 以 arr[i] 结尾的最长上升子序列的长度

状态转移：f[i] = max(1, f[i], f[j] + 1) if j < i && arr[j] < arr[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	// ...

	for (int i = 0; i < n; i++)
	{
		f[i] = 1;
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i])
				f[i] = max(f[i], f[j] + 1);
	}

	int res = 0;
	for (int i = 0; i < n; i++)
		res = max(res, f[i]);
	cout << res << endl;
}

🌖AcWing 897. 最长公共子序列

原题链接
我的代码

状态表示：f[i][j] <=> A[1 ~ i] 和 B[1 ~ j] 的最长公共子序列的长度

状态转移：

  1. A[i] ≠ B[j]: f[i][j] = max(f[i - 1][j], f[i][j - 1])
  2. A[i] = B[j]: f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1)
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
	// ...
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			f[i][j] = max(f[i][j - 1], f[i - 1][j]);
			if (A[i - 1] == B[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	}
}

🌖AcWing 902. 最短编辑距离

原题链接
我的代码

状态表示：f[i][j] <=> s1[:i] 变成 s2[:j] 的最短编辑距离

状态转移:

  1. insert: f[i][j] = f[i - 1][j] + 1
  2. delete: f[i][j] = f[i][j - 1] + 1
  3. update: f[i][j] = f[i - 1][j - 1] + (s1[i - 1] != s2[j - 1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
	// ...
	for (int i = 0; i <= n; i++) f[i][0] = i;
	for (int j = 0; j <= m; j++) f[0][j] = j;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
			f[i][j] = min(f[i][j], f[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]));
		}
	}
}

🌖AcWing 900. 整数划分

原题链接
我的代码

状态表示：f[i][j] <=> 从 1~i 中选，且总和等于 j 的方案数

状态转移：f[i][j] = f[i - 1][j] + f[i][j - i] (f[i][j - i] 包含了 f[i - 1][j - k * i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 压缩成一维版本
int main()
{
    // ...

	f[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
		{
			f[j] = f[j] + f[j - i] % E;
		}
	}
	cout << f[n] % E << endl;
}

🌗AcWing 91. 最短Hamilton路径

原题链接
我的代码

状态表示：f[i][j] <=> 当前经过点的状态为 i, 在 j 点结束的最短路径。

状态转移：见下面的代码。

1
2
3
4
5
6
7
8
9
10
11
int main()
{
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (int i = 0; i < 1 << n; i++)
		for (int j = 0; j < n; j++)
			if (i >> j & 1)
				for (int k = 0; k < n; k++)
					if (i >> k & 1)
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}

🌗AcWing 285. 没有上司的舞会

原题链接
我的代码

树型 DP 问题。

状态表示:

  1. f[i][0] <=> 第 i 号职员不参加晚会，其子树的最大快乐值
  2. f[i][1] <=> 第 i 号职员参加晚会，其子树的最大快乐值

状态转移（j 是 i 的子节点）：

  1. f[i][0] = sum { max(f[j][0], f[j][1]) }
  2. f[i][1] = sum { f[j][0] }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int dfs(vector<Point> &points, int root, bool select)
{
	Point p = points[root];
	st[root] = true;

    // 记忆化搜索
	if (f[root][select])return f[root][select];

    // res1 => f[i][1], res2 => f[i][0] 
	int res1 = p.value;
	int res2 = 0;
	for (int i = 0; i < p.edges.size(); i++)
	{
		int index = p.edges[i];
		if (st[index])continue;
		int ans1 = dfs(points, index, false), ans2 = dfs(points, index, true);
		res1 += ans1;
		res2 += max(ans1, ans2);
	}
	f[root][true] = res1;
	f[root][false] = res2;

	return f[root][select];
}

🌗AcWing 901. 滑雪

原题链接
我的代码

状态表示：f[i][j] <=> 从 (i, j) 开始滑，最多能滑多少格

状态转移：

  1. if(h[i][j] > h[i - 1][j]) => f[i][j] = max(f[i][j], f[i - 1][j] + 1)
  2. if(h[i][j] > h[i + 1][j]) => f[i][j] = max(f[i][j], f[i + 1][j] + 1)
  3. if(h[i][j] > h[i][j - 1]) => f[i][j] = max(f[i][j], f[i][j - 1] + 1)
  4. if(h[i][j] > h[i][j + 1]) => f[i][j] = max(f[i][j], f[i][j + 1] + 1)

核心问题是，状态转移的过程并不是一个拓扑排序，故需要用到记忆化搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(int R, int C, int curR, int curC)
{
	if (curR <= 0 || curC <= 0 || curR > R || curC > C)return 0;

	// 记忆化搜索的核心
	if (f[curR][curC] > 0)return f[curR][curC];

	int res = 0;
	if (arr[curR][curC] > arr[curR - 1][curC]) res = max(res, search(R, C, curR - 1, curC));
	if (arr[curR][curC] > arr[curR + 1][curC]) res = max(res, search(R, C, curR + 1, curC));
	if (arr[curR][curC] > arr[curR][curC - 1]) res = max(res, search(R, C, curR, curC - 1));
	if (arr[curR][curC] > arr[curR][curC + 1]) res = max(res, search(R, C, curR, curC + 1));

	return f[curR][curC] = res + 1;
}

贪心

🌖AcWing 148. 合并果子

原题链接
我的代码

核心逻辑: Huffman 树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
	// ...
	priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        q.push(a);
    }

    int res = 0;
    while ((int)q.size() > 1)
    {
        int n1 = q.top(); q.pop();
        int n2 = q.top(); q.pop();

        res += n1 + n2;
        q.push(n1 + n2);
    }
}

🌖AcWing 913. 排队打水

原题链接
我的代码

升序排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	// ...
    sort (t + 1, t + n + 1);
    
    for (int i = 1; i <= n; i++)
        t[i] += t[i - 1];
    
    long long res = 0;
    for (int i = 1; i < n; i++)
        res += t[i];
    cout << res << endl;
}

🌕AcWing 104. 货仓选址

原题链接
我的代码

核心逻辑：

  1. 如果商店总数是奇数，和中间数重叠
  2. 如果商店总数是偶数，在中间左数和中间右数之间即可
1
2
3
4
5
6
7
8
9
10
11
int main()
{
	// ...
	sort(nums.begin(), nums.end());

	int pos = nums[nums.size() / 2];
	int res = 0;
	for (auto n : nums)
		res += abs(n - pos);
	cout << res << endl;
}

🌖AcWing 125. 耍杂技的牛

原题链接
我的代码

核心逻辑: 若某个序列不是最优，一定可以通过冒泡排序，交换若干相邻位得到最优序列。

假设目前序列为: c1, c2, ..., ci, ci+1, ..., cn，交换 ci 和 ci+1:

设 w = w1 + ... + wi-1

ci ci+1
before swap w - si w + wi - si+1
after swap w + wi+1 - si w - si+1

所以交换策略为: max(w - si, w + wi - si+1) < max(w - si+1, w + wi+1 - si)

<=> max(si+1, wi + si) < max(si, wi+1 + si+1)

<=> wi + si < wi+1 + si+1

1
2
3
4
bool compare(pair<int, int>& p1, pair<int, int>& p2)
{
    return p1.first + p1.second < p2.first + p2.second;
}

补充练习

🌖AcWing 271. 杨老师的照相排列

原题链接
我的代码

状态表示：f[a][b][c][d][e] <=> 第一排 a 个人，第二排 b 个人，第三排 c 个人，第四排 d 个人，第五排 e 个人的方案数。

状态转移：考虑从站好 a + b + c + d + e - 1 个人的状态转移过来。

  1. a > 0 && a - 1 >= b 说明可从状态 f[a - 1][b][c][d][e] 转移而来
  2. b > 0 && b - 1 >= c 说明可从状态 f[a][b - 1][c][d][e] 转移而来
  3. c > 0 && c - 1 >= d 说明可从状态 f[a][b][c - 1][d][e] 转移而来
  4. d > 0 && d - 1 >= e 说明可从状态 f[a][b][c][d - 1][e] 转移而来
  5. e > 0 说明可从状态 f[a][b][c][d][e - 1] 转移而来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
	// ...
	memset(f, 0, sizeof f);
	f[0][0][0][0][0] = 1;
	for (int n1 = 0; n1 <= n[0]; n1++)
		for (int n2 = 0; n2 <= min(n[1], n1); n2++)
			for (int n3 = 0; n3 <= min(n[2], n2); n3++)
				for (int n4 = 0; n4 <= min(n[3], n3); n4++)
					for (int n5 = 0; n5 <= min(n[4], n4); n5++)
					{
						LL& v = f[n1][n2][n3][n4][n5];
						if (n1 > 0 && n1 - 1 >= n2) v += f[n1 - 1][n2][n3][n4][n5];
						if (n2 > 0 && n2 - 1 >= n3) v += f[n1][n2 - 1][n3][n4][n5];
						if (n3 > 0 && n3 - 1 >= n4) v += f[n1][n2][n3 - 1][n4][n5];
						if (n4 > 0 && n4 - 1 >= n5) v += f[n1][n2][n3][n4 - 1][n5];
						if (n5 > 0)					v += f[n1][n2][n3][n4][n5 - 1];
					}
	
	cout << f[n[0]][n[1]][n[2]][n[3]][n[4]] << endl;
}

🌗AcWing 272. 最长公共上升子序列

原题链接
我的代码

状态表示: f[i][j] 表示在 A[1 ~ i], B[1 ~ j] 中任选，以 B[j] 结尾的最长公共上升子序列的长度。

状态转移:

  1. 若 A[i] == B[j]:
    • f[i][j] = 1
    • k ∈ [1, j) && B[k] < B[j], f[i][j] = max(f[i][j], f[i][k] + 1)
  2. 若 A[i] != B[j]:
    • f[i][j] = f[i - 1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
	// ...
	for (int i = 1; i <= n; i++)
	{
		int maxv = 1;
		for (int j = 1; j <= n; j++)
		{
			f[i][j] = f[i - 1][j];
			if (A[i] == B[j]) f[i][j] = max(f[i][j], maxv);
			if (A[i] > B[j]) maxv = max(maxv, f[i - 1][j] + 1);
		}
	}
}

🌗AcWing 273. 分级

原题链接
我的代码

首先通过惊人的注意力可以得到结论：一定存在一组最优解，使得 B 中的所有数都在 A 里出现过。

状态表示: f[i][j] 表示考虑 A[1 ~ i], 且 B[j] = A'[i] 时的 S 最小值，A' 表示升序排序的 A

状态转移: f[i][j] = min(f[i - 1][k] + abs(A[i] - A'[j])), k ∈ [1, j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
	// ...
	for (int i = 1; i <= n; i++)
	{
		int minv = INF;
		for (int j = 1; j <= n; j++)
		{
			minv = min(minv, f[i - 1][j]);
			f[i][j] = minv + abs(A[i] - B[j]);
		}
	}
	
	int res = INF;
	for (int i = 1; i <= n; i++)
		res = min(res, f[n][i]);
}