915-22 编程

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

作者：

张指导 , 2023-12-08 02:57:06 , 所有人可见 , 阅读 465

10

4

【前排提醒】

22年编程题共40分（15，15，10），其中第一题考察的是简单的输入输出和结构体排序，代码量略大；第二题考察的是一个比较简单的思维题，重在思考过程，代码量很小；第三题难度相比前两道要大，考察的是迭代法（二进制表示法）实现指数型子集枚举 or 递归实现指数型子集枚举。
第一题结构体排序是重点，我也给出了多种写法供大家参考，至少要熟练掌握一种。
第二题是个思维题，能想出来的话做起来就很快。https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/description/
第三题分值不大，难度却大，对于编程基础一般的同学，且所剩时间不多的情况下，可以战略性放弃，重点放在前两个编程题上。（ps：这里不是说第三道一定是最难的一道，每年情况不一定相同）。

一、无人机打靶

题目描述

有 $N$ 支队伍参赛，每个队伍的无人机成绩为 $S$ ，且每个无人机颜色被随机涂为蓝（b）、红（r）、绿（g）、紫（p）之一。

输入格式

第一行包含整数 $N$，表示参加的队伍数目，即无人机数目。
接下来 $N$ 行，每行包含每支参赛队伍的无人机颜色和打靶成绩 $S$ ，由空格分隔开。

输出格式

输出内容由两部分组成。
第一部分输出各种颜色对应的无人机数目。
第二部分根据按照成绩从大到小进行排序，输出无人机打靶成绩 $S$ 和对应的无人机颜色。

数据范围

$1 <= N <= 30$
$0 <= S <= 100$

输入样例

输出样例

blue 2
green 1
purple 1
red 1

95 purple
90 green
90 red
85 blue
80 blue

C++ 代码1：不用 sort（手写冒泡）

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 35;

struct Node 
{
    char c;
    int s;
} q[N];

// 统计每种颜色的无人机数量
unordered_map<char, int> cnt;
// 映射颜色字符到对应的颜色名
unordered_map<char, string> color{
    {'g', "green"},
    {'r', "red"},
    {'b', "blue"},
    {'p', "purple"}
};

int main()
{
    int n;
    cin >> n;

    // 输入每支参赛队伍的无人机颜色和打靶成绩
    for (int i = 0; i < n; i ++)
    {
        cin >> q[i].c >> q[i].s;
        cnt[q[i].c] ++;
    }

    // 输出各种颜色对应的无人机数目
    for (auto t : cnt)
        cout << color[t.first] << ' ' << t.second << endl;
    cout << endl;

    // 使用冒泡排序按照成绩从大到小进行排序
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
            // 如果当前位置的成绩小于后面位置的成绩，交换两者的位置
            if (q[i].s < q[j].s) 
                swap(q[i], q[j]);


    // 输出排序后的无人机打靶成绩和对应的无人机颜色
    for (int i = 0; i < n; i ++)
        cout << q[i].s << ' ' << color[q[i].c] << endl;

    return 0;
}

这段代码首先统计各种颜色的无人机数量，然后按照成绩从大到小进行排序，并输出统计结果和排序后的信息。

C++ 代码 2： sort(重载＜)

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 35;

struct Node 
{
    char c;
    int s;

    bool operator< (const Node &t) const
    {
        return s > t.s;
    }
} q[N];

// 统计每种颜色的无人机数量
unordered_map<char, int> cnt;
// 映射颜色字符到对应的颜色名
unordered_map<char, string> color{
    {'g', "green"},
    {'r', "red"},
    {'b', "blue"},
    {'p', "purple"}
};

int main()
{
    int n;
    cin >> n;

    // 输入每支参赛队伍的无人机颜色和打靶成绩
    for (int i = 0; i < n; i ++)
    {
        cin >> q[i].c >> q[i].s;
        cnt[q[i].c] ++;
    }

    // 输出各种颜色对应的无人机数目
    for (auto t : cnt)
        cout << color[t.first] << ' ' << t.second << endl;
    cout << endl;

    sort(q, q + n);

    // 输出排序后的无人机打靶成绩和对应的无人机颜色
    for (int i = 0; i < n; i ++)
        cout << q[i].s << ' ' << color[q[i].c] << endl;

    return 0;
}

C++ 代码 3： sort(自定义 cmp 比较函数)

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 35;

