有基础班_day06课上题目

zxcvbnm

2025-07-07 15:10:12

发布于：上海

25阅读

0回复

0点赞

题目
抽奖1
抽奖2
抽奖3
抽奖4
迷宫的相邻点
迷宫之判定
迷宫之方案数

抽奖1

题目大意

从编号为 1、2、3 的小球中 有放回地抽取 3 次，输出所有可能的抽取结果，并按字典序输出。

题意分析

有放回，意味着每次都可以抽 1、2、3 中任意一个；
抽取 3 次，总共有 $3^3 = 27$ 种组合；
每组输出一个序列，共 3 个数，按字典序排序。

解题思路

每个位置都可以是 1、2、3；
用三重循环枚举所有可能；
因为 1 到 3 本身就是有序的，按顺序枚举自然满足字典序。

时间复杂度解析

总共 $3^3 = 27$ 种情况；
每种情况输出 3 个数；
所以时间复杂度为 $O(1)$ ，极小，直接枚举即可。

代码演示

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 3; i++) {        // 第一次抽
        for (int j = 1; j <= 3; j++) {    // 第二次抽
            for (int k = 1; k <= 3; k++) {// 第三次抽
                // 输出当前抽法
                cout << i << " " << j << " " << k << endl;
            }
        }
    }
    return 0;
}

抽奖2

题目大意

给定一个整数 $n$ ，表示有编号为 $1$ 到 $n$ 的 $n$ 个球，每次从中有放回地抽一个球，共抽 $n$ 次。请你输出所有可能的抽取情况，要求按字典序输出。

题意分析

每一轮抽奖都可以选 $1$ 到 $n$ 中的任意一个数字。
有放回：意味着每一位都可以独立选择 $n$ 个数。
抽 $n$ 次：每种结果是一个长度为 $n$ 的序列。
所有可能情况数为 $n^n$ ，在 $n=8$ 时是 $16777216$ ，可以接受。

解题思路

使用 递归 DFS 生成所有长度为 $n$ 的数字序列，序列中的每个位置可取值范围为 $1$ 到 $n$ 。

字典序要求：

因为我们在递归中从小到大枚举，所以天然满足字典序。

时间复杂度分析

总共有 $n^n$ 个序列，每个序列长度 $n$ ，所以时间复杂度是：

总复杂度： $O(n^n)$
对于 $n = 8$ ，最多 $16777216$ 次递归调用，打印 16M 行，属于可接受范围。

代码演示

#include <iostream>
using namespace std;

int n;
int a[10]; // 存储当前序列，最多8个数字

// step 表示当前递归的层数
void dfs(int step) {
    if (step == n + 1) {
        // 已经抽取了n次，输出当前序列
        for (int i = 1; i <= n; i++) {
            cout << a[i];
            if (i < n) cout << " ";
        }
        cout << '\n';
        return;
    }

    // 当前这一步可以从1选到n
    for (int i = 1; i <= n; i++) {
        a[step] = i;
        dfs(step + 1);
    }
}

int main() {
    cin >> n;
    dfs(1); // 从第1步开始
    return 0;
}

抽奖3

题目大意

给定一个整数 $n$ ，表示有 $n$ 个球，编号从 $1$ 到 $n$ 。每次从中抽取一个球，无放回地抽 $n$ 次。求所有可能的抽取情况，按字典序输出。

题意分析

无放回意味着抽取过程中不能重复；
抽 $n$ 次，恰好把 $n$ 个数全排列一遍；
输出的本质是 $n$ 个数的全排列；
字典序输出即为 字典序排列所有全排列。

解题思路

使用 DFS+回溯 生成 $1\sim n$ 的全排列，每次选择一个未使用的数字，标记为已使用，递归下一位。

时间复杂度分析

一共 $n!$ 种情况；
每种排列打印 $n$ 个数字；
所以时间复杂度为 $O(n \times n!)$ ，最大情况 $n=8$ 时是 $8 \times 40320 = 322560$ ，可接受。

C++代码演示

#include <iostream>
using namespace std;

int n;
int a[10];       // 当前排列
bool used[10];   // 标记数字是否用过

