算法每日一题4

2023-04-11

竞赛 / 算法 / 每日一题

Word count: 2.4k | Reading time≈ 11 min

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、装箱问题

lanqiao-763：装箱问题 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月3日

tags：动态规划、线性DP 01-背包简化版

$\textcolor{red}{分析：}$

使得剩余的空间最小，那么就是要装的体积要最大；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 装箱问题——01-背包简化版（即w=v） 
const int N = 2e4+10;
int V, n;
int v[31];
int dp[N];

int main() {
	cin>>V>>n;
	for(int i=1;i<=n;++i){
		cin>>v[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=V;j>=v[i];--j){// 空间压缩：自我滚动 
			dp[j] = max(dp[j], dp[j-v[i]]+v[i]);
		}
	} 
	cout<<V-dp[V];// 箱子剩余的空间大小 
	return 0;
}

2、01-背包的方案数

lanqiao-2186：01-背包的方案数 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月3日

tags：动态规划、01-背包的方案数

$\textcolor{red}{分析：}$

dp[i][j][k]分别为前i个数选择了j个数，并且这j个数的和为k；

- 定义dp[][][]：dp[i][j][k]表示数字1~i取j个，和为k的方案数。
- 下面的分析沿用标准0/1背包的分析方法。
- 从i~1扩展到i，分两种情况：
（1）k≥i。数i可以要，也可以不要。
	要i。从1~i-1中取j-1个数，再取i，等价于dp[i-1][j-1][k-i]。
	不要i。从1~i-1中取j个数，等价于dp[i-1][j][k]
      合起来：dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-i]
（2）k<i。由于数i比总和k还大，显然i不能用。有：dp[i][j][k] = dp[i-1][j][k]

