算法基础入门

算法竞赛基础入门

一、基础语法

1. 数据类型（算法中最常用的）

• 整数：int（4 字节，范围约 ±2e9）、long long（8 字节，范围约 ±9e18，处理大数字必用，避免溢出）

• 浮点数：double（双精度，处理小数，注意精度误差）

• 字符：char（单个字符，如 ‘a’、’3’）

• 布尔：bool（值为true/false，判断条件用）

注意：算法题中 “大整数”（如 1e18）必须用long long，否则会溢出！

2. 变量与常量

• 变量：数据类型 变量名 = 初始值; 例：int a = 5; long long b = 1e18;

• 常量：用const定义（不可修改），例：const int N = 1e5;（定义数组大小常用）

• 数组定义与变量常量的关系：

• • 数组大小需为常量或常量表达式，如const int size = 10; int arr[size];
• • 不能用变量直接定义数组大小，如int n = 5; int arr[n];（错误），需用动态数组vector

int arr[5];
arr[5] = 10; // 错误！数组下标0-4

3. 输入输出（算法题的 “接口”）

• cin/cout（C++ 风格，简单但默认较慢）：

#include <iostream>
using namespace std;
int main() {
    int x; 
    cin >> x;  // 输入单个整数
    cout << x << " ";  // 输出单个整数

    // 数组的输入输出
    const int N = 5;
    int arr[N];
    for (int i = 0; i < N; i++) {
        cin >> arr[i];  // 输入数组元素
    }
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";  // 输出数组元素
    }
    return 0;
}

• scanf/printf（C 风格，速度快，处理大量数据必用）：

#include <cstdio>
int main() {
    int x; 
    scanf("%d", &x);  // 输入整数
    printf("%d ", x);  // 输出整数

    // 数组的输入输出
    const int N = 5;
    int arr[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);  // 输入数组元素
    }
    for (int i = 0; i < N; i++) {
        printf("%d ", arr[i]);  // 输出数组元素
    }
    return 0;
}

提示：比赛中加一句ios::sync_with_stdio(false); cin.tie(0);可以让 cin/cout 速度接近 scanf/printf（放在 main 函数开头）。

4. 运算符与表达式

• 算术运算符：+ - * / %（%是取模，例：5%2=1；注意负数取模结果为正，如-5%2=1）

• 比较运算符：> < >= <= == !=（返回 bool 值，用于条件判断）

• 逻辑运算符：&&（与）、||（或）、!（非）

5. 控制流（程序的 “逻辑”）

• 条件语句：处理分支逻辑

if (条件1) {
    // 条件1成立时执行
} else if (条件2) {
    // 条件2成立时执行
} else {
    // 都不成立时执行
}

• 循环语句：重复执行代码（算法核心，遍历 / 枚举常用）

• • for循环（最常用，遍历数组 / 范围）：

for (int i = 0; i < 10; i++) {  // i从0到9，共10次
    cout << i << " ";
}

• • while循环（条件满足时执行）：

int i = 0;
while (i < 10) {
    cout << i << " ";
    i++;
}

• • 范围 for 循环（for each）：遍历容器或数组（C++11 及以上支持）

int arr[] = {1, 2, 3, 4, 5};
for (int num : arr) {  // 遍历数组arr，num依次取数组元素值
    cout << num << " ";
}

vector<int> v = {6, 7, 8};
for (int val : v) {  // 遍历vector v
    cout << val << " ";
}

6. 数组（连续存储的同类型数据）

• 定义：数据类型 数组名[大小]; 例：int a[10];（10 个 int 元素，下标 0~9）

• 初始化：int a[5] = {1,2,3};（未初始化的元素为 0）

• 访问：a[0] = 10;（通过下标访问，下标从 0 开始！）

• 注意：数组大小必须是 “常量”（如const int N=10; int a[N];），不能用变量直接定义（动态大小用 STL 的 vector）。

7. 字符串（字符的序列）

• 用 C++ 的string类（比 C 的字符数组方便 10 倍）：

#include <string>
string s = "abc";  // 初始化
s += "d";  // 拼接：s变成"abcd"
int len = s.size();  // 长度：4
char c = s[0];  // 访问第一个字符：'a'

• 常用操作：s.empty()（是否为空）、s.substr(1,2)（从下标 1 取 2 个字符，例：”bc”）

8.函数：代码的 “模块化”

• 作用：把重复逻辑封装，避免重复写代码（如 “判断素数”“求最大值”）

• 定义格式：

返回值类型 函数名(参数类型 参数1, 参数类型 参数2) {
    // 函数体
    return 结果;  // 与返回值类型匹配
}

• 示例（求两数之和）：

int add(int a, int b) {
    return a + b;
}
int main() {
    cout << add(3,5);  // 输出8
    return 0;
}

• 重点：参数用long long时，函数定义和调用都要一致（避免类型不匹配）。

二、STL（标准模板库）

STL 是 C++ 自带的工具库，包含现成的数据结构和算法，能大幅简化代码。必须掌握以下内容：

