Bài Giải Đề Luyện Tập ACM Hrbust 2024 Tuần Thứ 9 (A-B)
HowieHz
Ngày đăng: 06/11/2024
Kiến thức chia sẻ > Phân tích cuộc thi > Lưu trữ bài giải
Các bài liên quan
- Tổng hợp các bài giải luyện tập thuật toán
Lời mở đầu
Liên kết đề bài: Đề tuần thứ 9 cho sinh viên khóa 2024 (DFS && BFS) - Virtual Judge.
Bài A
Link gốc: B3622 Liệt kê tập con (thực hiện bằng đệ quy kiểu mũ). Nguồn: [Luogu].
Mã nguồn Python:
1
2
3
4
5
6
7
8
9
10
|
arr = [0] * 11
def dfs(site):
if site == n + 1:
print("".join(arr[1:site]))
if site <= n:
for j in ["N", "Y"]:
arr[site] = j
dfs(site + 1)
n = int(input())
dfs(1)
|
Mã nguồn C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m;
char arr[11], s[2] = {'N', 'Y'};
void dfs(int cur) {
if (cur == m + 1) {
for (int j = 1; j <= cur - 1; ++j) printf("%c", arr[j]);
printf("\n");
}
if (cur <= m) {
for (int j = 0; j <= 1; ++j) {
arr[cur] = s[j];
dfs(cur + 1);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
scanf("%d", &m);
dfs(1);
return 0;
}
|
Bài B
Link gốc: P1706 Toàn bộ hoán vị - [Luogu], T1735 Hoán vị toàn phần - [Jisuanke].
Mã nguồn C++:
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr)
const int N = 10; // Dựa trên chỉ số 1
int n;
int a[N]; // Ghi lại dãy số đã sử dụng
bool st[N]; // Kiểm tra số có được sử dụng hay chưa
void dfs(int cur) {
if (cur == n + 1) {
for (int i = 1; i <= n; ++i) {
cout << std::setw(5) << a[i];
}
cout << endl;
return;
}
for (int i = 1; i <= n; ++i) {
if (st[i]) continue;
a[cur] = i;
st[i] = true;
dfs(cur + 1);
a[cur] = 0;
st[i] = false;
}
}
void solve() {
cin >> n;
dfs(1);
}
int main() {
ios;
int T = 1;
while (T--) {
solve();
}
}
|
Mã nguồn Python:
Mã này hoạt động tốt trên Luogu nhưng bị timeout ở điểm cuối cùng trên Jisuanke, có thể do hiệu suất đệ quy của Python thấp.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
N = 10
a = [0] * N
st = [False] * N
def dfs(cur):
if cur == n + 1:
print("".join(f"{x:5}" for x in a[1:n + 1]))
for i in range(1, n + 1):
if st[i]: continue
a[cur] = i
st[i] = True
dfs(cur + 1)
a[cur] = 0
st[i] = False
n = int(input())
dfs(1)
|
Bài C
Link gốc: HNOI 2003 - [Luogu]
Mã nguồn C++:
1
|
// Chưa cung cấp mã nguồn
|
Bài D
Python Code:
1
|
// Chưa cung cấp mã nguồn
|
Bài E
Python Code:
1
|
// Chưa cung cấp mã nguồn
|
Bài F
Link gốc: [Chưa xác định]
Mã nguồn C++:
1
|
// Chưa cung cấp mã nguồn
|
Một cách thực hiện khác:
1
|
// Chưa cung cấp mã nguồn
|
Bài G
Link gốc: [Chưa xác định]
Mã nguồn Python:
1
|
// Chưa cung cấp mã nguồn
|
Bài H
Link gốc: [Chưa xác định]
1
|
// Chưa cung cấp mã nguồn
|
Bài viết gợi ý
- 2024-09-16: Luyện tập ACM Hrbust 2024 - Tuần 4 - Bài giải từ A đến G và J-O.
- 2024-09-09: Luyện tập ACM Hrbust 2024 - Tuần 3 - Bài giải chi tiết.
- 2024-09-02: Luyện tập ACM Hrbust 2024 - Tuần 1 và 2 - Tổng hợp bài giải.
Hy vọng những chia sẻ trên sẽ giúp ích cho quá trình học tập của bạn. Chúc bạn thành công!
Lưu ý: Nếu bạn gặp khó khăn trong việc hiểu hoặc triển khai các đoạn mã, đừng ngần ngại để lại bình luận hoặc thắc mắc dưới bài viết này.