函数就像一份披萨食谱：

- 输入（参数）：   食材——面粉、奶酪、番茄
- 过程（函数体）：烹饪步骤
- 输出（返回值）：做好的披萨

就像你可以用一份食谱做很多张披萨，
你可以用不同的输入多次调用一个函数。

pizza("薄底", "培根")  → 一张披萨
pizza("厚底", "蘑菇")  → 另一张披萨

#include <bits/stdc++.h>
using namespace std;

// ---- 函数定义（必须在使用前定义，或使用前置声明）----

// 接收一个整数，返回它的平方
int square(int x) {
    return x * x;
}

// 接收两个整数，返回较大的那个
int maxOf(int a, int b) {
    if (a > b) return a;
    else return b;
}

// void 函数：执行某件事但不返回值
void printSeparator() {
    cout << "====================\n";
}

// ---- 主函数 ----
int main() {
    cout << square(5) << "\n";       // 以 x=5 调用 square，打印 25
    cout << square(12) << "\n";      // 以 x=12 调用 square，打印 144

    cout << maxOf(7, 3) << "\n";     // 打印 7
    cout << maxOf(-5, -2) << "\n";   // 打印 -2

    printSeparator();                // 打印分隔线
    cout << "完成！\n";
    printSeparator();

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int square(int x);       // 原型——只有签名，没有函数体
int maxOf(int a, int b); // 原型

int main() {
    cout << square(5) << "\n";   // OK！编译器知道 square 存在
    return 0;
}

// 完整定义可以在 main 之后
int square(int x) {
    return x * x;
}

int maxOf(int a, int b) {
    return (a > b) ? a : b;
}

// void 函数执行某个动作
void printLine(int n) {
    for (int i = 0; i < n; i++) {
        cout << "-";
    }
    cout << "\n";
}

// 调用 void 函数——直接调用，不要尝试接收返回值
printLine(10);    // 打印：----------
printLine(20);    // 打印：--------------------

void addOne_byValue(int x) {
    x++;  // 修改的是局部副本——原变量不变
    cout << "函数内部：" << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byValue(n);
    cout << "函数之后：" << n << "\n";   // 还是 5！原变量未改变
    return 0;
}

void addOne_byRef(int& x) {  // & 表示「原变量的引用」
    x++;  // 直接修改原变量
    cout << "函数内部：" << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byRef(n);
    cout << "函数之后：" << n << "\n";   // 现在是 6！原变量被改变了
    return 0;
}

// 同时计算商和余数
void divmod(int a, int b, int& quotient, int& remainder) {
    quotient = a / b;
    remainder = a % b;
}

int main() {
    int q, r;
    divmod(17, 5, q, r);  // q 和 r 被函数修改
    cout << "17 / 5 = " << q << " 余 " << r << "\n";
    // 打印：17 / 5 = 3 余 2
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 声明一个有 5 个整数的数组（元素未初始化——是垃圾值！）
    int arr[5];

    // 逐一赋值
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

    // 同时声明和初始化
    int nums[5] = {1, 2, 3, 4, 5};

    // 全部初始化为零
    int zeros[100] = {};          // 所有 100 个元素 = 0
    int zeros2[100];
    fill(zeros2, zeros2 + 100, 0); // 另一种方式

    // 访问和打印
    cout << arr[2] << "\n";       // 30

    // 遍历数组
    for (int i = 0; i < 5; i++) {
        cout << nums[i] << " ";   // 1 2 3 4 5
    }
    cout << "\n";

    return 0;
}

int arr[5] = {10, 20, 30, 40, 50};

// 错误：循环从 i=0 到 i=5 包含——下标 5 不存在！
for (int i = 0; i <= 5; i++) {   // BUG：<= 5 应改为 < 5
    cout << arr[i];               // i=5 时崩溃或打印垃圾值
}

// 正确：循环从 i=0 到 i=4（i < 5 确保 i 永远到不了 5）
for (int i = 0; i < 5; i++) {    // i 的值：0, 1, 2, 3, 4 ✓
    cout << arr[i];               // 始终有效
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;  // 最大长度 + 1（常见惯例）
int arr[MAXN];              // 全局声明——大数组安全
// 全局数组会自动初始化为 0！

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    return 0;
}

int n;
cin >> n;

vector<int> arr(n);    // 马上学 vector；用法与数组相同
for (int i = 0; i < n; i++) cin >> arr[i];

// 求和
long long sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
cout << "总和：" << sum << "\n";

// 最大值（初始化为第一个元素！）
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] > maxVal) maxVal = arr[i];
}
cout << "最大值：" << maxVal << "\n";

// 最小值（同理）
int minVal = arr[0];
for (int i = 1; i < n; i++) {
    minVal = min(minVal, arr[i]);  // min() 是内置函数
}
cout << "最小值：" << minVal << "\n";

int grid[3][4];  // 3 行 4 列

// 填入 i * 10 + j
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        grid[r][c] = r * 10 + c;
    }
}

