精选1-15道完整的信奥赛C++算法题

发布于：2025-12-06 阅读：255

以下是15道完整的信奥赛C++算法题，每道题包含题目描述、输入输出格式、样例和C++参考代码。这里15题精选涵盖各核心算法类型的代表性题目。

📝 一、模拟与基础数学

1. 数字反转

题目描述：给定一个整数，请将该数各个位上数字反转得到一个新数。新数不应有前导零。
输入格式：一个整数 N（-1,000,000,000 ≤ N ≤ 1,000,000,000）
输出格式：反转后的新数
样例输入：

text

-380

样例输出：

text

-83

C++代码：

cpp

#include <iostream>#include <string>#include <algorithm>using namespace std;int main() {
    int n;
    cin >> n;
    
    string s = to_string(abs(n));  // 转为字符串并取绝对值
    std::reverse(s.begin(), s.end());  // 反转字符串
    
    // 去除前导零
    int i = 0;
    while (i < s.length() - 1 && s[i] == '0') {
        i++;
    }
    s = s.substr(i);
    
    // 输出结果
    if (n < 0) {
        cout << "-";
    }
    cout << s << endl;
    
    return 0;}

2. 陶陶摘苹果（NOIP2005普及组）

题目描述：陶陶有一张30cm高的凳子，当她不能直接用手摘到苹果时，会站到凳子上再试试。现在已知10个苹果到地面的高度，以及陶陶把手伸直能够到的最大高度，请帮她算一下她能够摘到的苹果数目。
输入格式：

第一行：10个整数，表示苹果到地面的高度
第二行：一个整数，表示陶陶把手伸直能够到的最大高度
输出格式：一个整数，表示陶陶能够摘到的苹果数目
样例输入：

text

100 200 150 140 129 134 167 198 200 111
110

样例输出：

text

C++代码：

cpp

#include <iostream>using namespace std;int main() {
    int apples[10];
    for (int i = 0; i < 10; i++) {
        cin >> apples[i];
    }
    
    int tao_height;
    cin >> tao_height;
    
    int chair_height = 30;
    int total_height = tao_height + chair_height;
    
    int count = 0;
    for (int i = 0; i < 10; i++) {
        if (apples[i] <= total_height) {
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;}

🎯 二、贪心算法

3. 部分背包问题

题目描述：有n件物品和一个容量为C的背包。第i件物品的重量是w_i，价值是v_i。你可以选择物品的一部分放入背包，其价值按重量比例计算。问背包能装入的最大总价值。
输入格式：

第一行：两个整数n和C
接下来n行：每行两个整数w_i, v_i
输出格式：一个浮点数，表示最大总价值，精确到小数点后两位
样例输入：

text

样例输出：

text

240.00

C++代码：

cpp

#include <iostream>#include <iomanip>#include <algorithm>#include <vector>using namespace std;struct Item {
    int weight;
    int value;
    double value_per_weight;};bool compare(Item a, Item b) {
    return a.value_per_weight > b.value_per_weight;}int main() {
    int n, C;
    cin >> n >> C;
    
    vector<Item> items(n);
    for (int i = 0; i < n; i++) {
        cin >> items[i].weight >> items[i].value;
        items[i].value_per_weight = (double)items[i].value / items[i].weight;
    }
    
    // 按单位重量价值降序排序
    sort(items.begin(), items.end(), compare);
    
    double total_value = 0.0;
    int remaining_capacity = C;
    
    for (int i = 0; i < n && remaining_capacity > 0; i++) {
        if (items[i].weight <= remaining_capacity) {
            // 全部装入
            total_value += items[i].value;
            remaining_capacity -= items[i].weight;
        } else {
            // 装入部分
            total_value += items[i].value_per_weight * remaining_capacity;
            remaining_capacity = 0;
        }
    }
    
    cout << fixed << setprecision(2) << total_value << endl;
    
    return 0;}

4. 排队接水

题目描述：有n个人在一个水龙头前排队接水，第i个人接水所需时间为t_i。请安排他们的排队顺序，使得所有人的平均等待时间最小。
输入格式：

第一行：一个整数n
第二行：n个整数，表示t_i
输出格式：
第一行：最优的排队顺序（编号，从1开始）
第二行：最小的平均等待时间（保留两位小数）
样例输入：

text

5
3 1 4 2 5

