信息学奥林匹克竞赛常用系统函数

针对信息学奥林匹克竞赛（通常简称为信奥赛）的常用函数，以下是一份详细的文档。这份文档旨在帮助参赛者更好地理解和使用这些函数，以便在编程比赛中提高效率和准确性。

一、数学函数

1. C/C++ 标准库数学函数（需包含 `<cmath>`）

函数	说明	示例
`abs(x)`	整型绝对值	`abs(-5) = 5`
`fabs(x)`	浮点型绝对值	`fabs(-3.14) = 3.14`
`pow(x, y)`	x的y次幂	`pow(2, 3) = 8.0`
`sqrt(x)`	平方根	`sqrt(16) = 4.0`
`cbrt(x)`	立方根（C++11）	`cbrt(27) = 3.0`
`hypot(x, y)`	计算直角三角形的斜边	`hypot(3, 4) = 5.0`
`exp(x)`	e的x次幂	`exp(1) ≈ 2.71828`
`log(x)`	自然对数（以e为底）	`log(10) ≈ 2.30259`
`log10(x)`	常用对数（以10为底）	`log10(100) = 2.0`
`log2(x)`	以2为底的对数（C++11）	`log2(8) = 3.0`
`sin(x)`	正弦（x为弧度）	`sin(3.14159/2) ≈ 1.0`
`cos(x)`	余弦	`cos(0) = 1.0`
`tan(x)`	正切	`tan(0.7854) ≈ 1.0`
`asin(x)`	反正弦	`asin(1) = π/2`
`acos(x)`	反余弦	`acos(0) = π/2`
`atan(x)`	反正切	`atan(1) = π/4`
`atan2(y, x)`	计算y/x的反正切	`atan2(1, 1) = π/4`
`ceil(x)`	向上取整	`ceil(3.2) = 4.0`
`floor(x)`	向下取整	`floor(3.8) = 3.0`
`round(x)`	四舍五入	`round(3.5) = 4.0`
`trunc(x)`	截断小数部分	`trunc(3.9) = 3.0`
`fmod(x, y)`	浮点数取余	`fmod(5.3, 2) = 1.3`
`remainder(x, y)`	带舍入的余数	`remainder(5.3, 2) = 1.3`

2. 算法竞赛常用数学技巧


#include <cmath>
#include <algorithm>
using namespace std;

// 示例代码：常用数学运算
void math_examples() {
    // 1. 幂运算
    double power = pow(2, 10);  // 2^10 = 1024
    
    // 2. 开方
    double square_root = sqrt(16);  // 4.0
    double cubic_root = cbrt(27);   // 3.0
    
    // 3. 对数运算
    double ln = log(100);      // 自然对数
    double lg = log10(1000);   // 以10为底
    double lb = log2(1024);    // 以2为底
    
    // 4. 取整函数
    double up = ceil(3.1);     // 4.0
    double down = floor(3.9);  // 3.0
    double r = round(3.5);     // 4.0
    
    // 5. 三角函数（注意使用弧度）
    double rad = 45 * M_PI / 180;  // 角度转弧度
    double sin_val = sin(rad);
    double cos_val = cos(rad);
}

二、输入输出函数

1. C风格输入输出

函数	说明	效率
`scanf()`	格式化输入	高
`printf()`	格式化输出	高
`getchar()`	读取单个字符	高
`putchar()`	输出单个字符	高


#include <cstdio>

void c_io_examples() {
    int a;
    double b;
    char str[100];
    
    // 快速输入
    scanf("%d %lf", &a, &b);
    scanf("%s", str);
    
    // 快速输出
    printf("%d %.2f\n", a, b);
    printf("%s\n", str);
    
    // 字符输入输出
    char ch = getchar();
    putchar(ch);
}

2. C++风格输入输出

函数	说明	效率
`cin`	标准输入流	较低
`cout`	标准输出流	较低
`getline()`	读取一行	中等


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

void cpp_io_examples() {
    // 关闭同步，提高速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string s;
    
    // 基本输入输出
    cin >> n;
    cout << n << endl;
    
    // 读取整行
    getline(cin, s);
    
    // 格式化输出
    cout << fixed << setprecision(2) << 3.14159 << endl;
}

