算法题训练

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

难度：🌕🌖🌗🌘🌚


基础算法

快速排序

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

Trie

🌖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 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 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 241. 楼兰图腾

原题链接
我的代码

核心逻辑: c[i] 表示数组 n 中值为 i 的个数

  1. 正向遍历数组，每次遍历使 c[num[i]]++
  2. 反向遍历数组，每次遍历使 c[num[i]]++

用树状数组维护 c 的前缀和:

  1. 正向遍历数组时，求 c[1 ~ num[i] - 1] 的前缀和，代表 n[i] 左边比 n[i] 小的个数
  2. 反向遍历数组时，求 c[1 ~ num[i] - 1] 的前缀和，代表 n[i] 右边比 n[i] 小的个数

最终的答案为:

  1. ∨ 的个数: sum{ left_high(i) * right_high(i) }
  2. ∧ 的个数: sum{ left_low(i) * right_low(i) }
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
const int N = 200010;
int num[N], c[N], rh[N], lh[N], n;

inline static int lowerbit(int x)
{
	return x & -x;
}

void add(int x, int y)
{
	for (; x <= n; x += lowerbit(x))
		c[x] += y;
}

int ask(int x)
{
	int ans = 0;
	for (; x; x -= lowerbit(x))
		ans += c[x];
	return ans;
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	for (int i = n; i >= 1; i--)
	{
		rh[i] = ask(n) - ask(num[i]);
		add(num[i], 1);
	}

	memset(c, 0, sizeof c);
	for (int i = 1; i <= n; i++)
	{
		lh[i] = ask(n) - ask(num[i]);
		add(num[i], 1);
	}

	LL res1 = 0, res2 = 0;
	for (int i = 1; i <= n; i++)
		res1 += (LL)rh[i] * lh[i], res2 += (LL)(n - i - rh[i]) * (i - 1 - lh[i]);
	cout << res1 << " " << res2 << endl;
	return 0;
}

🌗AcWing 242. 一个简单的整数问题

原题链接
我的代码

核心逻辑: 用树状数组维护差分的前缀和。

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
#include<iostream>
using namespace std;

const int N = 100010;
int a[N], c[N];
int n, m;

inline int lowerbit(int x)
{
	return x & -x;
}

void add(int x, int y)
{
	for (; x <= n; x += lowerbit(x))
		c[x] += y;
}

int ask(int x)
{
	int ans = 0;
	for (; x; x -= lowerbit(x))
		ans += c[x];
	return ans;
}

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= n; i++)
		add(i, a[i] - a[i - 1]);

	while (m--)
	{
		char op;
		cin >> op;

		if (op == 'C')
		{
			int l, r, d;
			cin >> l >> r >> d;

			add(l, d), add(r + 1, -d);
		}
		else if (op == 'Q')
		{
			int x;
			cin >> x;

			cout << ask(x) << endl;
		}
	}
	return 0;
}

🌘AcWing 243. 一个简单的整数问题2

原题链接
我的代码

我们希望维护一些额外信息。

例如在一个简单的整数问题中，我们维护一个新的数组 b:

  1. 将 C l r d 转换为 b[l] += d, b[r + 1] -= d
  2. C l r d 操作对 b 数组前缀和的影响为: sum[l], ..., sum[r] += d
  3. 此时，b[1] + ... + b[x] 代表 C 操作对 a[x] 的总影响

本问题中，我们希望将 C 操作对 a[x] 的总影响 转化为 C 操作对 a[1] + a[2] + ... + a[x] 的总影响。我们维护两个数组 c0, c1:

  1. 将 C l r d 转换为 c0[l] += d, c0[r + 1] -= d; c1[l] += ld, c1[r + 1] -= (r + 1)d
  2. 此时，[(r + 1) * (c0[1] + ... + c0[r]) - (c1[1] + ... + c1[r])] - [l * (c0[1] + ... + c0[l - 1]) - (c1[1] + ... + c1[l - 1])] 代表 C 操作对 a[1] + a[2] + ... + a[x] 的总影响
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
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
LL a[N], c[2][N];
int n, m;

inline int lowerbit(int x)
{
	return x & -x;
}

void add(int k, int x, int y)
{
	for (; x <= n; x += lowerbit(x))
		c[k][x] += y;
}

LL ask(int k, int x)
{
	int ans = 0;
	for (; x; x -= lowerbit(x))
		ans += c[k][x];
	return ans;
}

int main()
{
	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];

	while (m--)
	{
		char op;
		cin >> op;

		if (op == 'C')
		{
			int l, r, d;
			cin >> l >> r >> d;

			add(0, l, d), add(0, r + 1, -d);
			add(1, l, l * d), add(1, r + 1, -(r + 1) * d);
		}
		else if (op == 'Q')
		{
			int l, r;
			cin >> l >> r;

			LL n1 = a[r] + (r + 1) * ask(0, r) - ask(1, r);
			LL n2 = a[l - 1] + l * ask(0, l - 1) - ask(1, l - 1);
			cout << n1 - n2 << endl;
		}
	}
	return 0;
}