样例输出：

text

2 4 1 3 5
5.10

C++代码：

cpp

#include <iostream>#include <iomanip>#include <algorithm>#include <vector>using namespace std;struct Person {
    int id;
    int time;};bool compare(Person a, Person b) {
    return a.time < b.time;}int main() {
    int n;
    cin >> n;
    
    vector<Person> people(n);
    for (int i = 0; i < n; i++) {
        cin >> people[i].time;
        people[i].id = i + 1;
    }
    
    // 按接水时间升序排序
    sort(people.begin(), people.end(), compare);
    
    // 输出排队顺序
    for (int i = 0; i < n; i++) {
        cout << people[i].id;
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    
    // 计算总等待时间和平均等待时间
    long long total_wait_time = 0;
    long long current_wait = 0;
    
    for (int i = 0; i < n - 1; i++) {
        current_wait += people[i].time;
        total_wait_time += current_wait;
    }
    
    double average_wait_time = (double)total_wait_time / n;
    cout << fixed << setprecision(2) << average_wait_time << endl;
    
    return 0;}

🔍 三、搜索算法（DFS/BFS）

5. 全排列问题

题目描述：输出自然数1到n所有不重复的排列，即n的全排列，按字典序输出。
输入格式：一个整数n（1 ≤ n ≤ 8）
输出格式：所有1~n的全排列，每行一个排列，数字间用空格分隔
样例输入：

text

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;vector<vector<int>> result;void backtrack(vector<int>& nums, int start, int n) {
    if (start == n) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(nums[start], nums[i]);
        backtrack(nums, start + 1, n);
        swap(nums[start], nums[i]);  // 回溯
    }}int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    
    backtrack(nums, 0, n);
    
    // 按字典序排序
    sort(result.begin(), result.end());
    
    // 输出结果
    for (const auto& perm : result) {
        for (int i = 0; i < n; i++) {
            cout << perm[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
    }
    
    return 0;}

6. 迷宫最短路径（BFS）

题目描述：给定一个N×M的迷宫（1代表墙壁，0代表通路），求从左上角(0,0)到右下角(N-1,M-1)的最短路径步数。只能上下左右移动。
输入格式：

第一行：两个整数N, M
接下来N行：每行M个整数（0或1）
输出格式：一个整数，表示最短路径步数。如果无法到达，输出-1
样例输入：

text

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <queue>using namespace std;struct Point {
    int x, y, steps;};int bfs(vector<vector<int>>& maze, int N, int M) {
    if (maze[0][0] == 1 || maze[N-1][M-1] == 1) {
        return -1;
    }
    
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    queue<Point> q;
    
    // 方向数组：上下左右
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    q.push({0, 0, 0});
    visited[0][0] = true;
    
    while (!q.empty()) {
        Point current = q.front();
        q.pop();
        
        // 到达终点
        if (current.x == N-1 && current.y == M-1) {
            return current.steps;
        }
        
        // 探索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && 
                !visited[nx][ny] && maze[nx][ny] == 0) {
                visited[nx][ny] = true;
                q.push({nx, ny, current.steps + 1});
            }
        }
    }
    
    return -1;}int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> maze(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> maze[i][j];
        }
    }
    
    int result = bfs(maze, N, M);
    cout << result << endl;
    
    return 0;}

🧠 四、动态规划

7. 数字三角形

题目描述：给定一个由数字组成的三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或右下方的结点，一直走到底层，请找出一条路径，使路径上经过的数字之和最大。
输入格式：

第一行：一个整数n，表示三角形的层数
接下来n行：第i行有i个整数
输出格式：一个整数，表示最大和
样例输入：

text

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> triangle(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    
    // 动态规划：从底部向上计算
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }
    
    cout << triangle[0][0] << endl;
    
    return 0;}

8. 最长上升子序列（LIS）

题目描述：给定一个长度为n的整数序列，求出它的最长上升子序列的长度（严格上升）。
输入格式：

第一行：一个整数n
第二行：n个整数
输出格式：一个整数，表示最长上升子序列的长度
样例输入：

text

7
1 7 3 5 9 4 8

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    // 方法1：动态规划 O(n^2)
    vector<int> dp(n, 1);  // dp[i]表示以nums[i]结尾的最长上升子序列长度
    int max_len = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    
    cout << max_len << endl;
    
    return 0;}