三、字符串处理函数

1. C风格字符串函数（需包含 `<cstring>`）

函数	说明	时间复杂度
`strlen(s)`	字符串长度	O(n)
`strcpy(dest, src)`	复制字符串	O(n)
`strcat(dest, src)`	连接字符串	O(n)
`strcmp(s1, s2)`	比较字符串	O(n)
`strstr(haystack, needle)`	查找子串	O(n×m)
`strchr(s, c)`	查找字符	O(n)
`memcpy(dest, src, n)`	内存复制	O(n)
`memset(ptr, val, n)`	内存设置	O(n)


#include <cstring>

void string_examples() {
    char s1[100] = "Hello";
    char s2[100] = "World";
    
    // 获取长度
    int len = strlen(s1);
    
    // 字符串复制
    strcpy(s1, s2);  // s1 = "World"
    
    // 字符串连接
    strcat(s1, s2);  // s1 = "WorldWorld"
    
    // 字符串比较
    int cmp = strcmp(s1, s2);
    
    // 查找子串
    char* pos = strstr(s1, "orl");
    
    // 内存操作
    memset(s1, 0, sizeof(s1));  // 清空
    memcpy(s1, s2, strlen(s2)); // 复制
}

2. C++字符串函数（需包含 `<string>`）


#include <string>
#include <algorithm>

void cpp_string_examples() {
    string s = "Hello World";
    
    // 基本操作
    int len = s.length();
    s += "!";  // 追加
    s[0] = 'h';  // 修改
    
    // 查找
    size_t pos1 = s.find("World");
    size_t pos2 = s.find_first_of("aeiou");
    
    // 子串
    string sub = s.substr(6, 5);  // "World"
    
    // 替换
    s.replace(6, 5, "OIers");
    
    // 转换C风格字符串
    const char* cs = s.c_str();
    
    // 算法库函数
    reverse(s.begin(), s.end());
    sort(s.begin(), s.end());
}

四、排序与查找函数

1. 排序函数（需包含 `<algorithm>`）


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