🌗AcWing 244. 谜一样的牛

原题链接
我的代码

核心逻辑:

  1. 维护一个数组 b, b[i] = 0 表示身高为 i 的牛已经被找到了, 反之 b[i] = 1
  2. 倒序遍历数组 a, 对于 a[i], 从 b 中找到第 a[i] 个值为 1 的索引, 作为第 i 只牛的身高
  3. 从 b 中找到第 a[i] 个值为 1 的索引 等价于 找到前缀和为 a[i] 的索引
  4. 可以用树状数组 + 二分的思想
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
#include<iostream>
#include<unordered_map>
using namespace std;

const int N = 100010;
int n;
int a[N], b[N], c[N];

inline int lowerbit(int x)
{
	return x & -x;
}

void add(int x, int y)
{
	for (; x <= n; x += lowerbit(x))
		c[x] += y;
}

int ask(int x)
{
	int ans = 0;
	for (; x; x -= lowerbit(x))
		ans += c[x];
	return ans;
}

int find(int k)
{
	int l = 1, r = n;
	while (l < r)
	{
		int mid = (l + r) >> 1;

		if (ask(mid) >= k) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main()
{
	cin >> n;

	for (int i = 2; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= n; i++)
		add(i, 1);

	for (int i = n; i >= 1; i--)
	{
		int p = find(a[i] + 1);
		b[i] = p;
		add(p, -1);
	}

	for (int i = 1; i <= n; i++)
		cout << b[i] << endl;
	return 0;
}

搜索与图论

DFS

🌖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 165. 小猫爬山

原题链接
我的代码

深度优先搜索，从重量逆序遍历所有猫猫，枚举所有当前使用的缆车，如果可以放下这只猫，则放；如果都放不下，则开一辆新车。

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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 20;
int n, w, res = N;
int cats[N], sums[N];

void dfs(int curN, int curC)
{
	if (curN > n)
	{
		res = min(res, curC);
		return;
	}

	if (curC >= res) return;

	for (int i = 1; i <= curC; i++)
	{
		if (sums[i] + cats[curN] <= w)
		{
			sums[i] += cats[curN];
			dfs(curN + 1, curC);
			sums[i] -= cats[curN];
		}
	}

	sums[curC + 1] += cats[curN];
	dfs(curN + 1, curC + 1);
	sums[curC + 1] -= cats[curN];
}

bool compare(int& n1, int& n2)
{
	return n1 > n2;
}

int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; i++)
		cin >> cats[i];

	sort(cats + 1, cats + n + 1, compare);

	dfs(1, 1);

	cout << res << endl;
	return 0;
}

🌖AcWing 167. 木棒

原题链接
我的代码

DFS 搜索顺序：根据木棒的长度从小到大枚举每根木棒，对于每根木棒，枚举可以由哪些木棍拼成，如果所有的木棍拼成了长度相等的多个木棒，说明找到了答案，否则木棒长度加 1 继续搜索。

为什么是正确的？因为题目要求保证拼凑成功的前提下，还有分组尽可能少，即木棒数量尽可能少，所以我们从小到大枚举每根木棒的长度，第一次找到答案时就是最优解。

剪枝优化：

  1. 剪枝 1：sum % length == 0 只有 length 是 sum 的约数才有可能凑出多个等长的木棒
  2. 剪枝 2：优化搜索顺序，木棍长度从大到小排序，可以减少搜索的分支
  3. 排除等效冗余优化
    • 剪枝 3-1：确定每根木棒中木棍的枚举顺序，因为我们的方案和顺序没有关系，以组合的形式枚举方案可以少搜很多重复方案
    • 剪枝 3-2：如果当前木棍没有搜到方案，则跳过所有长度相等的木棍
    • 剪枝 3-3：如果是木棒的第一根木棍就搜索失败了，则一定搜不到方案
    • 剪枝 3-4：如果是木棒的最后一根木棍（+ 上它木棒长度正好是 length）搜索失败了，也一定搜不到方案
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
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int n, len, total;
int wood[65];
bool st[65];

bool compare(int& n1, int& n2)
{
	return n1 > n2;
}

bool dfs(int curN, int curS, int start)
{
	if (curN == total) return true;
	if (curS == len) return dfs(curN + 1, 0, 0);

	for (int i = start; i <= n; i++)
	{
		if (st[i]) continue;
		if (curS + wood[i] > len) continue;
		
		st[i] = true; 
		if (dfs(curN, curS + wood[i], start + 1)) return true;
		st[i] = false;

		if (curS == 0) return false;
		if (curS + wood[i] == len) return false;
	
		int j = i;
		while (j <= n && wood[i] == wood[j])j++;
		i = j - 1;
	}

	return false;
}

void solution()
{
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> wood[i];
		sum += wood[i];
	}
	memset(st, false, sizeof st);
	sort(wood + 1, wood + n + 1, compare);
	for (len = wood[1]; len <= sum; len++)
	{
		if (sum % len) continue;
		total = sum / len;
		if (dfs(0, 0, 1))
		{
			cout << len << endl;
			return;
		}
	}
}

