算法每日一题2

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

每日一题

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

1、美丽区间

lanqiao1372：题库 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月29日

tags：尺取

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

  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
#include<bits/stdc++.h>
using namespace std;
// 美丽区间 ——双指针同向搜索 
using ll = long long;

int main() {
	int n, S;
	cin>>n>>S;
	int a[n+1];
	for(int i=1;i<=n;++i)cin>>a[i];
	int ans = 1e5;
	int sum = 0;
	for(int i=1, j=1;i<=n;){// 双指针移动 
		if(sum<S){
			sum += a[i];
			++i;
		}else{
			ans = min(ans, i-j);
			sum -= a[j];
			j++;
		}
	}
	if(ans == 1e5)cout<<0;
	else cout<<ans;
	return 0;
}

2、最少砝码

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

完成时间：2023年3月29日

tags：思维、递推

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

  1. 首先，1个砝码最大称到1（砝码重量：1） ； 2个砝码最大称到4（砝码重量：1,3） ；3个砝码最大称到13 ；

  2. 推出公式为：新一级的砝码最大称重=上一级砝码上限 × 3 + 1

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin>>n;
	int sum = 0;
	int i;
	for(i=1;; i++) {
		sum = 3 * sum + 1;// 递推公式 
		if(n<=sum) {
			break;
		}
	}
	cout<<i;
	return 0;
}

3、路径之谜

lanqiao-89：路径之谜 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月30日21:27:26

tags：搜索、dfs

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

  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
#include<bits/stdc++.h>
using namespace std;
// 路径之谜——逆向思维，每走一步就取该位置处北方和西方靶子上的箭 

// 两两组合形成上下左右四个方向
//      1------------------> x
//      |
//      |
//      |
//      |
//      |
//      |
//      |
//      ↓
//      y

const int N = 21;
int n;
int col[N], row[N];// 前一个数组存储正北方向的靶子，后一个数组存储正西方向的靶子 
vector<pair<int, int>>res;// 存储路径坐标 
int direct[] = {-1, 0, 1, 0, -1};// 存储四个移动方向
bool flag[N][N];// 是否经过 
 
 
bool check(int x, int y){
	if(x==n-1&&y==n-1){// 当到达终点位置时，判断靶子是否都没有箭了 
		for(int i=0;i<n;++i){
			if(col[i]){
				return false;
			}else if(row[i]){
				return false;
			}
		}
		// 靶子上都没有箭之后进行路径输出
		for(int i=0;i<res.size();++i){
			int xt = res[i].first;
			int yt = res[i].second;
			int num = yt*n+xt;// 计算位置编号
			cout<<num<<" "; 
		} 
		return false;// 终止 
	}
	return true;// 继续遍历 
} 

bool pd(int x, int y){// 判断是否越界 
	if(x<0||x>=n||y<0||y>=n||flag[y][x]==1)return false;
	if(col[x]<=0||row[y]<=0)return false;// 靶子没箭了，但是没走到终点位置 
	return true;
}

void dfs(int x, int y){
	if(!check(x, y))return;
	else{
		int xt, yt;
		for(int i=0;i<4;++i){
			xt = direct[i]+x,yt = direct[i+1]+y;
			if(pd(xt, yt)){// 判断是否越界 
				flag[yt][xt]=1;
				res.push_back({xt, yt});
				col[xt]--;
				row[yt]--;
				dfs(xt, yt);
				flag[yt][xt]=0;
				res.pop_back();
				col[xt]++;
				row[yt]++;
			}
		}
	}
}

int main() {
	cin>>n;
	for(int i=0;i<n;++i)cin>>col[i];// 北方靶子 
	for(int i=0;i<n;++i)cin>>row[i];// 西方靶子 
	flag[0][0] = true;// 初始化入口(起点位置)
	res.push_back({0, 0});
	col[0]--;
	row[0]--;
	dfs(0, 0);// 深度优先搜索 
	return 0;
}

4、N皇后问题

lanqiao-1508：N皇后问题 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月30日