// 打印
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        cout << grid[r][c] << "\t";
    }
    cout << "\n";
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 创建空向量
    vector<int> v;

    // 用 push_back 在末尾添加元素
    v.push_back(10);    // v = [10]
    v.push_back(20);    // v = [10, 20]
    v.push_back(30);    // v = [10, 20, 30]

    // 按下标访问（与数组相同，从 0 开始）
    cout << v[0] << "\n";     // 10
    cout << v[1] << "\n";     // 20

    // 常用函数
    cout << v.size() << "\n"; // 3（元素个数）
    cout << v.front() << "\n"; // 10（第一个元素）
    cout << v.back() << "\n";  // 30（最后一个元素）
    cout << v.empty() << "\n"; // 0（false——不为空）

    // 删除最后一个元素
    v.pop_back();   // v = [10, 20]

    // 清空所有元素
    v.clear();      // v = []
    cout << v.empty() << "\n"; // 1（true——现在为空）

    return 0;
}

vector<int> v = {10, 20, 30, 40, 50};

// 方法一：下标循环（与数组相同）
for (int i = 0; i < (int)v.size(); i++) {
    cout << v[i] << " ";
}
cout << "\n";

// 方法二：范围 for 循环（更简洁，推荐）
for (int x : v) {
    cout << x << " ";
}
cout << "\n";

// 方法三：引用范围 for（需要修改时使用）
for (int& x : v) {
    x *= 2;  // 将每个元素就地翻倍
}

void fillSquares(int arr[], int n) {  // 数组参数的 arr[] 语法
    for (int i = 0; i < n; i++) {
        arr[i] = i * i;   // 修改的是原数组！
    }
}

int main() {
    int arr[5] = {0};
    fillSquares(arr, 5);
    // arr 现在是 {0, 1, 4, 9, 16}
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    return 0;
}

// 按值传递——复制整个向量（大向量时很慢）
void printVec(vector<int> v) {
    for (int x : v) cout << x << " ";
}

// 按引用传递——不复制，可修改原向量（用于输出参数）
void sortVec(vector<int>& v) {
    sort(v.begin(), v.end());
}

// 按 const 引用传递——不复制，不可修改（只读时最佳）
void printVecFast(const vector<int>& v) {
    for (int x : v) cout << x << " ";
}

思路： 把函数写在 main 之上，用输入调用它。

#include <bits/stdc++.h>
using namespace std;

int square(int x) {
    return x * x;
}

int main() {
    int n;
    cin >> n;
    cout << square(n) << "\n";
    return 0;
}

关键点：

• 函数定义在 main 之上，编译器才能识别
• return x * x;——C++ 计算 x * x 并返回结果
• 若 x 可能很大（如最大 10^9），用 long long（x² 最大 10^18）

思路： 比较 a 和 b，返回较大的那个。

#include <bits/stdc++.h>
using namespace std;

int myMax(int a, int b) {
    if (a > b) return a;
    return b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << myMax(a, b) << "\n";
    return 0;
}

关键点：

• C++ 有内置的 max(a, b) 函数——但自己写一遍有助于理解概念
• 三目运算符替代方案：return (a > b) ? a : b;

思路： 从下标 4 循环到 0（倒序）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    for (int i = 4; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• 从下标 n-1 = 4 循环到 0（包含），使用 i--
• if (i > 0) cout << " " 避免末尾多一个空格——不过对 USACO 来说末尾空格通常可以接受

思路： 创建空向量，push 5 个值，循环求和。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    long long sum = 0;
    for (int x : v) {
        sum += x;
    }

    cout << sum << "\n";
    return 0;
}

关键点：

• 范围 for for (int x : v) 遍历所有元素
• 一行替代方案：accumulate(v.begin(), v.end(), 0LL)

思路： 一个内含 for 循环的 void 函数。

#include <bits/stdc++.h>
using namespace std;

void sayHello(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Hello!\n";
    }
}

int main() {
    int n;
    cin >> n;
    sayHello(n);
    return 0;
}

关键点：

• void 表示函数不返回任何值——不需要 return 值;（可以用裸 return; 提前退出）
• sayHello 参数中的 n 是 main 中 n 的独立副本（按值传递）

思路： 存入向量，然后从最后一个下标到第一个倒序打印。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• vector<int> arr(n) 创建大小为 n 的向量（初始全为零）
• 就像数组一样读入 arr[i]
• 从 n-1 循环到 0（包含）打印

思路： 维护累计和，每次新读入后除以已读个数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        double avg = (double)sum / i;
        cout << fixed << setprecision(2) << avg << "\n";
    }

    return 0;
}

关键点：

• 每次新元素读入后更新 sum；i 是已读元素个数
• (double)sum / i——先强转为 double 再除，得到小数结果
• fixed << setprecision(2) 强制输出恰好 2 位小数

思路： 用数组（或向量）作为「计数器」——下标 1 到 10 存储对应值的计数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int freq[11] = {};  // 下标 0-10；我们用 1-10。全部初始化为 0。

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;    // 值 x 的计数加一
    }

    for (int v = 1; v <= 10; v++) {
        cout << v << " appears " << freq[v] << " times\n";
    }

    return 0;
}

关键点：