int main()
{
	while (cin >> n && n)
		solution();
	return 0;
}

🌖AcWing 168. 生日蛋糕

原题链接
我的代码

DFS 搜索顺序：枚举蛋糕的每一层，每一层内枚举半径 r 和高度 h。

问题转化:

  1. 满足条件: Σ (i = 1, i <= M) { R^2 } * H = N
  2. 最小化: min{ 2 * Σ (i = 1, i <= M) { RH } + R1^2 }

剪枝优化：

  1. 剪枝 1: 当前最优解大于等于全局最优解时，剪枝
  2. 剪枝 2: 上层蛋糕取最大体积也无法到达 N 时，剪枝
  3. 剪枝 3: 上层蛋糕取最小体积也无法小于 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
58
59
60
61
62
63
64
65
#include<iostream>
#include<cmath>
using namespace std;

int N, M;
const int INF = 0x3f3f3f3f;

// ΣR^2 * H = N
// min{ 2ΣRH + R1^2 }

int res = INF;

void dfs(int curM, int curV, int curR, int curH, int curRes)
{
	if (curM > M) 
	{
		if(curV == N)
			res = min(res, curRes);
		return;
	}

	// prune 1: res too big
	int minr = 0;
	for (int i = 1; i <= M - curM + 1; i++)
		minr += 2 * i * i;
	if (curRes + minr >= res) return;

	// prune 2: V too big
	int minv = 0;
	for (int i = 1; i <= M - curM + 1; i++)
		minv += i * i * i;
	if (minv + curV > N) return;

	// prune 3: V too small
	int maxv = 0;
	for (int i = 1; i <= M - curM + 1; i++)
		maxv += (curR - i) * (curR - i) * (curH - i);
	if (maxv + curV < N) return;

	int minrh = M - curM + 1;
	for (int r = curR - 1; r >= minrh; r--)
	{
		if (r * r + curV > N) continue;
		for (int h = curH - 1; h >= minrh; h--)
		{
			int v = r * r * h;
			int s = 2 * r * h + r * r * (curM == 1);

			if (v + curV > N) continue;

			dfs(curM + 1, curV + v, r, h, curRes + s);
		}
	}
}

int main()
{
	cin >> N >> M;
	dfs(1, 0, sqrt(N), N, 0);

	if (res > INF / 2) cout << 0 << endl;
	else cout << res << endl;

	return 0;
}

🌖AcWing 170. 加成序列

原题链接
我的代码

迭代加深，每次搜索能否构造出长度为 d 的序列，如果不行则让 d++。

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
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

const int N = 110;
int n, maxD, path[N];

bool dfs(int curN)
{
	if (curN == maxD && path[curN] == n)
		return true;

	if (curN >= maxD) 
		return false;

	bool st[N] = { 0 };
	for (int i = curN; i >= 1; i--)
	{
		for (int j = i; j >= 1; j--)
		{
			int sum = path[i] + path[j];
	
			if (st[sum] || sum > n) continue;
			st[sum] = true;

			if (sum <= path[curN]) return false;
			
			path[curN + 1] = sum;
			if (dfs(curN + 1)) return true;
		}
	}

	return false;
}

void solution()
{
	path[1] = 1;
	for (maxD = 1; maxD <= n; maxD++)
	{
		if (dfs(1))
		{
			for (int i = 1; i <= maxD; i++)
				cout << path[i] << " ";
			cout << endl;
			break;
		}
	}
}

int main()
{
	while (cin >> n && n)
		solution();
	
	return 0;
}

BFS

🌖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 175. 电路维修

原题链接
我的代码

将不能走的路视为权重为 1 的边，能走的路视为权重为 0 的边，问题等价于求解起点到终点的最短路径。

对于权重只有 0 和 1 的最短路径问题，可以用双端 BFS 解决。当遇到权重为 0 的边时，将其插入队头；当遇到权重为 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
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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <deque>

using namespace std;

typedef pair<int, int > PII;

int n, m;
const int N = 510;
char g[N][N];
int d[N][N];

inline bool check(int x, int y)
{
    if(x >= 0 && x <= n && y >= 0 && y <= m) return true;
    return false;
}

inline int bfs()
{
    memset(d, 0x3f, sizeof d);

    deque<PII> dq;
    dq.push_front({0, 0});
    d[0][0] = 0;

    int moved[4][2] = {
        {-1, -1},
        {-1, 1},
        {1, 1},
        {1, -1},
    };
    int movei[4][2] = {
      {-1, -1},
      {-1, 0},
      {0, 0},
      {0, -1},
    };
    char cp[] = "\\/\\/";

    while(dq.size())
    {
        auto t = dq.front();
        dq.pop_front();

        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i ++)
        {
            int a = x + moved[i][0], b = y + moved[i][1];
            if(check(a, b))
            {
                int j = x + movei[i][0], k = y + movei[i][1];
                int w;
                if(g[j][k] != cp[i]) w = 1;
                else w = 0;

                if(d[a][b] > d[x][y] + w)
                {
                    d[a][b] = d[x][y] + w;
                    if(w) dq.push_back({a, b});
                    else dq.push_front({a, b});
                }
            }
        }
    }

    if(d[n][m] == 0x3f3f3f3f) return -1;
    else return d[n][m];
}