tags：搜索、dfs、回溯

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

  1. N皇后问题使用回溯法解决；

  2. 关键是要正确表示左右斜线；（左斜线：k=i+j；右斜线：k=i-j+N-1）

  3. 在每次放置皇后的时候必须保证当前位置的同一行（这里不用定义数组，直接根据递归回溯来限制同一行只能有一个皇后）、同一列（定义bool型的col[N]）以及左右斜线上（定义bool型R[2 * N],L[2 * N]）没有放置过皇后；

  4. 每放置一个位置M[i][j]就更新对应的col[j],R[i-j+N-1],L[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
#include<bits/stdc++.h>
using namespace std;

int N;
int counts = 0;// 计数

int N_queens(int i, vector<vector<int>>&M, int col[], int L[], int R[]){
	for(int j = 0;j < N;++j){// 遍历每一行的位置 
		if(!col[j]&&!R[i-j+N-1]&&!L[i+j]){// 可放置 
			M[i][j] = i+1;// 放置皇后 
			col[j] = L[i+j] = R[i-j+N-1] = 1;
			if(i == N-1){
				counts++;// 放置方法加1 
			}else{
				N_queens(i+1, M, col, L, R);
			}
			M[i][j] = 0;// 回溯-去皇后 
			col[j] = L[i+j] = R[i-j+N-1] = 0;
		}
	} 
	return counts;
}

int main() {
	cin>>N;
	vector<vector<int>>M(N, vector<int>(N, 0));// 采用int M[N][N]，不方便给函数传参，这里要用vector动态数组 
	int col[N]={0}, L[2*N]={0}, R[2*N]={0};// 1则表明存储皇后 
//	count = 0;// 计数 
	int n = N_queens(0, M, col, L, R);
	cout<<n;// 可行解数量 
	return 0;
}

5、长草

lanqiao-149：长草 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月31日

tags：搜索、bfs、曼哈顿距离

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

  1. 草地每个月往外扩张一次；

  2. 经典的bfs问题；

  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
#include<bits/stdc++.h>
using namespace std;
// 长草
// 每个月往外扩张一次
// 尝试曼哈顿距离解决本题——更快速
typedef pair<int, int> PII;
const int N = 1e3+10;
int n, m, k;
vector<PII>vec;// 存储长草的位置
bool isg[N][N];// 存储是否长草

int main() {
	cin>>n>>m;
	char ch;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			cin>>ch;
			if(ch=='g') {
				vec.push_back({i, j});
				isg[i][j] = 1;
			}
		}
	}
	cin>>k;

	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			if(!isg[i][j]) { // (i,j)位置还没长草
				for(int l=0; l<vec.size(); ++l) {
					PII p = vec[l];// 遍历当前已经长草的位置坐标
					int x = p.first;
					int y = p.second;
					int d = abs(x-i) + abs(y-j);// 曼哈顿距离 
					if(d<=k) {
						isg[i][j] = 1;// 在k月内必定会长草 
						break;// 没必要再看其它已经长草位置与(i,j)位置的曼哈顿距离 
					}
				}
			}
		}
	}
//	cout<<k;
	char tmp_c;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			if(isg[i][j]==1) {
				tmp_c = 'g';
			}else{
				tmp_c = '.';
			}
			cout<<tmp_c;
		}
		cout<<endl;
	}
	return 0;
}

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
#include<bits/stdc++.h>
using namespace std;
// 长草——bfs 

typedef pair<int, int> PII;
const int N = 1e3+10;

queue<PII>qu; // 队列
int n, m, k;
bool isg[N][N];// 标记是否长草 
int direc[] = {-1, 0, 1, 0, -1};// 方位数组 
int len;// 控制当前层队列长度，每一次将当前层的多有元素扩展之后就执行k-- 

bool pd(int x, int y){// 边界判断 
	if(x<0||x>=n||y<0||y>=m)return false;
	return true;
}


