算法每日一题6

竞赛 / 算法 / 每日一题
Word count: 3.2k   |   Reading time≈ 14 min

每日一题

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

1、分解质因数

lanqiao-1559：分解质因数 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：简单数论、质因数分解

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

  1. image-20230405021119535

解决代码：

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
#include<bits/stdc++.h>
using namespace std;
// 分解质因数
int p[20];  //p[]记录因子，p[1]是最小因子。一个int数的质因子最多有10几个
int c[40];  //c[i]记录第i个因子的个数。一个因子的个数最多有30几个 

int getFactor(int n){
	int m = 0;
	for(int i=2;i<=sqrt(n);++i){
		if(n%i==0){// i为n因子 
			p[++m] = i, c[m] = 0;// 存储第m个因子以及其个数 
			while(n%i==0){
				n /= i,c[m]++;
			}
		}
	} 
	if(n>1){// 剩下的整数 
		p[++m] = n, c[m] = 1;
	}
	return m;
} 

int main() {
	int a, b;
	cin>>a>>b;
	for(int i=a;i<=b;++i){
		int m = getFactor(i);
		cout<<i<<"=";
		for(int k=1;k<=m;++k){
			for(int j=1;j<=c[k];++j){
				cout<<p[k];
				if(j<c[k])cout<<"*";
			}
			if(k<m)cout<<"*";
		}
		cout<<endl;
	}
	return 0;
}

2、最少砝码

lanqiao-1461：最少砝码 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：思维训练、找规律

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

  1. image-20230405105822797

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
// 最少砝码 
int cnt = 0;
int R, N;

int main() {
	cin>>N;
	while(R<N){
		R = 3*R+1;// 推导出的公式 
		cnt++; 
	}
	cout<<cnt;
	return 0;
}

3、砍竹子

lanqiao-2117：砍竹子 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：思维训练、找规律

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

  1. 正解：思维。这样计算最少砍刀数：

    （1）首先计算最多砍多少刀，计算每棵竹子砍到1需要多少刀，所有竹子砍数相加得到一个总数，记为ans；

    （2）记录每棵竹子每次被砍后的新高度；

    （3）比较任意两个相邻的竹子，它们是否有相同的高度，如果有相同的高度，这两棵竹子接下来可以一起砍，从而少砍一刀，ans减一；

    （4）比较结束后，ans就是答案。

解决代码：

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
#include<bits/stdc++.h>
using namespace std;
// 砍竹子 
typedef long long ll;
const int N = 2e5+10;
int n;
ll total = 0;// 存储对所有竹子一棵一棵的砍的总次数
ll cnt = 0;// 记录少砍多少刀
ll x;// 输入竹子的高度
unordered_set<ll>h[N]; // 定义了一个类型为set的数组，即h[i]就是一个set 

ll sqr(ll n){// 由于数据过大时使用sqrt会出现误差 
	ll x = sqrt(n);// 由于精度问题进行调整 
	if((x+1)*(x+1)<=n)x = x+1;
	else if(x*x>n)x = x-1;
	return x; 
}

int main() {
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x;
		while(x>1){// 竹子高度大于1时 
			total++;
			if(h[i-1].count(x))cnt++;// 必须保证是连续的具有相同高度的竹子
			h[i].insert(x);// 存储当前第i个竹子的多个高度情况 
			x = sqr(x/2+1);// 砍一刀之后剩下的高度 
		}
	}
	cout<<total-cnt;
	return 0;
}

4、排列小球

lanqiao-546：排列小球 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：思维训练、dfs

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

  1. 初步看题可知为枚举各种颜色小球的数量，来实现递增序列，故确定思路为dfs.

  2. 我们应该如何枚举小球呢？可以利用递增条件，记录上一次枚举的数量，下一次枚举需要大于这个数量；

  3. dfs(sum,x,last)表示还需要sum个球中，前面选了颜色为last色的，x个球；

  4. 如果接着再选j个颜色为i的，为dfs(sum-j,j,i)；

  5. 递归边界所有球都用完，方案数加一。dfs过程中需要注意两个问题：

     （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
30
#include<bits/stdc++.h>
using namespace std;
// 排列小球
int nums[3];// 存储R,G,B的个数
int res = 0, total = 0;// 分别为方案数、小球总数 