inline void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> g[i];

    int res = bfs();

    if(res == -1) puts("NO SOLUTION");
    else cout << res << endl;
}

int main()
{
    int t;
    cin >> t;
    while( t -- ) solve();
    return 0;
}

🌖AcWing 173. 矩阵距离

原题链接
我的代码

多源 BFS，从多个起点同时搜索。

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
#include<iostream>
#include<queue>
using namespace std;

const int N = 1010;
char A[N][N];
int B[N][N];
int n, m;
pair<int, int> offsets[4] = { {0,1},{0,-1},{1,0},{-1,0} };

int main()
{
	cin >> n >> m;

	queue<pair<int, int>> q;
	for (int i = 1; i <= n; i++)
	{
		scanf("%s", A[i] + 1);
		for (int j = 1; j <= m; j++)
		{
			if (A[i][j] == '1')
			{
				B[i][j] = 1;
				q.push({ i,j });
			}
		}
	}

	while (!q.empty())
	{
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ni = ci + offsets[i].first;
			int nj = cj + offsets[i].second;
			
			if (ni <= 0 || ni > n || nj <= 0 || nj > m) continue;
			if (B[ni][nj]) continue;
			B[ni][nj] = B[ci][cj] + 1;

			q.push({ ni,nj });
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			printf("%d ", B[i][j] - 1);
		puts("");
	}
	return 0;
}

🌗AcWing 3681. 小镇购物

原题链接
我的代码

对每个点分别进行 BFS 搜索。

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

struct Point
{
	int idx;
	int com;
	vector<int> edges;

	Point() :idx(-1), com(-1), edges(vector<int>()) {}
	Point(int idx, int com) :idx(idx), com(com), edges(vector<int>()) {}
};

struct State
{
	int idx, dist;
};

const int N = 10010, K = 110, INF = 0x3f3f3f3f;

int n, m, k, s;
vector<Point> points;
bool pf[N], cf[N];

int work(int root)
{
	queue<State> q;
	State st({ root,0 });
	memset(pf, false, sizeof pf);
	memset(cf, false, sizeof cf);

	q.push(st);
	pf[st.idx] = cf[points[st.idx].com] = true;
	
	int res = 0, cnt = 1;
	if (s == 1) return res;
	while (!q.empty())
	{
		Point& p = points[q.front().idx];
		int dist = q.front().dist;
		q.pop();

		for (auto next : p.edges)
		{
			int com = points[next].com;
			
			if (pf[next]) continue;
			pf[next] = true;

			if (!cf[com])
			{
				cf[com] = true;
				cnt++;
				res += dist + 1;
				if (cnt == s)
					return res;
			}

			q.push(State({ next, dist + 1 }));
		}
	}

	return res;
}

int main()
{
	while (cin >> n >> m >> k >> s)
	{
		points.clear();
		points.push_back(Point());

		for (int i = 1; i <= n; i++)
		{
			int com; cin >> com;
			points.push_back(Point(i, com));
		}

		for (int i = 1; i <= m; i++)
		{
			int a, b;
			cin >> a >> b;

			points[a].edges.push_back(b);
			points[b].edges.push_back(a);
		}

		for (int i = 1; i <= n; i++)
			cout << work(i) << " ";
		cout << endl;
	}

	return 0;
}

树和图的遍历

🌖AcWing 846. 树的重心

原题链接
我的代码

删除一个节点 i，剩余各个连通块中点数的最大值为两者的最大值:

  1. 各个子节点的规模的最大值
  2. 总节点数减去自己子树的规模
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dfs(int root, vector<Point>& po, vector<bool>& st, int &res)
{ 
	Point& p = po[root];
	
	int n1 = 0, n2 = 1;
	for (auto edge : p.edges)
	{
		if (st[edge]) continue;
		st[edge] = true;

		int tmp = dfs(edge, po, st, res);
		n1 = max(n1, tmp);
		n2 = n2 + tmp;
	}

	res = min(res, max(n1, (int)po.size() - n2 - 1));
	return n2;
}

🌖AcWing 847. 图中点的层次

原题链接
我的代码

对于权值恒为一的图，最短路径用广度有限搜索即可。

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
int main()
{
	// ...
	queue<pair<int, int>> q;		// index, dist
	vector<bool> st(n + 1, false);

	q.push({ 1, 0 });
	st[1] = true;

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

		if (p.index == n)
		{
			cout << dist << endl;
			return 0;
		}

		for (auto next : p.edges)
		{
			if (st[next]) continue;
			st[next] = true;

			q.push({ next, dist + 1 });
		}
	}
}

🌖AcWing 164. 可达性统计

原题链接
我的代码

核心逻辑: 进行拓扑排序，对可达性进行或运算。

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
#include<iostream>
#include<bitset>
#include<vector>
#include<queue>
using namespace std;

const int N = 30000;

