Hrbust ACM练习 2024级第9周题单 题解分享 (A-B)

相关文章链接

• 算法题练习 题解分享 文章汇总

前言

题单链接：2024级第九周题单(DFS && BFS) - Virtual Judge (vjudge.net)

A 题

原题链接：B3622 枚举子集（递归实现指数型枚举） - 洛谷

Python Code

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)

Cpp Code

#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 题

原题链接：P1706 全排列问题 - 洛谷、T1735 全排列问题 - 计蒜客

Cpp Code

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr)

const int N = 10;  // 1 based
int n;
int a[N];    // 记录已经使用的数字构成的序列
bool st[N];  // 记录数字是否使用

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

Python Code 洛谷能过，计蒜客上最后一个点会超时，可能是 Python 递归效率低导致的

```python
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)

C 题

原题：HNOI 2003
洛谷链接：

Cpp Code

Cpp Code

D 题

Python Code

E 题

Python Code

F 题

原题链接：

Cpp Code

Cpp Code 另一种实现

G 题

原题链接：

Python Code

H 题

原题链接：