• freq[x]++ 是非常常见的模式——用值作为频率数组的下标
• 声明 freq[11]，下标 0-10，使 freq[10]（表示值 10）有效
• int freq[11] = {}——= {} 将所有元素初始化为零

思路： 检查所有满足 i < j 的对 (i, j)，若任意一对之和等于 T，打印 YES。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t;
    cin >> n >> t;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    bool found = false;
    for (int i = 0; i < n && !found; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == t) {
                found = true;
                break;
            }
        }
    }

    cout << (found ? "YES" : "NO") << "\n";

    return 0;
}

关键点：

• 内层循环从 j = i + 1 开始，避免同一元素使用两次，也避免重复检查相同的对
• break + 外层循环的 && !found 条件确保找到匹配后立即停止
• 这是 O(N²)——对 N ≤ 100 完全够用。N 最大 10^5 时，需要用集合（第 3.1 章）

为什么不对每次查询直接求和？ 暴力法：每次查询从 L 循环到 R，时间复杂度 O(N)，所有查询总计 O(N×Q)。当 N=10^5，Q=10^5 时是 10^{10} 次操作——远超时限。

优化思路： 预处理一次，O(N)；之后每次查询只需 O(1)。总计 O(N+Q)，快得多！这就是前缀和的核心思想（第 3.2 章深入讲解）。

思路： 构建前缀和数组，prefix[i] = arr[0..i-1] 的和。则 L 到 R 的和 = prefix[R+1] - prefix[L]，每次查询 O(1)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> arr(n), prefix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        prefix[i + 1] = prefix[i] + arr[i];  // 构建前缀和
    }
    // prefix[0] = 0
    // prefix[1] = arr[0]
    // prefix[2] = arr[0] + arr[1]
    // prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // l 到 r（含）的和 = prefix[r+1] - prefix[l]
        cout << prefix[r + 1] - prefix[l] << "\n";
    }

    return 0;
}

关键点：

• prefix[i] = 前 i 个元素之和（prefix[0] = 0 是哨兵）
• arr[L..R] 的和 = prefix[R+1] - prefix[L]——减去 L 之前的部分
• 用样例验证：arr=[1,2,3,4,5]，prefix=[0,1,3,6,10,15]。查询 [0,2]：prefix[3]-prefix[0]=6-0=6 ✓

复杂度分析：

• 时间：O(N + Q)——预处理 O(N) + 每次查询 O(1) × Q
• 空间：O(N)——前缀和数组占 N+1 的空间

💡 暴力 vs 优化： 暴力 O(N×Q) vs 前缀和 O(N+Q)。N=Q=10^5 时，前者需 10^{10} 次操作（超时），后者只需 2×10^5 次操作（瞬间）。

思路： 新数组在位置 i 的元素原来在位置 (i - K + N) % N。等价地，从下标 N-K 开始打印，循环回绕。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // 从下标 (n - k) % n 开始打印 n 个元素，循环回绕
    for (int i = 0; i < n; i++) {
        int idx = (n - k + i) % n;
        cout << arr[idx];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• 右旋 K 位：后 K 个元素先输出，再输出前 N-K 个
• (n - k + i) % n 将新位置 i 映射到旧位置——% n 处理回绕
• 验证：n=5，k=2。i=0: idx=(5-2+0)%5=3 → arr[3]=4。i=1: idx=4 → arr[4]=5。i=2: idx=0 → arr[0]=1。正确！

思路： 双指针——一个指向每个数组的当前位置。每步取两个当前元素中较小的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n1;
    cin >> n1;
    vector<int> a(n1);
    for (int i = 0; i < n1; i++) cin >> a[i];

    int n2;
    cin >> n2;
    vector<int> b(n2);
    for (int i = 0; i < n2; i++) cin >> b[i];

    // 双指针合并
    int i = 0, j = 0;
    vector<int> result;

    while (i < n1 && j < n2) {
        if (a[i] <= b[j]) {
            result.push_back(a[i++]);  // 取 a，i 前进
        } else {
            result.push_back(b[j++]);  // 取 b，j 前进
        }
    }
    // 某个数组可能还有剩余元素
    while (i < n1) result.push_back(a[i++]);
    while (j < n2) result.push_back(b[j++]);

    for (int idx = 0; idx < (int)result.size(); idx++) {
        cout << result[idx];
        if (idx < (int)result.size() - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• 双指针 i 和 j 同步扫描数组 a 和 b
• 始终取当前较小的元素——维持有序性
• while 循环结束后，某个数组可能还有剩余元素——直接追加

思路： 检查所有满足 i < j 的对，对每对计算距离并与半径和比较。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> pos(n), rad(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> rad[i];
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long dist = abs(pos[i] - pos[j]);
            long long sumRad = rad[i] + rad[j];
            if (dist <= sumRad) {
                count++;
            }
        }
    }

    cout << count << "\n";
    return 0;
}

关键点：

• 检查满足 i < j 的对，避免同一对计数两次
• abs(pos[i] - pos[j]) 计算位置间的绝对距离
• 使用 long long 以防位置和半径较大