void dfs(int sum, int x, int color){// 深度优先搜索 
	if(sum==0){
		++res;// 方案数+1 
		return ;
	}
	for(int i=0;i<3;++i){
		if(i==color)continue;// 颜色相同则换另一种颜色的球
		for(int j=x+1;j<=nums[i];++j){// j从上一个颜色的球的个数+1开始遍历(球的数量递增) 
			nums[i] -= j;
			if(sum>=j)dfs(sum-j, j, i);
			nums[i] += j;// 恢复现场 
		} 
	}
}

int main() {
	for(int i=0;i<3;++i){
		cin>>nums[i];
		total += nums[i];
	}
	dfs(total, 0, -1);
	cout<<res;
	return 0;
}

5、LCIS

lanqiao-1190：LCIS - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：思维训练、LCS、LIS

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

  1. 这题是动态规划问题经典问题

    在动态规划中，最长公共子序列（LCS）与最长上升子序列（LIS）是基础的线性DP,本题要求求出两个不等长序列的最长公共上升子序列。

    本体解法就是在最长公共子序列上找一遍最长上升子序列即可。

    求解最长公共子序列，也就是在判断a[i] = = b[j]的前提下，再求出上升序列；

    dp[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；

    dp[i][j]的值等于该集合的子序列中长度的最大值；

  2. 状态方程：

    对于当处于(a[i], b[j]) 状态时 ,由于dp状态就决定了，b[j]是一定作为这个状态下LICS的结尾的，所以对于a[i]，就有两种情况，将其纳入LCIS或者不纳入，首先先说不把a[i]纳入LCIS的情况：

    （1）若是 a[i] != b[j] ，显然是一定不能讲a[i]与b[j]进行配对的，那么问题就缩小成了a的前i - 1个字符与b的前j个字符且以b[j]结尾的LCIS，即dp[i - 1, j]也就是说 ，i之前的以b[j]结尾的序列自然没有改变，长度仍然是dp[i−1][j]; 若是a[i] == b[i] 如果不想要a[i]与b[j]进行配对，是不是也会得到上面的结果，故当不想a[i]与b[j]配对(或无法配对)时，dp[i, j] = dp[i - 1, j]

    （2）当a[i] == b[j]且它们进行配对时，就要在a串前i - 1个字符和b的前j - 1个字符中找到一个最长的序列，设这个序列以k结尾且b[k] < b[j]，就等价于dp[i][j]=max(dp[i - 1, k]) + 1

    最后再遍历一边dp[n][1~m]，找出其中最大值即可。

解决代码：

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
#include<bits/stdc++.h>
using namespace std;
// LCIS ——在求LCS的过程中求LIS 
int a[2010], b[2010], dp[2010][2010];// dp[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合
int n, m;
int res = 0;

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

	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i]==b[j]){// 匹配 
				dp[i][j] = 1;// 表示初始的上升序列都是1 
				for(int k=1;k<j;++k){
					if(b[k]<b[j]){
						dp[i][j] = max(dp[i-1][k]+1, dp[i][j]);
					}
				}
			}else{// 不匹配 
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	for(int j=1;j<=m;++j){
		res = max(res, dp[n][j]);
	}
	cout<<res;
	return 0;
}

6、蓝桥公园

lanqiao-1121：蓝桥公园- 蓝桥云课 (lanqiao.cn)

image-20230405163054608

完成时间：2023年4月5日

tags：图论、Floyd算法

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

  1. 在代码中，0x3f经常被用作一个特殊的数值，比如在动态规划中，可以将dp数组初始化为0x3f，表示还没有任何状态值被更新过，相当于无限大的意思。(0x3f的十进制数为63)

  2. const long long INF = 0x3f3f3f3f3f3f3f3fLL; //这样定义INF的好处是: INF <= INF+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
#include<bits/stdc++.h>
using namespace std;
// 蓝桥公园 
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;// 这样定义INF的好处是: INF <= INF+x 防止溢出
int n, m, q;
int u, v;
ll w;
int st, ed;
ll dp[405][405];// dp[i][j]:从i到j的距离 

void floyd(){// Floyd算法 
	for(int k=1;k<=n;++k){// k必须在最外循环层 
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
			}
		} 
	}
}