9. 0-1背包问题

题目描述：有n件物品和一个容量为C的背包。第i件物品的重量是w_i，价值是v_i。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且总价值最大。
输入格式：

第一行：两个整数n和C
接下来n行：每行两个整数w_i, v_i
输出格式：一个整数，表示最大的总价值
样例输入：

text

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {
    int n, C;
    cin >> n >> C;
    
    vector<int> weight(n), value(n);
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    
    // 动态规划：dp[i][j]表示前i个物品，容量为j时的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(C + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            // 不选第i个物品
            dp[i][j] = dp[i-1][j];
            
            // 如果能选第i个物品
            if (j >= weight[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i-1]] + value[i-1]);
            }
        }
    }
    
    cout << dp[n][C] << endl;
    
    // 空间优化版本（一维数组）
    /*
    vector<int> dp(C + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = C; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[C] << endl;
    */
    
    return 0;}

🗺️ 五、图论

10. 并查集：亲戚关系

题目描述：如果两个人是亲戚，那么他们的亲戚也是亲戚。给定n个人和m条亲戚关系，回答q个询问，判断两人是否为亲戚。
输入格式：

第一行：三个整数n, m, q
接下来m行：每行两个整数a, b，表示a和b是亲戚
接下来q行：每行两个整数x, y，询问x和y是否为亲戚
输出格式：对于每个询问，输出一行"Yes"或"No"
样例输入：

text

样例输出：

text

Yes
Yes
No

C++代码：

cpp

#include <iostream>#include <vector>using namespace std;class UnionFind {private:
    vector<int> parent;
    vector<int> rank;
    public:
    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按秩合并
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
    
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }};int main() {
    int n, m, q;
    cin >> n >> m >> q;
    
    UnionFind uf(n);
    
    // 建立亲戚关系
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        uf.unite(a, b);
    }
    
    // 回答询问
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        if (uf.isConnected(x, y)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;}

11. Dijkstra单源最短路径

题目描述：给定一个n个点，m条边的有向图（无向图），边权非负。求从点1到点n的最短路径长度。
输入格式：

第一行：两个整数n, m
接下来m行：每行三个整数u, v, w，表示从u到v有一条权值为w的边
输出格式：一个整数，表示从1到n的最短路径长度。如果不存在，输出-1
样例输入：

text

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;struct Edge {
    int to;
    int weight;};struct Node {
    int id;
    int dist;
    
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }};int dijkstra(int n, vector<vector<Edge>>& graph) {
    vector<int> dist(n + 1, INT_MAX);
    vector<bool> visited(n + 1, false);
    
    dist[1] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({1, 0});
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        if (visited[current.id]) continue;
        visited[current.id] = true;
        
        for (const Edge& edge : graph[current.id]) {
            int newDist = current.dist + edge.weight;
            if (newDist < dist[edge.to]) {
                dist[edge.to] = newDist;
                pq.push({edge.to, newDist});
            }
        }
    }
    
    return (dist[n] == INT_MAX) ? -1 : dist[n];}int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<Edge>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        // 如果是无向图，加上下面这行
        // graph[v].push_back({u, w});
    }
    
    int result = dijkstra(n, graph);
    cout << result << endl;
    
    return 0;}

12. 最小生成树（Kruskal算法）

题目描述：给定一个无向图，求其最小生成树的边权之和。
输入格式：

第一行：两个整数n, m
接下来m行：每行三个整数u, v, w，表示点u和点v之间有一条权值为w的边
输出格式：一个整数，表示最小生成树的边权之和。如果图不连通，输出"orz"
样例输入：

text

样例输出：

text

C++代码：

cpp

#include <iostream>#include <vector>#include <algorithm>using namespace std;struct Edge {
    int u, v, weight;
    
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }};class UnionFind {private:
    vector<int> parent;
    public:
    UnionFind(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
            return true;
        }
        return false;
    }};int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    
    int total_weight = 0;
    int edges_used = 0;
    
    for (const Edge& edge : edges) {
        if (uf.unite(edge.u, edge.v)) {
            total_weight += edge.weight;
            edges_used++;
            if (edges_used == n - 1) {
                break;
            }
        }
    }
    
    if (edges_used == n - 1) {
        return total_weight;
    } else {
        return -1;  // 表示图不连通
    }}int main() {
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }
    
    int result = kruskal(n, edges);
    if (result == -1) {
        cout << "orz" << endl;
    } else {
        cout << result << endl;
    }
    
    return 0;}