void dfs(int step) {
    if (step == n + 1) {
        // 输出当前排列
        for (int i = 1; i <= n; i++) {
            cout << a[i];
            if (i < n) cout << " ";
        }
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            a[step] = i;     // 当前位选择 i
            used[i] = true;  // 标记 i 被用过
            dfs(step + 1);   // 递归下一位
            used[i] = false; // 回溯
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

抽奖4

题目大意

有 $n$ 个小球，每个小球有一个积分 $a[i]$ 。
每次可以有放回地抽一个小球，共抽 $n$ 次。
求所有 编号序列，使得 $n$ 次抽取的小球积分总和为 $k$ 。
要求结果按字典序输出，输出的是小球编号序列（从 1 开始编号）。

题意分析

有放回：每次都可以选任意编号的小球。
抽 $n$ 次：结果是一个长度为 $n$ 的编号序列。
要求总积分之和为 $k$ ，所以需要在枚举的同时记录并判断和。

解题思路

这是一个典型的 DFS + 剪枝 + 记录编号 的问题：

使用 DFS 每次递归代表一次抽取；
每次可以从 1 到 $n$ 中任选一个编号；
记录当前路径和对应的积分和；
当抽满 $n$ 次且积分和为 $k$ 时，输出当前路径；
需要对编号序列按字典序输出；
- 枚举顺序从小到大自然满足字典序要求；
剪枝优化：
- 当前积分和已经超过 $k$ 的时候提前剪枝，避免继续递归。

时间复杂度分析

理论上最多需要枚举 $n^n$ 种序列；
但我们通过剪枝（提前终止）可以大大减少不必要的递归；
对于 $n \le 8$ 完全可接受。

代码实现

#include <iostream>
using namespace std;

int n, k;
int a[10];        // 积分数组，a[1] ~ a[n]
int path[10];     // 当前编号选择路径

// step: 当前递归的层数（已抽了几次）
// sum: 当前积分和
void dfs(int step, int sum) {
    if (step == n + 1) {
        if (sum == k) {
            // 输出当前路径
            for (int i = 1; i <= n; i++) {
                cout << path[i];
                if (i < n) cout << " ";
            }
            cout << '\n';
        }
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (sum + a[i] > k) continue;  // 剪枝：提前终止
        path[step] = i;
        dfs(step + 1, sum + a[i]);
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; // 从下标1开始存积分，更好对应编号
    }
    dfs(1, 0);
    return 0;
}

迷宫的相邻点

题目大意

给定一个 $n \times m$ 的迷宫，以及某个格子坐标 $(x, y)$ ，请输出其右、下、左、上方向的相邻格子的坐标。如果越界则输出 NA。

题意分析

总共有 4 个方向，按照 右、下、左、上 的顺序输出。
每个方向对应一个坐标偏移值 (dx, dy)。
若相邻坐标合法（不越界），就输出相邻坐标；
若越界，则输出 NA。

解题思路

我们可以用一个方向数组来存储方向偏移，例如：

int dir[4][2] = {
    {0, 1},   // 右
    {1, 0},   // 下
    {0, -1},  // 左
    {-1, 0}   // 上
};

然后依次尝试四个方向，看相邻点是否在迷宫范围内。

代码实现

#include <iostream>
using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;

    // 右、下、左、上 四个方向
    int dir[4][2] = {
        {0, 1},   // 右
        {1, 0},   // 下
        {0, -1},  // 左
        {-1, 0}   // 上
    };

    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        // 判断是否越界
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
            cout << nx << " " << ny << endl;
        } else {
            cout << "NA" << endl;
        }
    }

    return 0;
}

迷宫之判定

题目大意

给定一个 $n \times m$ 的迷宫，其中：

'.' 表示可以走；
'#' 表示障碍物，不能走；

问能否从左上角 (0,0) 走到右下角 (n-1,m-1)。

解题思路

每次只能走上下左右 4 个方向；
不能走出边界；
不能重复走已经走过的格子；
不能走障碍物 #；
一旦到达终点，即可判断为 “YES”。

方向数组

int dx[4] = {-1, 1, 0, 0}; // 上下左右的行偏移
int dy[4] = {0, 0, -1, 1}; // 上下左右的列偏移

代码实现

#include <iostream>
using namespace std;

const int MAX = 50;
char maze[MAX][MAX];
bool visited[MAX][MAX];
int n, m;
bool found = false;

// 上下左右
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) {
        found = true;
        return;
    }

    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 判断边界和可行性
        if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
            !visited[nx][ny] && maze[nx][ny] == '.') {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }

    dfs(0, 0);

    if (found) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

迷宫之方案数

题目大意

给定一个 $N \times M$ 的迷宫，有 $T$ 个障碍点；
每个格子最多只能走一次；
从起点 $(SX, SY)$ 走到终点 $(FX, FY)$ ；
求一共有多少条可行路径。

输入解析

第一行：迷宫大小和障碍数量：N M T
第二行：起点和终点坐标：SX SY FX FY
接下来 $T$ 行：障碍坐标，不能走；
所有坐标都是 1 开始，不是 0。

解题思路

这是典型的 DFS 回溯搜索路径数：

每次尝试向上/下/左/右走；
如果下一个点可走（没越界、不是障碍、没走过）就继续；
如果走到了终点，计数器加 1；
每次递归后，记得回溯：将当前点恢复“未访问”状态。

实现细节

用一个 vis[N][M] 数组记录哪些格子已经访问过；
用一个 maze[N][M] 数组记录哪些格子是障碍；
起点终点都可能在边角，注意边界处理；
使用 dx, dy 控制方向遍历。

方向数组

int dx[4] = {-1, 1, 0, 0}; // 上下左右的行偏移
int dy[4] = {0, 0, -1, 1}; // 上下左右的列偏移

C++ 代码实现

#include <iostream>
using namespace std;

const int MAX = 10;
int N, M, T;
int SX, SY, FX, FY;
int maze[MAX][MAX];     // 1 表示障碍，0 表示可以走
bool vis[MAX][MAX];     // 是否访问过
int ans = 0;

// 方向：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
    if (x == FX && y == FY) {
        ans++;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 判断边界、是否为障碍、是否访问过
        if (nx >= 1 && nx <= N && ny >= 1 && ny <= M &&
            !vis[nx][ny] && maze[nx][ny] == 0) {
            vis[nx][ny] = true;     // 标记访问
            dfs(nx, ny);
            vis[nx][ny] = false;    // 回溯
        }
    }
}

int main() {
    cin >> N >> M >> T;
    cin >> SX >> SY >> FX >> FY;

    // 初始化障碍
    for (int i = 0; i < T; i++) {
        int x, y;
        cin >> x >> y;
        maze[x][y] = 1;
    }

    // 起点标记访问
    vis[SX][SY] = true;
    dfs(SX, SY);

    cout << ans << endl;

    return 0;
}