int main() {
	cin>>n>>m>>q;
	memset(dp, 0x3f, sizeof(dp));// 初始化, 0x3f在这里指代INF
	for(int i=1;i<=m;++i){// 存储图 
		cin>>u>>v>>w;
		dp[u][v] = dp[v][u] = min(dp[u][v], w);// 避免重边 
	} 
	floyd();
	for(int i=1;i<=q;++i){
		cin>>st>>ed;
		if(dp[st][ed]==INF)cout<<-1<<endl;// 不可达 
		else if(st==ed)cout<<0<<endl;	// 确保dp[i][i]=0（符合逻辑） 
		else cout<<dp[st][ed]<<endl;
	}
	return 0;
}

7、蓝桥王国

lanqiao-1121：蓝桥王国 - 蓝桥云课 (lanqiao.cn)

image-20230405171822310

完成时间：2023年4月5日

tags：图论、Dijkstra算法

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

  1. 维护两个集合：已确定最短路径的结点集合A、这些结点向外扩散的邻居结点集合B。

    （1）把起点s放到A中，把s所有的邻居放到B中。此时，邻居到s的距离就是直连距离。

    （2）从B中找出距离起点s最短的结点u，放到A中。

    （3）把u所有的新邻居放到B中。显然，u的每一条边都连接了一个邻居，每个新邻居都要加进去。其中u的一个新邻居v，它到s的距离dis(s, v)等于dis(s, u) + dis(u, v)。

    （4）重复(2)、(3)，直到B为空时，结束。

解决代码：

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
#include<bits/stdc++.h>
using namespace std;
// 蓝桥王国 ——Dijkstra算法 
const int N = 3e5+10;
using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;// 定义INF，并且保证了INF<=INF+x，防止溢出
 
struct edge{
	int from, to;// 起点，终点 ,起点from并没有用到，eg[i]的i就是from
	ll w;// 权重(距离) 
	edge(int a, int b, ll c){
		from = a;
		to = b;
		w = c;
	}
};

struct s_node{
	int id;ll n_dis;// 点id，当前点到起点的距离
	s_node(int a, ll b){
		id = a;
		n_dis = b;
	} 
	bool operator <(const s_node&a)const{
		return n_dis>a.n_dis;// 实现优先队列根据n_dis升序排序？？？ 
	} 
};

int n, m;
vector<edge>eg[N];// 存储图——相当于是一个二维数组 
ll dis[N];// 存储点i到起点的距离
bool done[N];// true标记已经找到了最短路径 

/*_______________需要打印路径时加上以下代码____________________*/
int pre[N];// 存储当前结点的前一结点，方便打印路径
void print_path(int s, int t){// 打印从s到t的最短路
	if(s==t){// 打印起点
		cout<<s<<" ";
		return ;
	}
	print_path(s, pre[t]);// 先打印前一个点
	cout<<t<<" ";// 后打印当前点。最后打印的是终点t
} 
/*____________________________________________________________*/

void dijkstra(){// Dijkstra算法 
	int s = 1;// 起点id 
	for(int i=1;i<=n;++i){
		dis[i] = INF;// 初始化距离为无穷大 
		done[i] = false; // 初始都为找到最短路径 
	}
	dis[s] = 0;// 起点到自己本身的距离为0 
	priority_queue<s_node>Q;// 优先队列存储新邻居结点——默认大顶堆 
	Q.push(s_node(s, dis[s]));// 将起点存储到其中 
	while(!Q.empty()){
		s_node u = Q.top();
		Q.pop();
		if(done[u.id])continue;// 如果已经找到了，就跳过继续往下 
		done[u.id] = true;// 标记找到最短路径 
		for(int i=0;i<eg[u.id].size();++i){
			edge y = eg[u.id][i];// 得到当前点u与其临界点之间的边 
			if(done[y.to])continue;
			if(dis[y.to]>y.w+u.n_dis){
				dis[y.to] = y.w+u.n_dis;// 更新最短距离 
				Q.push(s_node(y.to, dis[y.to]));// 增加新邻居结点 
				//pre[y.to] = u.id;// 如果有需要，记录路径
			}
		} 
	}
	//print_path(s, n);// 如果有需要，打印路径: 起点1，终点n
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i)eg[i].clear();// 清除可能存在的元素 
	int u,v;
	ll w;
	for(int i=1;i<=m;++i){
		cin>>u>>v>>w;
		eg[u].push_back(edge(u, v, w));// 单向，如果是双向，则再怎加eg[v].push_back()即可 
	} 
	dijkstra();// 调用Dijkstra算法 
	for(int i=1;i<=n;++i){// 1~n个点 
		if(dis[i]>=INF)cout<<"-1 ";
		else cout<<dis[i]<<" ";
	}
	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.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信