struct Node 
{
    char c;
    int s;
} q[N];

bool cmp(Node a, Node b)
{
    return a.s > b.s;
}

// 统计每种颜色的无人机数量
unordered_map<char, int> cnt;
// 映射颜色字符到对应的颜色名
unordered_map<char, string> color{
    {'g', "green"},
    {'r', "red"},
    {'b', "blue"},
    {'p', "purple"}
};

int main()
{
    int n;
    cin >> n;

    // 输入每支参赛队伍的无人机颜色和打靶成绩
    for (int i = 0; i < n; i ++)
    {
        cin >> q[i].c >> q[i].s;
        cnt[q[i].c] ++;
    }

    // 输出各种颜色对应的无人机数目
    for (auto t : cnt)
        cout << color[t.first] << ' ' << t.second << endl;
    cout << endl;

    sort(q, q + n, cmp);

    // 输出排序后的无人机打靶成绩和对应的无人机颜色
    for (int i = 0; i < n; i ++)
        cout << q[i].s << ' ' << color[q[i].c] << endl;

    return 0;
}

C++ 代码 4： pair写法（不用写重载和 cmp）

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

// pair 排序默认按 first 大小排，这里的 first（int）代表无人机成绩
typedef pair<int, char> PIC;

const int N = 35;

PIC q[N];

// 统计每种颜色的无人机数量
unordered_map<char, int> cnt;
// 映射颜色字符到对应的颜色名
unordered_map<char, string> color{
    {'g', "green"},
    {'r', "red"},
    {'b', "blue"},
    {'p', "purple"}
};

int main()
{
    int n;
    cin >> n;

    // 输入每支参赛队伍的无人机颜色和打靶成绩
    for (int i = 0; i < n; i ++)
    {
        cin >> q[i].second >> q[i].first;
        cnt[q[i].second] ++;
    }

    // 输出各种颜色对应的无人机数目
    for (auto t : cnt)
        cout << color[t.first] << ' ' << t.second << endl;
    cout << endl;

    // sort(q, q + n);  // 从小到大排序
    sort(q, q + n, greater<>());    // 从大到小排序

    // 输出排序后的无人机打靶成绩和对应的无人机颜色
    for (int i = 0; i < n; i ++)
        cout << q[i].first << ' ' << color[q[i].second] << endl;

    return 0;
}

C语言版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 35

struct Node
{
    char c;
    int s;
};

// 统计每种颜色的无人机数量
int cnt[128];  // Assuming ASCII characters for colors
// 映射颜色字符到对应的颜色名
char* color[128];  // Assuming ASCII characters for colors

int compare(const void *a, const void *b)
{
    return ((struct Node *)b)->s - ((struct Node *)a)->s;
}

int main()
{
    int n;
    scanf("%d", &n);

    struct Node q[N];

    // 初始化颜色映射表
    color['g'] = "green";
    color['r'] = "red";
    color['b'] = "blue";
    color['p'] = "purple";

    // 输入每支参赛队伍的无人机颜色和打靶成绩
    for (int i = 0; i < n; i++)
    {
        scanf(" %c %d", &q[i].c, &q[i].s);
        cnt[q[i].c]++;
    }

    // 输出各种颜色对应的无人机数目
    for (int i = 0; i < 128; i++)
        if (cnt[i] > 0 && color[i] != NULL)
            printf("%s %d\n", color[i], cnt[i]);
    printf("\n");

    // 使用快速排序按照成绩从大到小进行排序
    qsort(q, n, sizeof(struct Node), compare);

    // 输出排序后的无人机打靶成绩和对应的无人机颜色
    for (int i = 0; i < n; i++)
        printf("%d %s\n", q[i].s, color[q[i].c]);

    return 0;
}

二、顺子

从扑克牌中抽取5张，其中A、J、Q、K分别表示 1、11、12、13，大小王用 0 表示,如果五张牌可以连成顺序则称为顺子，大小王可以表示任意数字。现在输入五张牌的牌面，判断是否为顺子。

算法思想

最大值 - 最小值 < 5 并且 除了大小王没重复的牌 → 是顺子