struct Point
{
	int index;
	vector<int> edges;
};

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

	vector<Point> points(n + 1, Point());
	vector<bitset<N>> flags(n + 1, 0);
	vector<int> degs(n + 1, 0);
	for (int i = 1; i <= n; i++)
		points[i].index = i, flags[i][i] = 1;

	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;

		points[y].edges.push_back(x);
		degs[x]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++)
		if (degs[i] == 0) q.push(i);

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

		for (auto ne : p.edges)
		{
			flags[ne] = flags[ne] | flags[p.index];

			degs[ne]--;
			if (degs[ne] == 0)
				q.push(ne);
		}
	}

	for (int i = 1; i <= n; i++)
		cout << flags[i].count() << endl;
	return 0;
}

🌘AcWing 3682. 图的连通分量

原题链接
我的代码

因为要满足 x & y = 0 才有边，而这样不太好进行枚举，因此，假设总二进制位数为 n，那么两个数之间有边等价于 (x ^ lim) & y ≠ 0 且此时 y 一定是 (x ^ lim) 的子集

所以我们只需要去枚举所有 (x ^ lim) 的子集即可。

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
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int M = 1e7 + 10;

int n, m, mask;
int arr[M];
bool st[M], has[M];

inline int lowbit(int x)
{
	return x & -x;
}

void dfs(int u)
{
	if (st[u]) return;
	st[u] = true;

	if (has[u]) dfs(u ^ mask);

	for (int x = u; x; x -= lowbit(x))
		dfs(u - lowbit(x));
}

void solution()
{
	mask = (1 << n) - 1;
	memset(st, false, sizeof st);
	memset(has, false, sizeof has);
	for (int i = 1; i <= m; i++)
	{
		cin >> arr[i];
		has[arr[i]] = true;
	}

	int res = 0;
	for (int i = 1; i <= m; i++)
	{
		if (st[arr[i]]) continue;
		res++;

		dfs(arr[i] ^ mask);
	}
	
	cout << res << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	while (cin >> n >> m)
		solution();

	return 0;
}

拓扑排序

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

最短路径

🌖AcWing 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 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 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 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; 
    }
}

动态规划

线性 DP

🌖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 899. 编辑距离

原题链接
我的代码

状态表示：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
15
16
17
18
19
20
21
int edit_distance(string s1, string s2)
{
	int len1 = s1.size(), len2 = s2.size();

	for (int i = 0; i <= len1; i++)f[i][0] = i;
	for (int i = 0; i <= len2; i++)f[0][i] = i;

	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			// delete | insert
			f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
		
			// update
			f[i][j] = min(f[i][j], f[i - 1][j - 1] + !(s1[i - 1] == s2[j - 1]));
		}
	}

	return f[len1][len2];
}

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

🌗AcWing 274. 移动服务

状态表示: f[k][x][y] 表示当前已经完成了 k 个请求，且三个服务员的位置为 r[k], x, y

状态转移: 若已经得到了 f[k][x][y]，能推出

  1. 对于 k + 1 个请求，(r[k], x, y) => (r[k + 1], x, y)，也即位于 r[k] 位置的服务员完成第 k + 1 个请求，有 f[k + 1][x][y] = f[k][x][y] + c[r[k]][r[k + 1]]
  2. 对于 k + 1 个请求，(r[k], x, y) => (r[k], r[k + 1], y)，也即位于 x 位置的服务员完成第 k + 1 个请求，有 f[k + 1][r[k]][y] = f[k][x][y] + c[x][r[k + 1]]
  3. 对于 k + 1 个请求，(r[k], x, y) => (r[k], x, r[k + 1])，也即位于 y 位置的服务员完成第 k + 1 个请求，有 f[k + 1][r[k]][y] = f[k][x][y] + c[y][r[k + 1]]

初始化时，由于三个服务员最开始位置在 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
int main()
{
	// ...
	r[0] = 3;
	memset(f, 0x3f, sizeof f);
	f[0][1][2] = 0;

	for (int k = 0; k < n; k++)
	{
		for (int x = 1; x <= l; x++)
		{
			for (int y = 1; y <= l; y++)
			{
				int v = f[k][x][y], z = r[k], u = r[k + 1];
				
				if (x == y || y == z || x == z) continue;

				// x, y, z => u, y, z
				f[k + 1][y][z] = min(f[k + 1][y][z], v + c[x][u]);

				// x, y, z => x, u, z
				f[k + 1][x][z] = min(f[k + 1][x][z], v + c[y][u]);

				// x, y, z => x, y, u
				f[k + 1][x][y] = min(f[k + 1][x][y], v + c[z][u]);
			}
		}
	}
}

🌗AcWing 275. 传纸条

原题链接
我的代码

一来一回传纸条等价于一个方向传两次。

状态表示: f[k][x][y] 表示两个纸条走了 k 步，一个位于 x 行，一个位于 y 行的好心程度最大值

状态转移: t = w[x][k - x + 1] + w[y][k - y + 1]

  1. f[k][x][y] = f[k - 1][x][y] + t
  2. f[k][x][y] = f[k - 1][x - 1][y] + t
  3. f[k][x][y] = f[k - 1][x][y - 1] + t
  4. f[k][x][y] = f[k - 1][x - 1][y - 1] + t