📊 六、高级数据结构

13. 线段树：区间求和

题目描述：给定一个长度为n的数组，支持两种操作：

将某个区间内的所有数加上一个值
查询某个区间内所有数的和
输入格式：

第一行：两个整数n, m
第二行：n个整数，表示初始数组
接下来m行：每行一个操作。操作格式为：

1 l r k：表示将区间[l, r]内每个数加上k
2 l r：表示询问区间[l, r]内所有数的和
输出格式：对于每个操作2，输出一行一个整数，表示区间和
样例输入：

text

样例输出：

text

15
21
20

C++代码：

cpp

#include <iostream>#include <vector>using namespace std;class SegmentTree {private:
    vector<long long> tree;
    vector<long long> lazy;
    int n;
    
    void build(const vector<int>& nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
        } else {
            int mid = (start + end) / 2;
            build(nums, node * 2, start, mid);
            build(nums, node * 2 + 1, mid + 1, end);
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }
    
    void push_down(int node, int start, int end) {
        if (lazy[node] != 0) {
            int mid = (start + end) / 2;
            tree[node * 2] += lazy[node] * (mid - start + 1);
            tree[node * 2 + 1] += lazy[node] * (end - mid);
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy

转载请注明出处：英飞凌中国代理（官网）
本文地址：https://www.oliyun.com/algorithm/179.html

请用手机淘宝APP扫一扫二维码关注我们；获取资料与芯片样品

标签： C++

上一篇: 没有了！

下一篇: 精选16-35道信奥赛C++算法题

CSP-J/S考试大纲知识点

文章标题：CSP-J/S考试大纲知识点分类名称知识点编程入门程序的基本结构main函数、输入输出语句、Dev C++的使用变量和常量变量

2025-12-09
英飞凌MCU嵌入式开发工具平台

使用工具平台为英飞凌MCU（包括CYT2B73）生成嵌入式C代码，并不是一个单一的操作，而是涉及选择工具链、配置项目、生成代码的系统化工程流程。基于车身控制器和A···

2025-12-06
英飞凌CYT2B73芯片 BCM嵌入式C语言代码

基于CYT2B73芯片，BCM嵌入式C语言代码如下：一、系统架构总览与代码规模说明首先，你需要理解基于AUTOSAR架构的软件是如何组织的，下图清晰地展示了其分层结构以···

2025-12-06
英飞凌CYT2B73CADQ0AZEGS集成控制车门车窗车灯雨刮车钥匙的嵌入式C语言代码

CYT2B73CADQ0AZEGS 是一款高性能的车规级微控制器（MCU），而不是像车钥匙、雨刮电机这样的独立终端器件。CYT2B73CADQ0AZEGS是作为智能“大脑”，即车身控制模块···

2025-12-06
车门MCU嵌入式C语言代码

车门控制系统是现代汽车中最复杂的车身电子模块之一，它集成了安全、舒适、网络通信等多种功能。根据车型定位（经济型、豪华型、智能电动车）和安全要求（QM到AS···

2025-12-06

精选1-15道完整的信奥赛C++算法题

📝 一、模拟与基础数学

1. 数字反转

2. 陶陶摘苹果（NOIP2005普及组）

🎯 二、贪心算法

3. 部分背包问题

4. 排队接水

🔍 三、搜索算法（DFS/BFS）

5. 全排列问题

6. 迷宫最短路径（BFS）

🧠 四、动态规划

7. 数字三角形

8. 最长上升子序列（LIS）

9. 0-1背包问题

🗺️ 五、图论

10. 并查集：亲戚关系

11. Dijkstra单源最短路径

12. 最小生成树（Kruskal算法）

📊 六、高级数据结构

13. 线段树：区间求和

请用手机淘宝APP扫一扫二维码关注我们；获取资料与芯片样品

CSP-J/S考试大纲知识点

英飞凌MCU嵌入式开发工具平台

英飞凌CYT2B73芯片 BCM嵌入式C语言代码

英飞凌CYT2B73CADQ0AZEGS集成控制车门车窗车灯雨刮车钥匙的嵌入式C语言代码

车门MCU嵌入式C语言代码