bool isStraight(vector<int>& nums) {
    // 初始化最大值和最小值，maxv初始为-1确保能够取到更小的值，
    // minv初始为20确保能够取到更大的值
    int maxv = -1, minv = 20; 
    unordered_set<int> s; // 使用无序集合存储已经出现的牌面值，用于判断是否重复
    for (int x : nums) 
    {
        if (x == 0) continue; // 跳过大小王
        maxv = max(maxv, x); // 更新最大值
        minv = min(minv, x); // 更新最小值
        if (s.count(x)) return false; // 如果已经出现过该牌面值，说明不是顺子，返回false
        s.insert(x); // 将当前牌面值加入集合
    }
    return (maxv - minv) < 5; // 最大值和最小值之差小于5说明可以组成顺子
}

三、递归实现指数型枚举

计算机视觉算法：检测获取一组候选物体，每个物体具有一个特征值，其中 Wi 为正整数，现研究基于特征值选取物问题，表示为< s, c >，s={W1, W2, …, Wn}，表示候选物体的特征值集合，其中 Wi 为正整数，表示第 i 个物品的特征值；C 为正整数，代表需达到目标特征值。要求编程寻找 s 的子集，使子集中物体的特征值之和为 C.

程序输入模式：第一行包括 2 个正整数 N 和 C，N 代表 S 中候选物体总数，C 代表需要达到目标特征值；第二行包括 N 个正整数（1≤N≤100），代表 S。

程序输出格式为：满足条件的 S 的子集（1 行 1 个），或者当问题无解时，输出“None”。

#include <iostream>
#include <vector>

using namespace std;

void dfs(int u, int sum, vector<int>& path, vector<int>& candidates, int target) {
    if (sum == target) {
        // 输出满足条件的子集
        for (int val : path) {
            cout << val << ' ';
        }
        cout << endl;
        return;
    }

    for (int i = u; i < candidates.size(); i++) {
        // 剪枝：如果当前物体的特征值加上当前和已经大于目标特征值，则不继续搜索
        if (sum + candidates[i] > target) {
            continue;
        }

        path.push_back(candidates[i]);
        dfs(i + 1, sum + candidates[i], path, candidates, target);
        path.pop_back();  // 回溯
    }
}

int main() {
    int N, C;
    cin >> N >> C;

    vector<int> candidates(N);
    for (int i = 0; i < N; i++) {
        cin >> candidates[i];
    }

    vector<int> path;
    dfs(0, 0, path, candidates, C);

    if (path.empty()) {
        cout << "None" << endl;
    }

    return 0;
}

该代码通过深度优先搜索（DFS）遍历所有可能的子集，寻找满足条件的子集。在搜索过程中，通过剪枝操作，减少不必要的搜索，提高效率。最终输出满足条件的子集或者输出 “None” 表示问题无解。

另一种做法是使用动态规划（01 背包问题，但是无法输出具体方案），通过构建二维数组 dp[i][j] 表示前 i 个物体中是否存在一组特征值的和等于 j。状态转移方程为：

dp[i][j] = dp[i-1][j] or dp[i-1][j-W_i]

其中 dp[i-1][j] 表示不选择第 i 个物体，$dp[i-1][j-W_i]$ 表示选择第 i 个物体。通过填充这个二维数组，最终可以得到是否存在一组特征值的和等于 C。

这种方法的时间复杂度为 O(NC)，其中 N 为物体数目，C 为目标特征值。相较于深度优先搜索，动态规划的时间复杂度更为优秀。以下是对应的 C++ 代码：

#include <iostream>
#include <vector>

using namespace std;

// 函数判断是否存在一组特征值的和等于 target
bool canAchieveTarget(vector<int>& weights, int target) {
    int n = weights.size();
    // 创建二维数组 dp，dp[i][j] 表示前 i 个物体中是否存在一组特征值的和等于 j
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));

    // 初始化状态，当特征值和为 0 时，认为存在一组解
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // 动态规划状态转移
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            dp[i][j] = dp[i - 1][j];  // 不选择第 i 个物体

            // 如果当前目标值 j 大于等于第 i 个物体的特征值，可以选择第 i 个物体
            if (j >= weights[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - weights[i - 1]];
            }
        }
    }

    // 返回最终结果，即是否存在一组特征值的和等于 target
    return dp[n][target];
}

int main() {
    int n, target;
    cin >> n >> target;

    vector<int> weights(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }

    // 调用函数判断是否存在一组特征值的和等于 target
    if (canAchieveTarget(weights, target)) {
        cout << "Subset exists." << endl;
    } else {
        cout << "None" << endl;
    }

    return 0;
}