当 x == y or x, y 超界时跳过。

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
int main()
{
	// ...
	for (int k = 1; k < n + m; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				int i1 = i, j1 = k - i + 1, i2 = j, j2 = k - j + 1;

				if (i1 == i2 || j1 < 1 || j1 > m || j2 < 1 || j2 > m) continue;

				int num = map[i1][j1] + map[i2][j2];

				// right right
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + num);

				// right down
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + num);

				// down right
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + num);

				// down down
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + num);
			}
		}
	}

	cout << f[n + m - 2][n][n - 1] << endl;
}

🌖AcWing 278. 数字组合

原题链接
我的代码

状态表示: f[x][y] 表示数 A1 ~ Ax 组成 y 的方法数

状态转移: f[x][y] = f[x - 1][y] + f[x - 1][y - Ai]

1
2
3
4
5
6
7
8
9
int main()
{
	// ...
	f[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= A[i]; j--)
			f[j] += f[j - A[i]];
	cout << f[m] << endl;
}

🌖AcWing 279. 自然数拆分

原题链接
我的代码

状态表示: f[x][y] 表示数 1 ~ x 组成 y 的方法数

状态转移: f[x][y] = f[x - 1][y] + f[x][y - i]

1
2
3
4
5
6
7
8
9
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) % E;
	cout << f[n] << endl;
}

🌗AcWing 280. 陪审团

原题链接
我的代码

状态表示: f[i][j][k] 表示在 1 ~ i 个分数中，选择 j 个分数，P - D 的值是 k 时，P + D 的最大值

状态转移:

  1. 不使用第 i 个分数: f[i][j][k] = f[i - 1][j][k]
  2. 使用第 i 个分数: f[i][j][k] = f[i - 1][j - 1][k - p[i] + d[i]] + p[i] + d[i]

需要注意的是，k 维度可能出现负数，实际代码需要加上一个 offset。

将 f 数组全部计算完毕后，k 从 0 开始扫，0 -> (1, -1) -> (2, -2) -> ...，找到最小的 k。之后根据 f 数组逆向出实际选择的分数情况。

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
#include<iostream>
#include<string.h>
using namespace std;

const int N = 210, M = 25, P = 500;
int d[N], p[N], f[N][M][2 * P];
int res[N], cntt;

int main()
{
	int n, m;
	int cnt = 0;
	while (cin >> n >> m && n && m)
	{
		cnt++;
		for (int i = 1; i <= n; i++)
			cin >> p[i] >> d[i];

		memset(f, -0x3f, sizeof f);
		f[0][0][P] = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= m; j++)
				for (int k = 0; k < 2 * P; k++)
				{
					f[i][j][k] = f[i - 1][j][k];
					if (j >= 1)
						f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - (p[i] - d[i])] + (p[i] + d[i]));
				}


		int minK = 0;
		while (f[n][m][P + minK] < 0 && f[n][m][P - minK] < 0) minK++;
		if (f[n][m][P + minK] < f[n][m][P - minK]) minK = P - minK;
		else minK = P + minK;

		int i = n, j = m, k = minK;
		cntt = 0;
		while (j)
		{
			// transfer from not choose i
			if (f[i][j][k] == f[i - 1][j][k])
			{
				i = i - 1;
			}
			// transfer from choose i
			else if (f[i][j][k] == f[i - 1][j - 1][k - (p[i] - d[i])] + (p[i] + d[i]))
			{
				res[cntt++] = i;
				k = k - (p[i] - d[i]), i = i - 1, j = j - 1;
			}
		}

		int numP = 0, numD = 0;
		for (int i = 0; i < cntt; i++)
			numP += p[res[i]], numD += d[res[i]];

		cout << "Jury #" << cnt << endl;
		cout << "Best jury has value " << numP << " for prosecution and value " << numD << " for defence:" << endl;
		for (int i = cntt - 1; i >= 0; i--)
			cout << " " << res[i];
		cout << endl; cout << endl;
	}
	return 0;
}

🌗AcWing 6447. 最长的括号匹配

原题链接
我的代码

状态表示: f[i] 表示以 i 结尾的最长有效括号子串的长度

状态转移:

  1. if s[i - 1], s[i] == (): f[i] = f[i - 2] + 2
  2. if s[i - 1], s[i] == )) && s[i - f[i - 1] - 1]: f[i] = f[i - 1] + 2 + f[i - f[i - 1] -2]
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
#include<iostream>
using namespace std;

const int N = 30010;
int f[N];

int main()
{
	string s;
	cin >> s;

	int size = s.size();

	for (int i = 1; i < size; i++)
	{
		if (s[i] == ')' && s[i - 1] == '(')
			f[i] = (i >= 2 ? f[i - 2] : 0) + 2;
		
		if (s[i] == ')' && s[i - 1] == ')' && i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] == '(')
			f[i] = f[i - 1] + 2 + (i - f[i - 1] - 2 >= 0 ? f[i - f[i - 1] - 2] : 0);
		
	}

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

