蓝桥杯 C++ 基础与常用内容

一、竞赛环境与要求

1.1 官方编译环境

  • IDE: Dev-C++ 5.11
  • 编译器: GCC 4.9.2
  • C++ 标准: C++11

1.2 代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

    // 代码内容

    return 0;
}

二、C++11 核心特性

2.1 auto 类型推导

  • 用途: 自动推导变量类型，简化代码
  • 示例: 
    1
2
3
4
5

    auto a = 10;         // int
auto b = 3.14;       // double
auto c = "hello";    // const char*
auto& d = a;         // int&
const auto& e = b;   // const double&

2.2 范围 for 循环

  • 用途: 简化容器遍历
  • 示例: 
    1
2
3
4

    vector<int> nums = {1, 2, 3, 4, 5};
for (const auto& num : nums) {
    cout << num << " ";
}

2.3 结构化绑定 (C++17)

  • 用途: 方便地解包 pair、tuple 等复合类型
  • 示例: 
    1
2
3
4

    map<string, int> scores = {{"Alice", 95}, {"Bob", 88}};
for (const auto& [name, score] : scores) {
    cout << name << ": " << score << endl;
}

2.4 智能指针

  • 用途: 自动管理内存，避免内存泄漏
  • 示例: 
    1
2

    unique_ptr<int> p1(new int(10));
shared_ptr<int> p2 = make_shared<int>(20);

三、常用 STL 容器

3.1 vector

  • 特点: 动态数组，支持随机访问
  • 常用操作: 
    1
2
3
4
5
6

    vector<int> v;
v.push_back(1);
v.pop_back();
v.size();
v.empty();
v.clear();

3.2 map / set

  • 特点: 有序，基于红黑树实现
  • 常用操作: 
    1
2
3
4
5
6
7
8
9

    map<string, int> m;
m["key"] = value;
m.find("key");
m.count("key");

set<int> s;
s.insert(1);
s.erase(1);
s.find(1);

3.3 unordered_map / unordered_set

  • 特点: 无序，基于哈希表实现，查找速度快
  • 常用操作: 
    1
2
3

    unordered_map<string, int> um;
um["key"] = value;
um.find("key");

3.4 queue / priority_queue

  • 特点: 队列 (FIFO) / 优先队列 (最大堆)
  • 常用操作: 
    1
2
3
4
5
6
7
8
9

    queue<int> q;
q.push(1);
q.pop();
q.front();

priority_queue<int> pq;
pq.push(1);
pq.pop();
pq.top();

3.5 stack

  • 特点: 栈 (LIFO)
  • 常用操作: 
    1
2
3
4

    stack<int> s;
s.push(1);
s.pop();
s.top();

3.6 deque

  • 特点: 双端队列，支持两端操作
  • 常用操作: 
    1
2
3
4
5

    deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_back();
dq.pop_front();

3.7 bitset

  • 特点: 位集合，高效的位操作
  • 常用操作: 
    1
2
3
4
5

    bitset<32> b;
b.set(0);
b.reset(0);
b.flip();
b.count();

四、常用算法

4.1 排序与查找

  • sort: 排序 
    1
2

    sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>());
  • lower_bound / upper_bound: 二分查找 
    1

    auto it = lower_bound(v.begin(), v.end(), x);

4.2 数值算法

  • max_element / min_element: 找最大/最小值
  • accumulate: 累加 
    1

    int sum = accumulate(v.begin(), v.end(), 0);

4.3 其他常用算法

  • reverse: 反转
  • unique: 去重
  • fill: 填充
  • copy: 复制

五、竞赛常用技巧

5.1 输入输出优化

1
2
3

ios::sync_with_stdio(false);
cin.tie(nullptr);
// 对于大数据量输入，考虑使用 scanf/printf

5.2 数据类型

  • int: 通常为 32 位，范围约 ±2e9
  • long long: 64 位，范围约 ±9e18
  • 注意: 蓝桥杯题目中，很多情况下需要使用 long long 避免溢出

5.3 常用宏定义

1
2
3
4

#define endl '\n'
#define int long long
#define INF 0x3f3f3f3f
#define MOD 1000000007

5.4 常见问题处理

  • 数组越界: 确保索引在有效范围内
  • 内存溢出: 合理使用容器，避免栈溢出
  • 时间超限: 优化算法，使用合适的数据结构
  • 精度问题: 浮点数比较时使用误差范围

六、经典算法模板

6.1 二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

6.2 深度优先搜索 (DFS)

1
2
3
4
5
6
7
8

void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

6.3 广度优先搜索 (BFS)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void bfs(int start, vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

6.4 快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void quick_sort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int pivot = nums[left + (right - left) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    quick_sort(nums, left, j);
    quick_sort(nums, i, right);
}

6.5 动态规划

  • 最长递增子序列: 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 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);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

七、蓝桥杯常见题型

7.1 暴力枚举

  • 特点: 直接枚举所有可能的情况
  • 适用场景: 数据规模较小的题目

7.2 模拟

  • 特点: 按照题目要求模拟整个过程
  • 适用场景: 流程明确的题目

7.3 动态规划

  • 特点: 利用子问题的解来解决原问题
  • 适用场景: 具有最优子结构和重叠子问题的题目

7.4 贪心

  • 特点: 每一步都做出局部最优选择
  • 适用场景: 具有贪心选择性质的题目

7.5 图论

  • 特点: 处理与图相关的问题
  • 适用场景: 路径、连通性等问题

7.6 数学

  • 特点: 利用数学知识解决问题
  • 适用场景: 数论、组合数学等问题