模板题

92. 递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式
输入一个整数 n。

输出格式
每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围
1≤n≤15
输入样例：

输出样例：

#include <iostream>

using namespace std;

const int N = 20;

int res[1 << N][N], cnt;  // res 存储结果，cnt 记录结果的数量
int n;
bool st[N]; // 记录每个位置选or不选

void dfs(int u) // u:层数
{
    if (u > n)
    {
        for (int i = 1; i <= n; i ++)
            if (st[i])
                res[cnt][i] = i;  // 记录当前选择的数
        cnt ++;
        return;
    }

    st[u] = false;  // 第一个分支：不选
    dfs(u + 1);

    st[u] = true;   // 第二个分支：选
    dfs(u + 1);
}

int main()
{
    cin >> n;

    dfs(1);

    for (int i = 0; i < cnt; i ++)
    {
        for (int j = 1; j <= n; j ++)
            if (res[i][j])
                cout << res[i][j] << ' ';
        cout << endl;
    }

    return 0;
}

算法思想：

使用深度优先搜索（DFS）进行指数型枚举，遍历每个元素时，可以选择将其加入子集或者不加入子集。

递归函数 dfs 的参数 u 表示当前遍历到的元素下标，st 数组记录当前元素是否选中。
当 u 大于 n 时，表示当前层遍历结束，将当前选择的子集记录到结果数组 res 中，同时 cnt 自增表示有一个方案。
在递归的过程中，先选择当前元素并递归，然后恢复现场（不选择当前元素）并递归，实现所有可能的组合。

最后，输出所有的方案，每行表示一种组合。

该代码的时间复杂度主要取决于深度优先搜索的次数，即搜索树的节点数。在最坏情况下，搜索树的高度为 N，因此时间复杂度为 O(2^N)。

#include <iostream>

using namespace std;

const int N = 20;

int nums[N];

int main()
{
    int n;
    cin >> n;

    // 初始化数组，表示选择的数为 1~n
    for (int i = 0; i < n; i ++) nums[i] = i + 1;

    // 通过二进制位的变化进行枚举
    for (int i = 0; i < 1 << n; i ++)
    {
        // 遍历每一位，如果该位为 1，表示选择当前位置的数
        for (int j = 0; j < n; j ++)
            if (i >> j & 1)
                cout << nums[j] << ' ';
        cout << endl;
    }

    return 0;
}

算法思想：

通过二进制位的变化进行枚举，每一位表示当前位置的数是否选中。
初始化数组 nums 表示选择的数为 1~n。
遍历从 0 到 2^n - 1 的二进制数，每一位为 1 表示选择当前位置的数，输出对应的组合方案。
输出所有的方案，每行表示一种组合。

这段代码的时间复杂度为 O(2^n)，其中 n 是输入的整数。这是因为代码使用了二进制位的变化进行枚举，对于每个数都有两种选择（选择或不选择），总共有 2^n 种组合。因此，时间复杂度与组合的总数成正比，即 O(2^n)。

相似例题

供希望进一步拔高程序设计的同学练习。

6 评论

浅笑流年 2个月前

第三题这样写可以吗？只用了几个简单的例子测试没问题

#include <iostream>

using namespace std;

const int N = 20, M = 3010;

int n, m;
int v[N], st[N];
vector<int> res;
bool flag; //dfs查找时不能用返回值来判断是否找到，因为一定会有失败的查找

void dfs(int u, int sum)
{
    if(u > n + 1 || sum > m) return ;
    if(sum == m)
    {
        for(int x : res) cout << x << " ";
        cout << endl;
        flag = true;
        return ;
    }

    res.push_back(u);
    dfs(u + 1, sum + v[u]);
    res.pop_back();

    dfs(u + 1, sum);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i];
    dfs(1, 0);
    if(!flag) cout << "None";
    return 0;
}

张指导 2个月前

那就没问题

acwing_33278 27天前

int res[1 << N][N]；
学长这里1 << N是什么意思啊

张指导 27天前

左移 n 位

Snow_raw 2023-12-12 02:13

问一下，第二题大小王可以充当任意数是不是也应当考虑

张指导 2023-12-12 09:47

最大值 - 最小值 < 5 并且除了大小王没重复的牌 → 是顺子
已经考虑了大小王

App 内打开