区间 DP

🌖AcWing 282. 石子合并

原题链接
我的代码

状态表示：f[i][j] <=> 区间 [i, j] 的石子合并成一堆的最小代价

状态转移:

  1. if i == j, f[i][j] = s[i]
  2. if i != j, f[i][j] = min{ f[i][k] + f[k + 1][j] } + sum{ s[i] + ... + s[j] }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
	// ...
	for (int i = 1; i <= n; i++) s[i] += s[i - 1];

	memset(f, 0x3f, sizeof f);
	for (int len = 2; len <= n; len++)
	{
		for (int l = 1; l <= n - len + 1; l++)
		{
			int r = l + len - 1;
			if (l == r)
			{
				f[l][r] = 0;
				continue;
			}
			int t = s[r] - s[l - 1];
			for (int k = l; k < r; k++)
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + t);
		}
	}
}

🌗AcWing 283. 多边形

原题链接
我的代码

N 边形去掉一条边后可以拉伸成一条线。对于枚举去掉的边，可以通过将数组重复一次简化。

状态表示:

  1. fmax[l][r] 表示将区间为 [l, r] 的所有点计算成一个点的最大值
  2. fmin[l][r] 表示将区间为 [l, r] 的所有点计算成一个点的最小值

状态转移:

  1. if op == +
    • fmax[l][r] = max{ fmax[l][t] + fmax[t + 1][r] }
    • fmin[l][r] = min{ fmin[l][t] + fmin[t + 1][r] }
  2. if op == *
    • v1 = fmax[l][t] * fmax[t + 1][r]
    • v2 = fmax[l][t] * fmin[t + 1][r]
    • v3 = fmin[l][t] * fmax[t + 1][r]
    • v4 = fmin[l][t] * fmin[t + 1][r]
    • fmax[l][r] = max(v1, v2, v3, v4)
    • fmin[l][r] = min(v1, v2, v3, v4)
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
#include<iostream>
#include<string.h>
using namespace std;

const int N = 110, INF = 0x3f3f3f3f;
int S[N], Fmin[N][N], Fmax[N][N], U[N];
char P[N];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> P[i] >> S[i];
	
	for (int i = n + 1; i <= n + n; i++)
		P[i] = P[i - n], S[i] = S[i - n];

	int res = -INF;
	for (int k = 1; k <= n; k++)
	{
		memset(Fmin, INF, sizeof Fmin);
		memset(Fmax, -INF, sizeof Fmax);
		for (int len = 1; len <= n; len++)
		{
			for (int l = k; l <= n - len + k; l++)
			{
				int r = len + l - 1;
				if (l == r)
				{
					Fmin[l][r] = Fmax[l][r] = S[l];
					continue;
				}

				for (int t = l; t < r; t++)
				{
					if (P[t + 1] == 't')
					{
						Fmax[l][r] = max(Fmax[l][r], Fmax[l][t] + Fmax[t + 1][r]);
						Fmin[l][r] = min(Fmin[l][r], Fmin[l][t] + Fmin[t + 1][r]);
					}
					else
					{
						int v1 = Fmax[l][t] * Fmax[t + 1][r];
						int v2 = Fmax[l][t] * Fmin[t + 1][r];
						int v3 = Fmin[l][t] * Fmax[t + 1][r];
						int v4 = Fmin[l][t] * Fmin[t + 1][r];


						int maxv = max(max(v1, v2), max(v3, v4));
						int minv = min(min(v1, v2), min(v3, v4));

						Fmax[l][r] = max(Fmax[l][r], maxv);
						Fmin[l][r] = min(Fmin[l][r], minv);
					}
				}
			}
		}
		U[k] = Fmax[k][k + n - 1];
		res = max(res, U[k]);
	}

	cout << res << endl;
	for (int i = 1; i <= n; i++)
		if (U[i] == res) cout << i << " ";
	cout << endl;
	return 0;
}

计数 DP

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

状态压缩 DP

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

树形 DP

🌗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 6040. 小木棍

原题链接
我的代码

可以发现，当 n ≥ 21 时，答案的前缀按 n % 7 排序的最优前缀是:

888,108,188,200,208,288,688

其余一直在尾部填 8 即可。

对于 n < 21 时，特判即可。

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

const int num[7] = { 0,1,2,4,6,7,8 };
const int sum[7] = { 6,2,5,4,6,3,7 };
const int INF = 0x3f3f3f3f;

string solution()
{
	int n;
	cin >> n;

	string res = "";
	while (n > 14)
	{
		n -= 7;
		res.push_back('8');
	}

	switch (n)
	{
	case 0:
		return "-1";
	case 1:
		return "-1";
	case 2:
		return "1";
	case 3:
		return "7";
	case 4:
		return "4";
	case 5:
		return "2";
	case 6:
		return "6";
	case 7:
		return "8";
	case 8:
		return "10" + res;
	case 9:
		return "18" + res;
	case 10:
	{
		string tmp = res;
		if (tmp.size()) 
		{
			tmp.pop_back(); 
			return "200" + tmp;
		}
		return "22" + res;
	}
	case 11:
		return "20" + res;
	case 12:
		return "28" + res;
	case 13:
		return "68" + res;
	case 14:
		return "88" + res;
	default:
		return "-1";
	}
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		string res = solution();
		cout << res << endl;
	}
	return 0;
}