1~i个数 选0个和为0的情况只有一种那就是不选
for(int i=0;i<=2022;i++)    dp[i][0][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

3. 思考：为什么 `dp[i][j>0][0]` 不初始化为1呢？为什么 `dp[i][0][j>0]` 不初始化为1呢？

4. 使用自滚动数组进行空间压缩时j必须从大到小。

解决代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
// 01-背包的方案数
using ll = long long;
ll dp[2222][11][2222];// dp[i][j][k]分别为前i个数选择了j个数，并且这j个数的和为k 
int n = 2022; 

int main() {
	// 初始化
	for(int i=0;i<=2022;++i)dp[i][0][0] = 1; // 1~i个数 选0个和为0的情况只有一种那就是不选
	for(int i=1;i<=2022;++i){// 必须是正整数 
		for(int j=1;j<=10;++j){
			for(int k=1;k<=2022;++k){
				dp[i][j][k] = dp[i-1][j][k];
				if(k>=i){// k是当前需要的总和，如果k比1~i中的i还大的话，那么就可以选i或者也可不选 
					dp[i][j][k] = dp[i][j][k]+dp[i-1][j-1][k-i];// 将两种请况合起来 
				}
			}
		}
	} 
	cout<<dp[2022][10][2022];
	return 0;
}
/*空间压缩：自滚动数组*/
#include<bits/stdc++.h>
using namespace std;
// 01-背包的方案数
using ll = long long;
ll dp[11][2222];// dp[i][j][k]分别为前i个数选择了j个数，并且这j个数的和为k 
int n = 2022; 

int main() {
	// 初始化
	dp[0][0] = 1; // 1~i个数 选0个和为0的情况只有一种那就是不选
	for(int i=1;i<=2022;++i){// 必须是正整数 
		for(int j=10;j>=1;--j){// j必须从大的开始
			for(int k=i;k<=2022;++k){// 这里直接满足了k>=i的条件 
				dp[j][k] = dp[j][k]+dp[j-1][k-i];// 将两种请况合起来 
			}
		}
	} 
	cout<<dp[10][2022];
	return 0;
}

3、过河卒

lanqiao-755：过河卒 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月3日

tags：动态规划、网格图上的DP

$\textcolor{red}{分析：}$

采用标数法；
统计路径条数，看起来是个搜索题，可以用DFS求解。把马的控制点标记为不能走，绕过它们。不过，用DFS搜索的路径数量是天文数字，肯定超时。
在小学上过奥数的都知道，这题应该用“标数法”，就是在每个坐标点上记录能走的路径条数。
标数法实际上就是DP的递推。
定义状态dp[][]：dp[i][j]表示卒走到坐标(i, j)时能走的路径条数。
如果不考虑马的控制点，有： dp[i][j] = dp[i - 1][j] + dp[i][j - 1];也就是(i, j)点的路径条数等于它上面和左边的路径条数之和。这就是小学奥数的“标数法”的原理。
本题的限制条件是马的控制点，只要令控制点的dp[i][j] = 0即可，即这个点上无路径。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 过河卒——网格图上的DP 
using ll = long long;
int xb, yb, xh, yh;// 分别表示 B 点坐标和马的坐标
ll dp[25][25];// 注意不要数组溢出了 
bool control[25][25];// 标记控制点，如果为1，则为控制点

int main() {
	cin>>xb>>yb>>xh>>yh;
	int bx = xb + 2, by = yb + 2, hx = xh + 2, hy = yh + 2;// 全部坐标+2防止马向左或上跳2格导致数组越界
	control[hx][hy]=1;// 标记马的控制点
	control[hx-2][hy-1] = 1, control[hx-1][hy-2] = 1, control[hx+1][hy-2] = 1, control[hx+2][hy-1] = 1;
	control[hx+2][hy+1] = 1, control[hx+1][hy+2] = 1, control[hx-1][hy+2] = 1, control[hx-2][hy+1] = 1;
	dp[2][1] = 1;// 初始化 
	for(int i=2;i<=bx;++i){
		for(int j=2;j<=by;++j){
			if(control[i][j])dp[i][j] = 0;
			else{
				dp[i][j] = dp[i-1][j] + dp[i][j-1];
			}
		}
	}
	cout<<dp[bx][by];
//	printf("%lld", dp[bx][by]);
	return 0;
}

4、小明的背包 2

lanqiao-1175：第十四届蓝桥杯省赛冲刺营【第二期】 - 【课后练习】小明的背包 2 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：动态规划、完全背包

$\textcolor{red}{分析：}$

自滚动数组进行空间压缩时，j从小到大（区别于01-背包问题）；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 完全背包问题 
const int N = 1e3+10;
int n, V;
int dp[N];// 自滚动数组 
int w, v;

int main() {
	cin>>n>>V;
	for(int i=1;i<=n;++i){
		cin>>w>>v;// 体积、价值 
		for(int j=w;j<=V;++j){
			dp[j] = max(dp[j], dp[j-w]+v);
		}
	}
	cout<<dp[V];
	return 0;
}

5、最长公共子序列

lanqiao-1189：第十四届蓝桥杯省赛冲刺营【第二期】 - 【课后练习】最长公共子序列 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：动态规划

$\textcolor{red}{分析：}$

分解为2种情况：

（1）当ai = bj时，已求得Ai-1和Bj-1的最长公共子序列，在其尾部加上ai 或bj即可得到Ai和Bj的最长公共子序列。状态转移方程： dp[i][j] = dp[i-1][j-1] + 1

（2）当ai ≠ bj时，求解两个子问题： Ai-1和Bj的最长公共子序列；Ai和Bj-1的最长公共子序列。取最大值，状态转移方程： dp[i][j] = max{dp[i][j-1], dp[i-1][j]}

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 最长公共子序列
const int N = 1e3+10;
int a[N], b[N];
int n, m;
int dp[N][N];

int main() {
	cin>>n>>m;
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	for(int i=0;i<m;++i){
		cin>>b[i];
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			if(a[i]==b[j])dp[i+1][j+1] = dp[i][j]+1;// 取dp[i+1][j+1]，而不是dp[i][j]是因为(i,j)从0开始,防止数组越界 
			else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
		}
	}
	cout<<dp[n][m];
	return 0;
}

6、蓝桥勇士

lanqiao-1175：第十四届蓝桥杯省赛冲刺营【第二期】 - 【课后练习】蓝桥勇士 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：动态规划、LIS

$\textcolor{red}{分析：}$

经典的C++问题——最长上升子序列（LIS）；
最初始状态的长度都为1；
定义dp[i]为以a[i]为结尾的最长上升子序列的长度。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 最长递增子序列 
const int N = 1e3+10;
int n, res = 0;
int a[N];
int dp[N]; 

int main() {
	cin>>n;
	for(int i=0;i<n;++i){// 初始化 
		cin>>a[i];
		dp[i] = 1;// 最初长度都为1 
	}
	for(int i=1;i<n;++i){ 
		for(int j=0;j<i;++j){
			if(a[j]<a[i]){
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
		res = max(res, dp[i]);// 存储最大长度，最答长度不一定在dp[n] 
	}
	cout<<res;
	return 0;
}

7、快速幂

lanqiao-1514：快速幂 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：简单数论

$\textcolor{red}{分析：}$

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 快速幂
using ll = long long;
ll b, p, k;

ll fastPow(ll b, ll p, ll k){
	ll res = 1;
	b %= k; // 防止下方res*b越界 
	while(p){// p为次数 
		if(p&1)res = (res*b)%k;
		b = b*b%k;// 对应于a^1,a^2,a^3…… 其中的指数代表的是n二进制中第几位的1（如：1011）
		p = p>>1;// 右移一位 
	}
	return res;
}

int main() {
	cin>>b>>p>>k;
	cout<<fastPow(b, p, k);
	return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.