void sort_examples() {
    // 1. 数组排序
    int arr[] = {5, 2, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    sort(arr, arr + n);  // 升序排序
    sort(arr, arr + n, greater<int>());  // 降序排序
    
    // 2. vector排序
    vector<int> vec = {5, 2, 8, 1, 9};
    sort(vec.begin(), vec.end());
    
    // 3. 自定义排序
    struct Point {
        int x, y;
    };
    vector<Point> points = {{1, 2}, {3, 1}, {2, 3}};
    
    sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    
    // 4. 部分排序
    partial_sort(arr, arr + 3, arr + n);  // 前3个最小的
    
    // 5. 稳定排序（保持相等元素相对顺序）
    stable_sort(vec.begin(), vec.end());
}

2. 查找函数


#include <algorithm>
#include <set>
#include <map>
using namespace std;

void search_examples() {
    // 1. 二分查找（必须已排序）
    int arr[] = {1, 3, 5, 7, 9};
    int n = 5;
    
    bool found = binary_search(arr, arr + n, 5);  // true
    int* lb = lower_bound(arr, arr + n, 6);  // 第一个>=6的位置
    int* ub = upper_bound(arr, arr + n, 5);  // 第一个>5的位置
    
    // 2. STL容器查找
    set<int> s = {1, 3, 5, 7, 9};
    auto it = s.find(5);  // 返回迭代器
    
    map<string, int> m = {{"Alice", 90}, {"Bob", 85}};
    auto mit = m.find("Alice");
    
    // 3. 最大值最小值
    int max_val = *max_element(arr, arr + n);
    int min_val = *min_element(arr, arr + n);
    
    // 4. 计数
    int cnt = count(arr, arr + n, 5);
}

五、容器相关函数

1. Vector（动态数组）


#include <vector>
using namespace std;

void vector_examples() {
    vector<int> v;
    
    // 插入元素
    v.push_back(1);
    v.emplace_back(2);  // 更高效
    v.insert(v.begin() + 1, 3);
    
    // 删除元素
    v.pop_back();
    v.erase(v.begin());
    v.erase(v.begin() + 1, v.begin() + 3);
    v.clear();
    
    // 访问元素
    int first = v[0];      // 不检查边界
    int second = v.at(1);  // 检查边界
    int front = v.front();
    int back = v.back();
    
    // 容量相关
    int size = v.size();
    bool empty = v.empty();
    v.resize(10);
    v.reserve(100);  // 预分配空间
    
    // 遍历
    for (int i = 0; i < v.size(); i++) {
        // 下标访问
    }
    for (auto it = v.begin(); it != v.end(); ++it) {
        // 迭代器访问
    }
    for (int x : v) {
        // 范围for循环
    }
}

2. Set/Multiset（集合）


#include <set>
using namespace std;

void set_examples() {
    // set（不重复，有序）
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(2);
    
    // 查找
    auto it = s.find(2);
    if (it != s.end()) {
        // 找到
    }
    
    // 删除
    s.erase(2);
    s.erase(it);
    
    // 遍历（自动排序）
    for (int x : s) {
        cout << x << " ";  // 1 2 3
    }
    
    // 上下界
    auto lb = s.lower_bound(2);
    auto ub = s.upper_bound(2);
    
    // multiset（允许重复）
    multiset<int> ms;
    ms.insert(1);
    ms.insert(1);
    
    // 删除所有值为1的元素
    ms.erase(1);
    // 只删除一个
    ms.erase(ms.find(1));
}

3. Map（映射）


#include <map>
#include <unordered_map>
using namespace std;

void map_examples() {
    // map（基于红黑树，有序）
    map<string, int> m;
    
    // 插入
    m["Alice"] = 90;
    m.insert({"Bob", 85});
    m.emplace("Charlie", 92);
    
    // 访问
    int score = m["Alice"];
    // 使用at会检查key是否存在
    // int score2 = m.at("David");  // 抛出异常
    
    // 查找
    auto it = m.find("Alice");
    if (it != m.end()) {
        string name = it->first;
        int score = it->second;
    }
    
    // 删除
    m.erase("Alice");
    m.erase(it);
    
    // unordered_map（哈希表，无序但更快）
    unordered_map<string, int> um;
    um.reserve(1000);  // 预分配空间提高效率
}

4. 优先队列（堆）


#include <queue>
#include <functional>
using namespace std;

void priority_queue_examples() {
    // 默认最大堆
    priority_queue<int> pq1;
    pq1.push(3);
    pq1.push(1);
    pq1.push(2);
    // 顶部是3
    
    // 最小堆
    priority_queue<int, vector<int>, greater<int>> pq2;
    pq2.push(3);
    pq2.push(1);
    pq2.push(2);
    // 顶部是1
    
    // 自定义比较函数
    struct Node {
        int x, y;
        bool operator<(const Node& other) const {
            return x < other.x;  // 按x从大到小
        }
    };
    priority_queue<Node> pq3;
    
    // 操作
    int top = pq1.top();  // 查看顶部
    pq1.pop();            // 弹出顶部
    bool empty = pq1.empty();
    int size = pq1.size();
}

六、算法函数

1. 常用算法函数（需包含 `<algorithm>`）


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

void algorithm_examples() {
    vector<int> v = {1, 2, 3, 4, 5};
    
    // 1. 翻转
    reverse(v.begin(), v.end());  // {5, 4, 3, 2, 1}
    
    // 2. 旋转
    rotate(v.begin(), v.begin() + 2, v.end());  // 前2个移到后面
    
    // 3. 去重（必须先排序）
    sort(v.begin(), v.end());
    auto last = unique(v.begin(), v.end());
    v.erase(last, v.end());
    
    // 4. 全排列
    string s = "abc";
    do {
        cout << s << endl;
    } while (next_permutation(s.begin(), s.end()));
    
    // 5. 前缀和（C++17 partial_sum）
    vector<int> prefix(v.size());
    partial_sum(v.begin(), v.end(), prefix.begin());
    
    // 6. 相邻差
    vector<int> diff(v.size());
    adjacent_difference(v.begin(), v.end(), diff.begin());
    
    // 7. 交换
    swap(v[0], v[1]);
    
    // 8. 填充
    fill(v.begin(), v.end(), 0);
    
    // 9. 复制
    vector<int> v2(v.size());
    copy(v.begin(), v.end(), v2.begin());
    
    // 10. 查找
    auto it = find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        // 找到
    }
}