1. 容器（存储数据的 “盒子”）

vector（动态数组，最常用！）：

#include <vector>
vector<int> v;
v.push_back(1);  // v = [1]
v.push_back(2);  // v = [1,2]
v.resize(4);  // v = [1,2,0,0]
v.clear();  // v为空

用途：存储动态长度的序列（如读入 n 个数，n 未知时）。

常用函数：

• push_back(x)：在末尾添加元素 x

• pop_back()：删除末尾元素

• size()：返回元素个数

• empty()：判断是否为空（空返回 true）

• clear()：清空所有元素

• resize(n)：调整容器大小为 n（新增元素为默认值）

• []：访问下标对应的元素（如v[0]）

queue（队列，先进先出）：

#include <queue>
queue<int> q;
q.push(1);  // q = [1]
q.push(2);  // q = [1,2]
int f = q.front();  // f=1
int b = q.back();  // b=2
q.pop();  // q = [2]

用途：BFS（广度优先搜索）必用。

常用函数：

• push(x)：入队（在队尾添加元素 x）

• pop()：出队（删除队头元素，无返回值）

• front()：返回队头元素

• back()：返回队尾元素

• size()：返回元素个数

• empty()：判断是否为空

stack（栈，先进后出）：

#include <stack>
stack<int> st;
st.push(1);  // st = [1]
st.push(2);  // st = [1,2]
int t = st.top();  // t=2
st.pop();  // st = [1]

用途：模拟栈操作、DFS 辅助。

常用函数：

• push(x)：入栈（在栈顶添加元素 x）

• pop()：出栈（删除栈顶元素，无返回值）

• top()：返回栈顶元素

• size()：返回元素个数

• empty()：判断是否为空

map/unordered_map（键值对映射）：

#include <unordered_map>
unordered_map<string, int> mp;
mp["apple"] = 5;  // 存："apple"对应5
if (mp.count("apple")) {  // 判断存在
    cout << mp["apple"];  // 取：5
}
mp.erase("apple");  // 删除键"apple"

用途：计数（如统计数字出现次数）、映射（如字符串转数字）。

常用函数：

• mp[key] = value：插入或修改键值对

• count(key)：判断 key 是否存在（存在返回 1，否则 0）

• erase(key)：删除 key 对应的键值对

• size()：返回键值对个数

• clear()：清空所有元素

set/unordered_set（集合，去重）：

#include <unordered_set>
unordered_set<int> s;
s.insert(1);
s.insert(1);  // 重复插入无效
if (s.count(1)) {  // 存在
    cout << "存在";
}
s.erase(1);  // 删除元素1

用途：去重、快速判断元素是否存在。

• 常用函数：

• insert(x)：插入元素 x（自动去重）

• count(x)：判断 x 是否存在

• erase(x)：删除元素 x

• size()：返回元素个数

• clear()：清空所有元素

2. STL 算法（现成的工具函数）

sort（排序，最常用！）：

#include <algorithm>
vector<int> v = {3,1,2};
sort(v.begin(), v.end());  // 从小到大排序：v = [1,2,3]
sort(v.begin(), v.end(), greater<int>());  // 从大到小：[3,2,1]

支持数组：int a[3] = {3,1,2}; sort(a, a+3);

其他常用：

• max(a,b)/min(a,b)：求两数最大 / 小值

• swap(a,b)：交换 a 和 b 的值

• reverse(v.begin(), v.end())：反转容器（如数组 /vector）

三、结构体

算法中常用结构体封装多个相关数据（如点的坐标、边的信息）：

struct Point {  // 定义结构体（点）
    int x, y;  // 成员：x坐标和y坐标
};
int main() {
    Point p;  // 定义结构体变量
    p.x = 1;  // 访问成员
    p.y = 2;
    vector<Point> points;  // 可以存入vector
    points.push_back(p);
    return 0;
}

用途：存储 “点、边、学生信息” 等多字段数据。

四、其他必备技巧

1. 位运算（高效处理二进制）

常用操作：

• &（与）：判断奇偶（x&1为 1 则是奇数）

• |（或）：设置位为 1

• ^（异或）：交换两数（a^=b; b^=a; a^=b;）、找唯一出现一次的数

• <<（左移）：x<<1 = x2，**x<<k = x2^k（快速计算倍数）

• >>（右移）：x>>1 = x/2（向下取整）

2. 递归（函数调用自身）

基础用法（如求阶乘）：

int factorial(int n) {
    if (n == 1) return 1;  // 终止条件（必须有，否则死循环）
    return n * factorial(n-1);  // 递归调用
}

用途：DFS（深度优先搜索）、分治算法等。

3. 输入输出优化（避免超时）

当数据量大（如 1e5 个数）：

• 用scanf/printf代替 cin/cout

• 若用 cin/cout，开头加：ios::sync_with_stdio(false); cin.tie(0);

更多详细内容可以查看：https://oi-wiki.org/lang/