int main() {
	cin>>n>>m;
	char ch;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			cin>>ch;
			if(ch=='g') {
				qu.push({i, j});
				isg[i][j] = 1;
			}
		}
	}
	len = qu.size();
	cin>>k;
	while(k>0&&!qu.empty()){// k次循环并且队列不为空 
		PII p = qu.front();
		qu.pop();// 去除首个元素
		for(int i=0;i<4;++i){// 四个方向 
			int x = p.first + direc[i];// 控制行 
			int y = p.second + direc[i+1];// 控制列 
			if(isg[x][y]!=1&&pd(x, y)){
				isg[x][y] = 1;
				qu.push({x, y});
			}
		} 
		len--;// 当前层的元素数量-1 
		if(len==0){
			k--;// 一个月过去了 
			len = qu.size();// 更新下一层的草块个数 
		}
	}
	char tmp_c;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			if(isg[i][j]==1) {
				tmp_c = 'g';
			}else{
				tmp_c = '.';
			}
			cout<<tmp_c;
		}
		cout<<endl;
	}
	return 0;
}

6、走迷宫

lanqiao-1216：走迷宫 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年3月31日

tags：搜索、bfs

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

  1. 典型的bfs解法，当到达终点时即结束搜索（用到一个check函数）；

解决代码：

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<bits/stdc++.h>
using namespace std;
// 走迷宫 
typedef pair<int, int> PII;
const int N = 110;
int n, m; 
int G[N][N];// 网格迷宫
int direc[] = {-1, 0, 1, 0, -1};
struct node{
	int x, y;
}; 
node startNode;// 起点 
//int x1, y1;
int x2, y2;// 终点 
int visit[N][N];// 标记已经访问过的位置并存储从起点开始的距离
int ans;
queue<PII>qu;

bool pd(int x, int y){
	if(x<1||x>n||y<1||y>m||visit[x][y]!=0||G[x][y]==0)return false;
	return true;
} 

bool check(int x, int y){
	if(x==x2&&y==y2){// 到达终点坐标 
		ans = visit[x][y];// 距离
		return true; 
	}
	return false;
} 

void bfs(){// 广度优先搜索 
	while(!qu.empty()){
		PII p = qu.front();
		qu.pop();
		for(int i=0;i<4;++i){
			int x = p.first + direc[i];
			int y = p.second + direc[i+1];
			if(pd(x, y)){// 满足在矩阵内，没有访问过，可以通过 
				visit[x][y] = visit[p.first][p.second] + 1;
				qu.push({x, y}); 
			}
			if(check(x, y)){// 到达终点——结束 
				return;
			} 
		}
	}
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>G[i][j];
		}
	}
	cin>>startNode.x>>startNode.y>>x2>>y2;// 起点与终点 
	qu.push({startNode.x, startNode.y});
	visit[startNode.x][startNode.y] = 1;// 最后输出答案时减1即可
	ans = 0;
	bfs();
	if(ans==0){
		cout<<-1;
	}else{
		cout<<ans-1; 
	}
	return 0;
}

7、合根植物

lanqiao-110：合根植物 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月1日22:36:15

tags：并查集

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

  1. 利用并查集的存储、查询以及合并操作处理输入，最后通过遍历parent数组判断有多少个根节点就能够知道有多少合根植物。

解决代码：

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
#include<bits/stdc++.h>
using namespace std;

const int K = 1e6+10;
int m, n, k;
int a, b;
int parent[K];// 存储父节点 
int ans = 0;

int find(int x){// 并查集查询函数 
	if(x!=parent[x]){// 不是根节点 
		parent[x] = find(parent[x]);
	}
	return parent[x]; 
}

void unionSet(int x, int y){
	int rootX = find(x);
	int rootY = find(y);
	if(rootX!=rootY){
		parent[rootX] = rootY;// 合并，以rootY为根节点 
	}
}

int main() {
	cin>>m>>n;
	for(int i=1;i<=m*n;++i){
		parent[i] = i;// 初始化父节点为本身，即为根节点 
	}
	cin>>k;
	for(int i=0;i<k;++i){
		cin>>a>>b;
		unionSet(a, b);// 合根 
	}
	for(int i=1;i<=m*n;++i){
		if(i==parent[i]){// 判断为根节点 
			ans++;
		}
	}
	cout<<ans;
	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:

请我喝杯咖啡吧~

支付宝
微信