七、实用工具函数

1. 随机数生成


#include <random>
#include <ctime>
using namespace std;

void random_examples() {
    // 1. 传统方法（不推荐）
    srand(time(NULL));
    int r1 = rand() % 100;  // 0-99
    
    // 2. C++11随机数（推荐）
    random_device rd;
    mt19937 gen(rd());  // 梅森旋转算法
    
    // 均匀分布
    uniform_int_distribution<> dis_int(1, 100);
    int r2 = dis_int(gen);
    
    uniform_real_distribution<> dis_real(0.0, 1.0);
    double r3 = dis_real(gen);
    
    // 正态分布
    normal_distribution<> dis_normal(0.0, 1.0);
    double r4 = dis_normal(gen);
    
    // 洗牌算法
    vector<int> v = {1, 2, 3, 4, 5};
    shuffle(v.begin(), v.end(), gen);
}

2. 位运算函数


#include <bitset>
#include <climits>
using namespace std;

void bit_examples() {
    // 1. 内置位运算
    unsigned int x = 13;  // 1101
    
    int bit_count = __builtin_popcount(x);  // 1的个数: 3
    int leading_zeros = __builtin_clz(x);    // 前导0个数
    int trailing_zeros = __builtin_ctz(x);   // 尾随0个数
    
    // 2. bitset类
    bitset<32> bs(x);
    bs.set(0);      // 设置第0位为1
    bs.reset(1);    // 设置第1位为0
    bs.flip(2);     // 翻转第2位
    bool bit = bs.test(3);  // 测试第3位
    
    // 3. 位运算技巧
    bool is_power_of_two = (x & (x - 1)) == 0;
    int lowest_bit = x & -x;
    int clear_lowest_bit = x & (x - 1);
}

八、竞赛专用技巧

1. 快速读入/输出（整数）


#include <cstdio>

// 快速读入整数
inline int read_int() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

// 快速输出整数
inline void write_int(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write_int(x / 10);
    putchar(x % 10 + '0');
}

2. 常用宏定义


// 竞赛常用宏
#include <bits/stdc++.h>  // 万能头文件（部分OJ支持）

// 简化代码
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// 调试输出
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

// 安全操作
template<typename T>
inline T max(T a, T b, T c) {
    return max(a, max(b, c));
}

// 无穷大定义
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3fLL;

九、注意事项

效率优先：竞赛中优先使用C风格函数（scanf/printf）
内存管理：注意数组大小，避免越界

浮点数比较：使用eps避免精度问题


const double eps = 1e-9;
bool equal(double a, double b) {
    return fabs(a - b) < eps;
}

时间复杂度：理解每个函数的时间复杂度
平台差异：某些函数在不同编译器可能有差异

十、常用头文件总结


// 竞赛常用头文件组合
#include <bits/stdc++.h>  // 万能头（慎用，部分比赛禁用）

// 或者使用以下组合
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <functional>
#include <limits>
using namespace std;

信息学奥林匹克竞赛常用系统函数

一、数学函数

1. C/C++ 标准库数学函数（需包含 <cmath>）

2. 算法竞赛常用数学技巧

二、输入输出函数

1. C风格输入输出

2. C++风格输入输出

三、字符串处理函数

1. C风格字符串函数（需包含 <cstring>）

2. C++字符串函数（需包含 <string>）

四、排序与查找函数

1. 排序函数（需包含 <algorithm>）

2. 查找函数

五、容器相关函数

1. Vector（动态数组）

2. Set/Multiset（集合）

3. Map（映射）

4. 优先队列（堆）

六、算法函数

1. 常用算法函数（需包含 <algorithm>）

七、实用工具函数

1. 随机数生成

2. 位运算函数

八、竞赛专用技巧

1. 快速读入/输出（整数）

2. 常用宏定义

九、注意事项

十、常用头文件总结

1. C/C++ 标准库数学函数（需包含 `<cmath>`）

1. C风格字符串函数（需包含 `<cstring>`）

2. C++字符串函数（需包含 `<string>`）

1. 排序函数（需包含 `<algorithm>`）

1. 常用算法函数（需包含 `<algorithm>`）