写给 C 语言用户的 C++ 竞赛入门笔记

注意 cin 读字符串时会自动跳过前导空白，如果需要保留整行（空格也留下），就用 getline。要去前导零，把 " " 换成 "0" 就行。

子串截取与拼接

#include <iostream>
#include <string>
using namespace std;

int main(void) {
    string s = "hello , world";
    // 从第 0 个位置截取长 5 的子串
    string s1 = s.substr(0, 5);
    // 从第 6 个位置截到末尾
    string s2 = s.substr(6);
    // 拼起来
    string s3 = s1 + s2;
    // 下面两行输出一样
    cout << s1 << s2 << "\n";
    cout << s3;
}

substr 很好记：起始位置 + 长度，省略长度就取到尾部。

几个用起来就放不下的操作

sort 远比冒泡快

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

bool comp(int& a, int& b) {
    return a > b;
}

int main(void) {
    int a[1000] = {0, 1, 1, 4, 5, 1, 4};
    // sort 区间是左闭右开，a+1 到 a+7
    sort(a + 1, a + 1 + 6);
    for (int i = 1; i <= 6; i++) cout << a[i];
    
    // 默认升序，想降序就传个 comp
    cout << "\n";
    sort(a + 1, a + 1 + 6, comp);
    for (int i = 1; i <= 6; i++) cout << a[i];
}

复杂度 O(nlogn)。comp 里用了引用 & 避免拷贝，数据量不大时不加也没事，但加上是习惯。

数组去重一条龙

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(void) {
    int a[1000] = {0, 1, 1, 4, 5, 1, 4};
    sort(a + 1, a + 1 + 6);
    
    // unique 把重复元素挤到末尾，返回新逻辑结尾
    int* pos = unique(a + 1, a + 1 + 6);
    int new_count = pos - (a + 1);
    for (int i = 1; i <= new_count; i++) cout << a[i] << " ";
}

unique 不真正删除元素，所以必须用返回值算新长度，或者搭配 vector 的 erase。

二分查找现成的轮子

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(void) {
    int a[105];
    for (int i = 1; i <= 100; i++) a[i] = i;
    
    // 第一个不小于 25 的位置
    int* lb1 = lower_bound(a + 1, a + 101, 25);
    int index1 = lb1 - a;
    cout << "elem is " << *(lb1) << " index is " << index1 << endl;
    
    // 第一个大于 25 的位置
    int* ub2 = upper_bound(a + 1, a + 101, 25);
    int index2 = ub2 - a;
    cout << "elem is " << *(ub2) << " index is " << index2 << endl;
    
    // 查不到就返回尾后
    int* result = lower_bound(a + 1, a + 101, 101);
    if (result == a + 101) {
        cout << "lower_bound(101) return a+101\n";
    }
    return 0;
}

lower_bound 和 upper_bound 要求区间有序，返回值是指针（或迭代器），相减得到下标。

STL 容器：栈、队列、映射、集合

算法题里高频出现的结构，STL 都给准备好了。

先进先出队列

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main(void) {
    queue<int> q;
    for (int i = 0; i < 10; i++) q.push(i);
    
    while (!q.empty()) {
        cout << q.front() << " " << q.back() << "\n";
        q.pop();
    }
    
    // 双端队列两头都能操作
    deque<int> qu;
    for (int i = 0; i < 10; i++) {
        qu.push_back(i);
        // 也可以 qu.push_front(i);
    }
    while (!qu.empty()) {
        cout << qu.front() << " " << qu.back() << "\n";
        qu.pop_back();
        qu.pop_front();
    }
}

queue 内部通常用数组实现，所有操作 O(1)。拿不准有多少元素时，while (!q.empty()) 是标准套路。

后进先出栈

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

int main(void) {
    stack<int> s;
    for (int i = 0; i < 10; i++) s.push(i);
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

接口和队列几乎一样，只是 front 换成了 top，弹出的是最后进去的那个。

键值对 map

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;

int main(void) {
    map<int, int> mp;
    int temp = 114514;
    for (int i = 0; i < 10; i++) {
        if (i < 4) mp[i] = temp * (10 - i);
        else mp.insert({i, temp * (10 - i)});
    }
    
    // 遍历
    for (auto& [key, value] : mp) {
        cout << "mp[" << key << "] = " << value << "\n";
    }
    
    // 查找
    if (mp.find(2) != mp.end()) cout << "Yes";
    if (mp.find(10) == mp.end()) cout << "No";
    cout << "\n";
    
    int idx = 0;
    while (1) {
        mp.erase(idx);
        idx++;
        if (mp.empty()) {
            cout << "已弹出所有元素";
            break;
        }
    }
    return 0;
}

底层是红黑树，插入、查找、删除都是 O(logn)。如果不需要有序，改用 unordered_map，哈希表 O(1) 更香。

自动排序去重的 set

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main(void) {
    set<int> s;
    for (int i = 0; i < 100; i++) s.insert(0);   // 只会留一个0
    s.insert(5);
    s.insert(3);
    s.insert(114514);
    
    for (auto i : s) cout << i << " ";
    cout << "\n";
    
    if (s.find(3) != s.end()) cout << "Yes" << " ";
    if (s.find(6) == s.end()) cout << "No" << " ";
    cout << "\n";
    
    cout << s.size() << "\n";
    for (auto i : s) s.erase(i);
    cout << s.size() << "\n";
    return 0;
}

相当于只有 key 的 map，集合内元素默认升序且唯一。复杂度也是 O(logn)。

竞赛常用的几个进阶招式

关掉同步，提速 IO

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

碰到大量输入输出的题，加上这三行，能甩开 C 风格 IO 的差距。

lambda 让比较就地解决

std::vector<int> arr = {1, 1, 4, 5, 1, 4};
std::sort(arr.begin(), arr.end(), [](int& a, int& b) { return a > b; });

不需要再单独写一个 comp 函数，lambda 表达式直接嵌在调用处，可读性不错。

优先队列自定义排序

struct Node {
    int x, y;
    bool operator<(Node &a) const {
        return x < a.x;
    };
};

int main(void) {
    std::priority_queue<Node> q;
}

priority_queue 默认是大顶堆，如果存的是结构体，必须重载 <，否则不知道怎么比大小。插入弹出 O(logn)，取堆顶 O(1)。

stringstream 做转换和分割

#include <vector>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;

int main(void) {
    // 字符串转数字
    string s = "1 2 3 4 5 6";
    vector<int> arr;
    stringstream stream(s);
    int num;
    while (stream >> num) {
        arr.push_back(num);
    }
    for (auto i : arr) cout << i << " ";
    cout << "\n";
    
    // 按逗号分割
    string data = "apple,banana,orange,grape";
    stringstream ss(data);
    string fruit;
    while (getline(ss, fruit, ',')) cout << fruit << endl;
    return 0;
}

stringstream 既能将带空格的字符串拆成数字，也能按指定分隔符切分，在一道题里做完输入预处理。

这些差不多就是 C++ 基础部分中最实用的内容了。搞开发的话，异常处理、内存管理、模板之类还得深挖，但单纯为了打比赛或者写点小工具，这些已经覆盖了八成的场景。