Huffman 树

🌖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 6039. 地图探险

原题链接
我的代码

略。

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
#include<iostream>
#include<string.h>
using namespace std;

const int N = 1010;
char map[N][N];
bool flags[N][N];
pair<int, int> offsets[4] = { {0,1},{1,0},{0,-1},{-1,0} };

struct State
{
	int x, y;
	int d;

	State() {}
	State(int x, int y, int d) :x(x), y(y), d(d) {}
};

void solution()
{
	int n, m, k;
	cin >> n >> m >> k;

	int bx, by, bd;
	cin >> bx >> by >> bd;

	memset(map, 'x', sizeof map);
	memset(flags, false, sizeof flags);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> map[i][j];

	int res = 1;
	State state(bx, by, bd);
	flags[state.x][state.y] = true;

	while (k--)
	{
		int nx = state.x + offsets[state.d].first;
		int ny = state.y + offsets[state.d].second;
		int nd = state.d;
		
		if (map[nx][ny] == 'x')
		{
			nd = (state.d + 1) % 4;
			state.d = nd;
			continue;
		}
		
		state.x = nx, state.y = ny;
		if (!flags[state.x][state.y])
		{
			flags[state.x][state.y] = true;
			res++;
		}
	}

	cout << res << endl;
}

int main()
{
	int T;
	cin >> T;

	while (T--)
		solution();

	return 0;
}

🌕AcWing 6038. 扑克牌

原题链接
我的代码

略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <unordered_set>

using namespace std;

int main()
{
    int n;
    cin >> n;

    unordered_set<string> s;
    while (n--)
    {
        string str;
        cin >> str;
        s.insert(str);
    }

    cout << 52 - (int)s.size() << endl;
    return 0;
}

🌕AcWing 5719. 词频统计

原题链接
我的代码

略。

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
#include<iostream>
using namespace std;

const int N = 110;

// cnt[i][j] 第 i 篇文章包含单词 j 的个数
// total[j] 所有文章包含单词 j 个个数
int cnt[N][N], total[N];
int res1[N], res2[N];

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

	for (int i = 1; i <= n; i++)
	{
		int l; cin >> l;
		for (int j = 1; j <= l; j++)
		{
			int w; cin >> w;
			cnt[i][w]++; total[w]++;
		}
	}

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			res1[i] += (cnt[j][i] > 0);

	for (int i = 1; i <= m; i++)
		res2[i] = total[i];

	for (int i = 1; i <= m; i++)
		cout << res1[i] << " " << res2[i] << endl;
	
	return 0;
}

🌕AcWing 5720. 相似度计算

原题链接
我的代码

略。

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
#include<iostream>
#include<unordered_set>
#include<cstring>
using namespace std;

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

	unordered_set<string> a, b, c;
	
	for (int i = 0; i < n; i++)
	{
		string s; cin >> s;
		for (auto& c : s) c = tolower(c);
		a.insert(s), c.insert(s);
	}
	
	for (int i = 0; i < m; i++)
	{
		string s; cin >> s;
		for (auto& c : s) c = tolower(c);
		b.insert(s), c.insert(s);
	}

	cout << a.size() + b.size() - c.size() << endl;
	cout << c.size() << endl;
	return 0;
}

🌕AcWing 5416. 因子化简

原题链接
我的代码

略。

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
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

bool compare(pair<LL, int> &a, pair<LL, int> &b)
{
	return a.second > b.second;
}

void solution()
{
	LL n, k;
	cin >> n >> k;

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

	LL res = 1;
	for (auto t : map)
		if (t.second >= k) res *= pow(t.first, t.second);
	cout << res << endl;
}

int main()
{
	int q;
	cin >> q;
	while (q--)
		solution();

	return 0;
}

中模拟

🌗AcWing 5722. 十滴水

原题链接
我的代码

略。

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
#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;

const int N = 300010;

PII q[N];
int l[N], r[N], w[N];
unordered_map<int, int> map;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int c, m, n;
	cin >> c >> m >> n;

	for (int i = 1; i <= m; i++)
		cin >> q[i].first >> q[i].second;
	sort(q + 1, q + m + 1);

	for (int i = 1; i <= m; i++)
	{
		l[i] = i - 1, r[i] = i + 1;
		w[i] = q[i].second;
		map[q[i].first] = i;
	}

	int res = m;
	while (n--)
	{
		int p;
		cin >> p;

		p = map[p];
		w[p]++;

		while (w[p] >= 5)
		{
			res--;
			int np = 0, L = l[p], R = r[p];
			r[L] = R, l[R] = L;
			if (R <= m && ++w[R] >= 5) np = R;
			if (L && ++w[L] >= 5) np = L;
			p = np;
		}
		cout << res << endl;
	}

	return 0;
}

大模拟

其他