#include <bits/stdc++.h>      // 「全包含」——一次性包含所有标准库
using namespace std;           // 让我们可以写 cout 而不是 std::cout

int main() {
    ios_base::sync_with_stdio(false);  // 禁用 C 和 C++ I/O 的同步（更快）
    cin.tie(NULL);                      // 解除 cin 和 cout 的绑定（输入更快）

    // 你的解题代码写在这里

    return 0;
}

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

int main() {
    // int：整数，范围：-2,147,483,648 到 +2,147,483,647（约 ±20 亿）
    int apples = 42;
    int temperature = -5;

    // long long：大整数，范围：约 ±9.2 × 10^18
    long long population = 7800000000LL;  // LL 后缀表示「这是 long long 字面量」
    long long trillion = 1000000000000LL;

    // double：小数/分数
    double pi = 3.14159265358979;
    double percentage = 99.5;

    // bool：只有 true 或 false
    bool isRaining = true;
    bool finished = false;

    // char：单个字符（以 0-255 的数字存储）
    char grade = 'A';     // 单引号表示字符
    char newline = '\n';  // 特殊字符：换行符

    // string：字符序列
    string name = "Alice";         // 双引号表示字符串
    string greeting = "Hello!";

    // 打印所有变量：
    cout << "苹果数量: " << apples << "\n";
    cout << "人口: " << population << "\n";
    cout << "圆周率: " << pi << "\n";
    cout << "在下雨: " << isRaining << "\n";  // true 打印 1，false 打印 0
    cout << "成绩: " << grade << "\n";
    cout << "姓名: " << name << "\n";

    return 0;
}

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

int main() {
    char ch = 'A';

    // char 本质上是整数——可以打印其数值
    cout << ch << "\n";        // 打印：A（字符形式）
    cout << (int)ch << "\n";   // 打印：65（ASCII 值）

    // 可以对 char 做算术！
    char next = ch + 1;       // 'A' + 1 = 66 = 'B'
    cout << next << "\n";     // 打印：B

    // 比较 char（比较 ASCII 值）
    cout << ('a' < 'z') << "\n";   // 1（真，因为 97 < 122）
    cout << ('A' < 'a') << "\n";   // 1（真，因为 65 < 97）

    return 0;
}

char upper = 'C';
char lower = upper + 32;           // 'C'(67) + 32 = 'c'(99)
cout << lower << "\n";            // 打印：c

// 更易读的写法：
char lower2 = upper - 'A' + 'a';  // 'C'-'A' = 2，'a'+2 = 'c'
cout << lower2 << "\n";           // 打印：c

// 反向：小写 → 大写
char ch = 'f';
char upper2 = ch - 'a' + 'A';    // 'f'-'a' = 5，'A'+5 = 'F'
cout << upper2 << "\n";           // 打印：F

// 使用内置函数（更推荐，可读性更好）：
cout << (char)toupper('g') << "\n";  // 打印：G
cout << (char)tolower('G') << "\n";  // 打印：g

char ch = '5';

// 判断是否为数字
if (ch >= '0' && ch <= '9') {
    cout << "是数字！\n";
}

// 判断是否为大写字母
if (ch >= 'A' && ch <= 'Z') {
    cout << "大写字母！\n";
}

// 判断是否为小写字母
if (ch >= 'a' && ch <= 'z') {
    cout << "小写字母！\n";
}

// 或使用内置函数：
// isdigit(ch), isupper(ch), islower(ch), isalpha(ch), isalnum(ch)
if (isdigit(ch)) cout << "数字！\n";
if (isalpha(ch)) cout << "字母！\n";

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

int main() {
    // 创建字符串
    string s1 = "Hello";
    string s2 = "World";
    string empty = "";           // 空字符串
    string repeated(5, 'x');     // "xxxxx"——5 个 'x'

    // 长度
    cout << s1.size() << "\n";   // 5（等同于 s1.length()）

    // 拼接
    string s3 = s1 + " " + s2;  // "Hello World"
    s1 += "!";                   // s1 变为 "Hello!"

    // 访问单个字符（从 0 开始，与数组相同）
    cout << s3[0] << "\n";      // 'H'
    cout << s3[6] << "\n";      // 'W'

    // 修改单个字符
    s3[0] = 'h';                // "hello World"

    // 比较（字典序）
    cout << ("apple" < "banana") << "\n";   // 1（真）
    cout << ("abc" == "abc") << "\n";       // 1（真）
    cout << ("abc" < "abd") << "\n";        // 1（真，逐字符比较）

    return 0;
}

string s = "USACO";

// 方法一：下标循环
for (int i = 0; i < (int)s.size(); i++) {
    cout << s[i] << " ";  // U S A C O
}
cout << "\n";

// 方法二：范围 for 循环（更简洁）
for (char ch : s) {
    cout << ch << " ";    // U S A C O
}
cout << "\n";

// 方法三：引用范围 for（可就地修改）
for (char& ch : s) {
    ch = tolower(ch);     // 将每个字符转为小写
}
cout << s << "\n";        // "usaco"

string s = "Hello, World!";

// 子串：s.substr(起始位置, 长度)
string sub = s.substr(7, 5);     // "World"（从第 7 个字符开始取 5 个）
string sub2 = s.substr(7);       // "World!"（从第 7 个到结尾）

// 查找：s.find("文本")——返回下标，找不到返回 string::npos
size_t pos = s.find("World");    // 7（注意类型是 size_t，不是 int！）
if (s.find("xyz") == string::npos) {
    cout << "未找到！\n";
}

// 追加
s.append(" Hi");                 // "Hello, World! Hi"
// 等价于：s += " Hi";

// 插入
s.insert(5, "!!");               // "Hello!!, World! Hi"

// 删除：s.erase(起始位置, 个数)
s.erase(5, 2);                   // 从第 5 位删除 2 个字符

// 替换：s.replace(起始位置, 个数, "新文本")
string msg = "I love cats";
msg.replace(7, 4, "dogs");       // "I love dogs"

// cin >> 读取一个单词（遇到空白字符停止）
string word;
cin >> word;    // 输入 "Hello World" → word = "Hello"

// getline 读取整行（包含空格）
string line;
getline(cin, line);   // 输入 "Hello World" → line = "Hello World"

// ⚠️ 注意：cin >> 之后，调用 getline 前先 cin.ignore()！
int n;
cin >> n;
cin.ignore();          // 消耗残留的 '\n'
string fullLine;
getline(cin, fullLine); // 现在可以正确读取

// 字符串 → 整数
string numStr = "42";
int num = stoi(numStr);         // stoi = "string to int" → 42
long long big = stoll("123456789012345"); // stoll = "string to long long"

// 字符串 → 浮点数
double d = stod("3.14");       // stod = "string to double" → 3.14

// 整数 → 字符串
int x = 255;
string s = to_string(x);       // "255"
string s2 = to_string(3.14);   // "3.140000"

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

int main() {
    int a = 17, b = 5;

    cout << a + b << "\n";   // 22  （加法）
    cout << a - b << "\n";   // 12  （减法）
    cout << a * b << "\n";   // 85  （乘法）
    cout << a / b << "\n";   // 3   （整数除法——截断向零！）
    cout << a % b << "\n";   // 2   （取模——整除后的余数）

    // 整数除法示例：
    // 17 ÷ 5 = 3 余 2
    // 因此：17 / 5 = 3，17 % 5 = 2

    double x = 17.0, y = 5.0;
    cout << x / y << "\n";   // 3.4（操作数是 double 时进行实数除法）

    // 复合赋值运算符：
    int n = 10;
    n += 5;    // 等同于：n = n + 5   → n 现在是 15
    n -= 3;    // 等同于：n = n - 3   → n 现在是 12
    n *= 2;    // 等同于：n = n * 2   → n 现在是 24
    n /= 4;    // 等同于：n = n / 4   → n 现在是 6
    n++;       // 等同于：n = n + 1   → n 现在是 7
    n--;       // 等同于：n = n - 1   → n 现在是 6

    cout << n << "\n";  // 6

    return 0;
}

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

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

    long long n, m;
    cin >> n >> m;  // 在同一行读取两个数

    cout << n + m << "\n";  // 和
    cout << n - m << "\n";  // 差
    cout << n * m << "\n";  // 积
    cout << n / m << "\n";  // 整数商
    cout << n % m << "\n";  // 余数

    return 0;
}

思路： 用 cout 打印三行。无需读取输入。

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

int main() {
    cout << "Hello, Alice!\n";
    cout << "My favorite number is 7.\n";
    cout << "I am learning C++.\n";
    return 0;
}

关键点：

• 每条 cout 语句以 ;\n" 结尾——\n 产生换行
• 也可以将多个 << 连在一条 cout 上
• 没有输入时不需要 cin

思路： 五条独立的 cout 语句，每条打印一个数字。

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

int main() {
    cout << 1 << "\n";
    cout << 2 << "\n";
    cout << 3 << "\n";
    cout << 4 << "\n";
    cout << 5 << "\n";
    return 0;
}

关键点：

• cout << 1 << "\n" 打印数字 1 后跟换行
• 第 2.2 章会学用循环来做这件事——但手动写对小数量完全没问题

思路： 读入变量，乘以 2，打印。

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

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

关键点：

• cin >> n 读取一个整数存入 n
• 可以直接在 cout 里做算术：n * 2 先计算，再打印
• 若 n 可能很大（最大 10^9），用 long long n，因为 n * 2 可能溢出 int

思路： 读取两个整数，相加，打印。

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

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

关键点：

• cin >> a >> b 在一条语句中读取两个值——无论它们在同一行还是不同行都有效
• 在同一行声明两个变量：int a, b; 等价于 int a; int b;

思路： 读取字符串，嵌入问候语中打印。

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

int main() {
    string name;
    cin >> name;
    cout << "Hi, " << name << "!\n";
    return 0;
}

关键点：

• string name; 声明一个存储文本的变量
• cin >> name 读取一个单词（遇到第一个空格停止）
• 注意 cout 的链式写法：字符串字面量 + 变量 + 字符串字面量

思路： 年龄乘以 365。由于年龄 × 365 不会超过 int 范围（最大约 150 岁 → 150×365 = 54750，远小于 int 上限），用 int 即可。

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

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

关键点：

• years * 365 按整数计算——这里不存在溢出风险
• 如果还要换算成小时、分钟、秒，为安全起见改用 long long

思路： 使用整数除法和取模。先除以 3600 得小时数，余数（mod 3600）再除以 60 得分钟数，最后剩余的是秒数。

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

int main() {
    long long s;
    cin >> s;

    long long hours = s / 3600;         // 每小时 3600 秒
    long long remaining = s % 3600;     // 去掉完整小时后剩余的秒数
    long long minutes = remaining / 60; // 每分钟 60 秒
    long long seconds = remaining % 60; // 去掉完整分钟后剩余的秒数

    cout << hours << " hours\n";
    cout << minutes << " minutes\n";
    cout << seconds << " seconds\n";

    return 0;
}

关键点：

• 用 long long 是因为 S 最大 10^9（int 也够，但 long long 是好习惯）
• 核心思路：s % 3600 得到去掉完整小时后的秒数，再除以 60 得分钟
• 验证：3661 → 3661/3600=1 小时，3661%3600=61，61/60=1 分钟，61%60=1 秒 ✓

思路： 面积 = L × W，周长 = 2 × (L + W)。

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

int main() {
    long long L, W;
    cin >> L >> W;

    cout << "Area: " << L * W << "\n";
    cout << "Perimeter: " << 2 * (L + W) << "\n";

    return 0;
}

关键点：

• 运算顺序：2 * (L + W)——括号确保先加 L+W，再乘以 2
• 使用 long long 以防 L、W 较大（若 L、W 最大 10^9，L*W 最大 10^18）

思路： 套用公式。需要小数输出，用 double。陷阱：9/5 整数运算结果是 1，不是 1.8！

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

int main() {
    double celsius;
    cin >> celsius;

    double fahrenheit = celsius * 9.0 / 5.0 + 32.0;

    cout << fixed << setprecision(2) << fahrenheit << "\n";

    return 0;
}

关键点：

• 用 9.0 / 5.0（或 9.0/5）而不是 9/5——后者是整数除法，结果是 1 而不是 1.8！
• fixed << setprecision(2) 强制输出恰好 2 位小数
• 验证：100°C → 100 × 9.0/5.0 + 32 = 180 + 32 = 212 ✓

思路： 每种硬币数量乘以面值，全部相加。

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

int main() {
    int quarters, dimes, nickels, pennies;
    cin >> quarters >> dimes >> nickels >> pennies;

    int total = quarters * 25 + dimes * 10 + nickels * 5 + pennies * 1;

    cout << total << "\n";

    return 0;
}

关键点：

• 每种硬币乘以面值：quarters=25，dimes=10，nickels=5，pennies=1
• 验证：3×25 + 2×10 + 1×5 + 4×1 = 75 + 20 + 5 + 4 = 104 ✓
• 若硬币数量很大，改用 long long

思路： 以 long long 读入两个数，然后两种方式各算一次乘积——一次强转为 int，一次用 long long。直观展示溢出效果。

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

int main() {
    long long a, b;
    cin >> a >> b;

    // 先转成 int 再乘，强制触发整数溢出
    int int_product = (int)a * (int)b;

    // long long 乘法——值最大 10^9 时不会溢出
    long long ll_product = a * b;

    cout << "int product: " << int_product << "\n";
    cout << "long long product: " << ll_product << "\n";

    return 0;
}

关键点：

• (int)a * (int)b——两个操作数都转成 int 再乘，乘法在 int 范围内溢出
• a * b（a、b 是 long long）——乘法在 long long 空间内进行，不溢出
• 10^9 × 3 的实际结果是 3×10^9，但 int 最大约 2.147×10^9 < 3×10^9，溢出后得到 -1294967296
• 教训： 当任意一个值可能达到约 10^5 或更大时，乘法时始终用 long long

思路： N 和 M 各自能放进 int，但 N × M = 10^18——超出 int 上限（约 2.1×10^9），勉强放进 long long（上限约 9.2×10^18）。必须用 long long。

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

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

    long long n, m;
    cin >> n >> m;

    cout << n * m << "\n";

    return 0;
}

关键点：

• 用 long long 变量读取是关键——cin >> n 可以处理最大 9.2×10^18 的值
• 若用 int 变量：int n, m; cin >> n >> m; cout << n * m;——这会静默溢出，输出错误答案
• 做 USACO 题时，始终检查约束：若 N 最大 10^9，且可能要算 N × N，就需要 long long

思路： 判断 x 和 y 的正负。x 和 y 正负的每种组合恰好对应一个象限。使用 if/else-if 链（第 2.2 章会完整讲，但这里很直接）。

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

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

    int x, y;
    cin >> x >> y;

    if (x > 0 && y > 0) {
        cout << 1 << "\n";
    } else if (x < 0 && y > 0) {
        cout << 2 << "\n";
    } else if (x < 0 && y < 0) {
        cout << 3 << "\n";
    } else {  // x > 0 && y < 0
        cout << 4 << "\n";
    }

    return 0;
}

关键点：

• && 运算符表示「且」——两个条件都必须为真
• 题目保证 x ≠ 0 且 y ≠ 0，无需处理这些边界情况
• 四种情况互斥（对任意输入恰好一种为真），else-if 链完美适用
• 可以用公式简化，但显式 if/else 更清晰，速度一样快

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

int main() {
    int score;
    cin >> score;

    if (score >= 90) {
        cout << "优秀！\n";
    }

    cout << "完成。\n";  // 无论 score 是多少都会执行
    return 0;
}

int score;
cin >> score;

if (score >= 90) {
    cout << "A\n";
} else if (score >= 80) {
    cout << "B\n";
} else if (score >= 70) {
    cout << "C\n";
} else if (score >= 60) {
    cout << "D\n";
} else {
    cout << "F\n";
}

int x, y;
cin >> x >> y;

if (x > 0 && y > 0) {
    cout << "两者都为正数\n";
}

if (x < 0 || y < 0) {
    cout << "至少有一个是负数\n";
}

bool done = false;
if (!done) {
    cout << "还在进行中……\n";
}

int x = 5;

// 危险的 BUG：
if (x = 10) {   // 这是把 10 赋值给 x，不是比较！
                 // x 变为 10，由于 10 不为零，这个条件永远为真
    cout << "x 是 10\n";  // 总是执行，即使 x 最初是 5！
}

// 正确写法：
if (x == 10) {  // 这才是比较 x 和 10
    cout << "x 是 10\n";  // 只有 x 真的等于 10 时才执行
}

int age, income;
cin >> age >> income;

if (age >= 18) {
    cout << "成年人\n";
    if (income > 50000) {
        cout << "高收入成年人\n";
    } else {
        cout << "普通收入成年人\n";
    }
} else {
    cout << "未成年人\n";
}

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

int main() {
    int i = 1;             // 1. 循环前初始化
    while (i <= 5) {       // 2. 检查条件——若为假则跳过循环
        cout << i << "\n"; // 3. 执行循环体
        i++;               // 4. 更新——非常重要！忘了这步 → 死循环
    }
    // 循环后：i = 6，条件 6 <= 5 为假，循环退出
    return 0;
}

// 从 0 数到 9（竞赛编程标准模式）
for (int i = 0; i < 10; i++) {
    cout << i << " ";
}
// 打印：0 1 2 3 4 5 6 7 8 9

// 从 1 数到 n（包含）
int n = 5;
for (int i = 1; i <= n; i++) {
    cout << i << " ";
}
// 打印：1 2 3 4 5

// 倒数
for (int i = 10; i >= 1; i--) {
    cout << i << " ";
}
// 打印：10 9 8 7 6 5 4 3 2 1

// 以 2 为步长
for (int i = 0; i <= 10; i += 2) {
    cout << i << " ";
}
// 打印：0 2 4 6 8 10

int day;
cin >> day;

switch (day) {
    case 1:
        cout << "星期一\n";
        break;   // 重要：break 退出 switch
    case 2:
        cout << "星期二\n";
        break;
    case 3:
        cout << "星期三\n";
        break;
    case 4:
        cout << "星期四\n";
        break;
    case 5:
        cout << "星期五\n";
        break;
    case 6:
    case 7:
        cout << "周末！\n";  // case 6 和 7 共用这段代码
        break;
    default:
        cout << "无效的日期\n";  // 没有 case 匹配时执行
}

bool found = false;
int target = 25;

for (int i = 0; i < 10 && !found; i++) {    // 外层循环也检查 !found
    for (int j = 0; j < 10; j++) {
        if (i * j == target) {
            cout << i << " * " << j << " = " << target << "\n";
            found = true;
            break;   // 退出内层循环；外层循环因为 !found 也会退出
        }
    }
}

int n;
cin >> n;

int maxVal, minVal;
cin >> maxVal;    // 读第一个元素
minVal = maxVal;  // 最大值和最小值都初始化为第一个元素

for (int i = 1; i < n; i++) {   // 从第二个元素开始（下标 1）
    int x;
    cin >> x;
    if (x > maxVal) maxVal = x;
    if (x < minVal) minVal = x;
}

cout << "最大值：" << maxVal << "\n";
cout << "最小值：" << minVal << "\n";

int n;
cin >> n;

int count = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {   // 条件：偶数
        count++;
    }
}
cout << "偶数个数：" << count << "\n";

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

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

    int n;
    cin >> n;

    // 我们需要存储所有值来与平均值比较
    //（第 2.3 章学数组/向量——这里先用 vector 预览）

    // 第一遍：找总和和最大值
    long long sum = 0;
    int maxMilk = 0;
    vector<int> milk(n);   // 存储所有值（第 2.3 章预览）

    for (int i = 0; i < n; i++) {
        cin >> milk[i];
        sum += milk[i];
        if (milk[i] > maxMilk) maxMilk = milk[i];
    }

    double avg = (double)sum / n;

    // 第二遍：统计高于平均值的数量
    int aboveAvg = 0;
    for (int i = 0; i < n; i++) {
        if (milk[i] > avg) aboveAvg++;
    }

    cout << "最大值：" << maxMilk << "\n";
    cout << "高于平均值：" << aboveAvg << "\n";

    return 0;
}

思路： 从 1 到 10（包含）的 for 循环。

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

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i << "\n";
    }
    return 0;
}

关键点：

• i <= 10（而不是 i < 10）因为我们要包含 10
• 也可以写 for (int i = 1; i < 11; i++)——效果相同

思路： 两种方案——步长为 2 循环，或每次循环检查是否为偶数。

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

int main() {
    // 方案一：步长为 2
    for (int i = 2; i <= 20; i += 2) {
        cout << i << "\n";
    }
    return 0;
}

关键点：

• i += 2 每次递增 2 而不是通常的 1
• 替代方案：for (int i = 1; i <= 20; i++) { if (i % 2 == 0) cout << i << "\n"; }

思路： 用三路 if/else if/else 覆盖所有情况。

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

int main() {
    int n;
    cin >> n;

    if (n > 0) {
        cout << "Positive\n";
    } else if (n < 0) {
        cout << "Negative\n";
    } else {
        cout << "Zero\n";
    }

    return 0;
}

关键点：

• 末尾的 else 精确捕获 n == 0（因为上面两个条件覆盖了 n>0 和 n<0）

思路： 从 1 循环到 10，每次打印 i*3。

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

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i * 3 << "\n";
    }
    return 0;
}

关键点：

• 替代方案：for (int i = 3; i <= 30; i += 3)——效果相同

思路： 循环读取 5 次，累加求和。

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

int main() {
    long long sum = 0;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << "\n";
    return 0;
}

关键点：

• sum 用 long long 以防整数较大
• 因为题目说「恰好 5 个整数」，循环读取恰好 5 次

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

思路： 循环 1 到 100。对每个数检查整除性——先检查同时整除的情况（被 3 和 5 整除），否则会被单独的 Fizz 或 Buzz 分支先捕获。

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

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            cout << "FizzBuzz\n";
        } else if (i % 3 == 0) {
            cout << "Fizz\n";
        } else if (i % 5 == 0) {
            cout << "Buzz\n";
        } else {
            cout << i << "\n";
        }
    }
    return 0;
}

关键点：

• 先检查 i % 3 == 0 && i % 5 == 0——如果先检查 i % 3 == 0，15 就会打印「Fizz」而永远到不了 FizzBuzz 分支
• 同时被 3 和 5 整除的数就是被 15 整除：i % 15 == 0 也有效

思路： 用读取的第一个值初始化最小值，每次看到更小的就更新。

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

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

    int n;
    cin >> n;

    int first;
    cin >> first;
    int minVal = first;  // 初始化为第一个元素

    for (int i = 1; i < n; i++) {   // 读取剩余 n-1 个元素
        int x;
        cin >> x;
        if (x < minVal) {
            minVal = x;
        }
    }

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

关键点：

• 将 minVal 初始化为读取的第一个元素（不是 0 或 INT_MAX），然后在循环中处理剩余元素
• 替代方案：用 INT_MAX 作为初始值——保证大于任何 int，第一个元素一定会更新它

思路： 维护一个计数器，满足条件（x > 0）时递增。

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

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

    int n;
    cin >> n;

    int count = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            count++;
        }
    }

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

关键点：

• count 从 0 开始，只在 x > 0 时递增
• 0 不是正数（也不是负数——它是零），所以 x > 0 正确地排除了它

思路： 嵌套循环——外层遍历行，内层打印对应数量的星号。

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

int main() {
    int n;
    cin >> n;

    for (int row = 1; row <= n; row++) {
        for (int star = 1; star <= row; star++) {
            cout << "*";
        }
        cout << "\n";
    }

    return 0;
}

关键点：

• 第 1 行 1 个星号，第 2 行 2 个，……，第 N 行 N 个
• 内层循环对每个 row 值恰好执行 row 次
• 使用 string 的替代方案：cout << string(row, '*') << "\n";——创建 row 个 * 的字符串

思路： 用取模技巧。N % 10 得到最后一位。N / 10 删除最后一位。重复直到 N 变为 0。

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

int main() {
    int n;
    cin >> n;

    int digitSum = 0;
    while (n > 0) {
        digitSum += n % 10;  // 加上最后一位
        n /= 10;             // 删除最后一位
    }

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

关键点：

• n % 10 提取个位数（如 12345 % 10 = 5）
• n /= 10 是整数除法，删除最后一位（如 12345 / 10 = 1234）
• 循环持续到 n = 0（所有数字都已提取）
• 追踪：12345 → +5 → 1234 → +4 → 123 → +3 → 12 → +2 → 1 → +1 → 0。总和 = 15 ✓

思路： 用 while 循环，不断应用规则直到到达 1，同时计数步数。

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

int main() {
    long long n;
    cin >> n;

    int steps = 0;
    cout << n;         // 打印起始数字

    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
        } else {
            n = n * 3 + 1;
        }
        cout << " " << n;  // 打印下一个数字
        steps++;
    }
    cout << "\n";
    cout << "Steps: " << steps << "\n";

    return 0;
}

关键点：

• 用 long long——即使从小数开始，序列中间值也可能很大（如 N=27 会到达 9232！）
• 考拉兹猜想称这个序列总会到达 1，但对所有 N 尚未被证明
• 循环前打印 N（作为起始值），之后每步打印新值

思路： 试除法——检查 2 到 √N 中有没有能整除 N 的数。如果没有，N 是质数。只需检查到 √N，因为若 N = a×b 且 a > √N，则 b < √N（早就找到了）。

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

int main() {
    int n;
    cin >> n;

    bool isPrime = true;

    if (n < 2) {
        isPrime = false;
    } else {
        // 检查 2 到 sqrt(n) 的因数
        for (int i = 2; (long long)i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = false;
                break;  // 找到因数，无需继续
            }
        }
    }

    cout << (isPrime ? "prime" : "composite") << "\n";
    return 0;
}

关键点：

• 用 i * i <= n 而不是 i <= sqrt(n)，避免浮点精度问题（也稍快）
• (long long)i * i 防止 i 较大时溢出（如 i = 1000000，i*i = 10^12）
• break 找到任意因数后立即退出——无需继续检查
• 时间复杂度：O(√N)，处理 N 最大 10^6 非常轻松（√10^6 = 1000 次迭代）

思路： 跟踪目前见过的最佳评分和名字，只在严格更高时更新。

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

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

    int n;
    cin >> n;

    string bestName;
    int bestRating = -1;  // 初始化为 -1，任何真实评分都高于它

    for (int i = 0; i < n; i++) {
        string name;
        int rating;
        cin >> name >> rating;

        if (rating > bestRating) {
            bestRating = rating;
            bestName = name;
        }
    }

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

关键点：

• 初始化 bestRating = -1（或 INT_MIN），让第一头奶牛始终成为新的最佳
• 用 >（严格大于）而非 >=，这样并列时保留最先出现的（题目要求）
• cin >> name >> rating 从同一行读取字符串和整数——完全有效

函数就像一份披萨食谱：

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

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

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 以防位置和半径较大

想象你要去旅行。你可以把每件东西分别拿着：
  - 左手：护照
  - 右手：手机
  - 口袋：钱包
  - 嘴里：机票 😬

或者，把所有东西放进一个背包：
  - backpack.passport ✅
  - backpack.phone ✅
  - backpack.wallet ✅
  - backpack.ticket ✅

struct/class 就是那个背包——把相关的东西组合在一个名字下。

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

struct Point {
    int x;
    int y;
};  // <-- 别忘了分号！

int main() {
    Point p;       // 声明一个 Point 变量
    p.x = 3;       // 用点号（.）访问成员
    p.y = 7;
    cout << "(" << p.x << ", " << p.y << ")" << endl;  // (3, 7)
    return 0;
}

struct Point {
    int x, y;

    // 构造函数
    Point(int _x, int _y) : x(_x), y(_y) {}
};

int main() {
    Point p(3, 7);  // 调用构造函数
    cout << p.x << " " << p.y << endl;  // 3 7
}

struct Edge {
    int from, to, weight;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }
}

struct Event {
    int start, end;

    // 按结束时间排序（贪心调度）
    bool operator<(const Event& other) const {
        return end < other.end;
    }
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}};
    sort(events.begin(), events.end());  // 自动使用 operator<

    for (auto& e : events) {
        cout << "[" << e.start << ", " << e.end << "] ";
    }
}

struct Event {
    int start, end;
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}};

    // 按开始时间排序
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.start < b.start;
    });
}

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};

set<Point> visited;
visited.insert({1, 2});
visited.insert({3, 4});

if (visited.count({1, 2})) {
    cout << "已访问过！" << endl;
}

struct State {
    int dist, node;

    // 最小堆：希望 dist 最小的在顶部
    // priority_queue 默认是最大堆，所以反转比较
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

// 用 operator> 实现最小堆
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, 1});   // 距离 0，节点 1
pq.push({5, 2});   // 距离 5，节点 2

auto top = pq.top();  // {0, 1}——距离最小

class BankAccount {
private:    // 只能在类内部访问
    double balance;

public:     // 可以从任何地方访问
    BankAccount(double initial) : balance(initial) {}

    void deposit(double amount) {
        if (amount > 0) {
            balance += amount;
        }
    }

    void withdraw(double amount) {
        if (amount > 0 && amount <= balance) {
            balance -= amount;
        }
    }

    double getBalance() const {
        return balance;
    }
};

int main() {
    BankAccount acc(100.0);
    acc.deposit(50.0);
    acc.withdraw(30.0);
    cout << acc.getBalance() << endl;  // 120.0

    // acc.balance = 999999;  // 错误！balance 是私有的
}

struct Rect {
    int width, height;

    int area() const {
        return width * height;
    }

    int perimeter() const {
        return 2 * (width + height);
    }

    bool contains(int x, int y) const {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
};

int main() {
    Rect r = {10, 5};
    cout << "面积：" << r.area() << endl;      // 50
    cout << "周长：" << r.perimeter() << endl;  // 30
    cout << r.contains(3, 4) << endl;            // 1（true）
}

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

int main() {
    pair<int, int> p = {3, 7};
    cout << p.first << " " << p.second << endl;  // 3 7

    // pair 有内置比较（字典序）
    vector<pair<int, int>> v = {{3, 1}, {1, 5}, {3, 0}, {1, 2}};
    sort(v.begin(), v.end());
    // 结果：{1, 2}, {1, 5}, {3, 0}, {3, 1}

    // 可以用 make_pair 或直接用花括号
    auto q = make_pair(10, 20);
}

struct Graph {
    int n;
    vector<vector<int>> adj;

    Graph(int _n) : n(_n), adj(_n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);

    for (int v : g.adj[1]) {
        cout << v << " ";  // 0 2
    }
}

// 方案 A：反转 operator<
bool operator<(const State& other) const {
    return dist > other.dist;  // dist 更大的优先级更低 → 最小堆
}
priority_queue<State> pq;

// 方案 B：定义 operator> 并使用 greater<>
bool operator>(const State& other) const {
    return dist > other.dist;
}
priority_queue<State, vector<State>, greater<State>> pq;

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

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;
        return name < other.name;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Student> students(n);
    for (int i = 0; i < n; i++) {
        cin >> students[i].name >> students[i].score;
    }
    sort(students.begin(), students.end());
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ". " << students[i].name << " " << students[i].score << "\n";
    }
}

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

struct PointVal {
    int val, originalIndex;

    bool operator<(const PointVal& other) const {
        return val < other.val;
    }
};

int main() {
    int n;
    cin >> n;
    vector<PointVal> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].val;
        points[i].originalIndex = i;
    }
    sort(points.begin(), points.end());

    int minDist = INT_MAX;
    int bestI = 0, bestJ = 1;
    for (int i = 0; i + 1 < n; i++) {
        int d = points[i + 1].val - points[i].val;
        if (d < minDist) {
            minDist = d;
            bestI = i;
            bestJ = i + 1;
        }
    }
    cout << minDist << "\n";
    cout << "（点 " << points[bestI].val << " 和点 " << points[bestJ].val << " 之间）\n";
}

输入：
6
1 4
3 5
0 6
5 7
3 8
5 9

输出：
3

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

struct Interval {
    int start, end;

    bool operator<(const Interval& other) const {
        return end < other.end;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Interval> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].start >> intervals[i].end;
    }
    sort(intervals.begin(), intervals.end());

    int count = 0, lastEnd = -1;
    for (auto& it : intervals) {
        if (it.start >= lastEnd) {
            count++;
            lastEnd = it.end;
        }
    }
    cout << count << "\n";
}

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

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;  // 区间 [a,b] 和 [c,d]

    // 如果输入不保证左端点 <= 右端点，可以先修正
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);

    if (b < c || d < a) {
        cout << "完全不相交\n";
    } else if (b == c || d == a) {
        cout << "仅端点相接\n";
    } else if (a <= c && d <= b) {
        cout << "[c,d] 在 [a,b] 内部（或相等）\n";
    } else if (c <= a && b <= d) {
        cout << "[a,b] 在 [c,d] 内部（或相等）\n";
    } else {
        cout << "部分重叠\n";
    }
    return 0;
}

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

int main() {
    // 方向编码：0=N, 1=E, 2=S, 3=W
    // dx/dy 对应四个方向的位移
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    
    int x = 0, y = 0, dir = 0;  // 初始位置和方向
    int n; cin >> n;
    
    while (n--) {
        string cmd; cin >> cmd;
        if (cmd == "left") {
            dir = (dir + 3) % 4;   // 左转 = (dir-1+4)%4
        } else if (cmd == "right") {
            dir = (dir + 1) % 4;   // 右转
        } else {
            int d; cin >> d;
            x += dx[dir] * d;
            y += dy[dir] * d;
        }
    }
    
    cout << x << " " << y << "\n";
    return 0;
}

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

const int MAX_COORD = 1000;                 // 坐标范围假设为 0~1000
int diff[MAX_COORD + 2][MAX_COORD + 2];     // 多开空间，方便处理 x2/y2

// 给矩形 [x1,x2) × [y1,y2) 覆盖区域 +1
void add_rect(int x1, int y1, int x2, int y2) {
    diff[y1][x1]++;
    diff[y1][x2]--;
    diff[y2][x1]--;
    diff[y2][x2]++;
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        add_rect(x1, y1, x2, y2);
    }

    // 二维前缀和还原每个格子的覆盖次数
    for (int y = 0; y <= MAX_COORD; y++) {
        for (int x = 0; x <= MAX_COORD; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];
        }
    }

    // 统计被至少一个矩形覆盖的 1×1 格子
    // 左下角最大只能到 (999,999)，因为格子 [999,1000) 才是最后一格
    long long covered = 0;
    for (int y = 0; y < MAX_COORD; y++) {
        for (int x = 0; x < MAX_COORD; x++) {
            if (diff[y][x] > 0) covered++;
        }
    }

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

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

int main() {
    long long ax1, ay1, ax2, ay2;
    long long bx1, by1, bx2, by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;

    long long ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) {
        cout << 0 << "\n";
    } else {
        cout << (ix2 - ix1) * (iy2 - iy1) << "\n";
    }

    return 0;
}

思路： 用差分数组标记每个 1×1 格子被覆盖的次数，最后统计覆盖次数 >= 1 的格子数。

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

int diff[1002][1002];

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 给矩形 [x1,x2) × [y1,y2) 加 1
        diff[y1][x1]++;
        diff[y1][x2]--;
        diff[y2][x1]--;
        diff[y2][x2]++;
    }

    long long ans = 0;
    for (int y = 0; y <= 1000; y++) {
        for (int x = 0; x <= 1000; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];

            // 只统计左下角为 (x,y) 的 1×1 格子，最大到 (999,999)
            if (x < 1000 && y < 1000 && diff[y][x] > 0) ans++;
        }
    }

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

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

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int n;
    cin >> n;

    while (n--) {
        long long px, py;
        cin >> px >> py;

        bool on_vertical_edge = (px == x1 || px == x2) && (y1 <= py && py <= y2);
        bool on_horizontal_edge = (py == y1 || py == y2) && (x1 <= px && px <= x2);
        bool on_edge = on_vertical_edge || on_horizontal_edge;

        bool inside = x1 < px && px < x2 && y1 < py && py < y2;

        if (on_edge) cout << "边界\n";
        else if (inside) cout << "内部\n";
        else cout << "外部\n";
    }

    return 0;
}

核心思路： 分类讨论 + 容斥。总面积 = 广告牌1面积 + 广告牌2面积 - 广告牌1被卡车遮挡面积 - 广告牌2被卡车遮挡面积。每块广告牌与卡车的遮挡面积用矩形交集公式计算。

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

// 计算两个矩形的交集面积
ll inter_area(ll ax1, ll ay1, ll ax2, ll ay2,
              ll bx1, ll by1, ll bx2, ll by2) {
    ll ix1 = max(ax1, bx1), iy1 = max(ay1, by1);
    ll ix2 = min(ax2, bx2), iy2 = min(ay2, by2);
    if (ix2 <= ix1 || iy2 <= iy1) return 0;
    return (ix2 - ix1) * (iy2 - iy1);
}

int main() {
    ll a1x1, a1y1, a1x2, a1y2;  // 广告牌1
    ll a2x1, a2y1, a2x2, a2y2;  // 广告牌2
    ll tx1, ty1, tx2, ty2;       // 卡车
    cin >> a1x1 >> a1y1 >> a1x2 >> a1y2;
    cin >> a2x1 >> a2y1 >> a2x2 >> a2y2;
    cin >> tx1 >> ty1 >> tx2 >> ty2;

    ll area1 = (a1x2 - a1x1) * (a1y2 - a1y1);
    ll area2 = (a2x2 - a2x1) * (a2y2 - a2y1);
    ll covered1 = inter_area(a1x1, a1y1, a1x2, a1y2, tx1, ty1, tx2, ty2);
    ll covered2 = inter_area(a2x1, a2y1, a2x2, a2y2, tx1, ty1, tx2, ty2);

    cout << area1 + area2 - covered1 - covered2 << "\n";
    return 0;
}

复杂度分析： 时间 O(1)，空间 O(1)。只需计算几个矩形的面积和交集，常数时间完成。

// ===== 单个位的操作（第 k 位，从 0 开始计数）=====

// 检查第 k 位是否为 1
bool check(int x, int k) { return (x >> k) & 1; }

// 将第 k 位设为 1（置位）
int set_bit(int x, int k) { return x | (1 << k); }

// 将第 k 位设为 0（清位）
int clear_bit(int x, int k) { return x & ~(1 << k); }

// 翻转第 k 位（0→1，1→0）
int flip_bit(int x, int k) { return x ^ (1 << k); }


// ===== 常用技巧 =====

// 判断 x 是否为 2 的幂（且 x > 0）
bool is_power_of_two(int x) { return x > 0 && (x & (x - 1)) == 0; }

// 获取最低有效位（lowbit，树状数组核心）
int lowbit(int x) { return x & (-x); }

// 清除最低有效位
int clear_lowest(int x) { return x & (x - 1); }

// 统计 x 中 1 的个数（popcount）
int count_ones(int x) { return __builtin_popcount(x); }     // 内置函数
// 或手动：
int count_ones_manual(int x) {
    int cnt = 0;
    while (x) { x &= x - 1; cnt++; }  // 每次清除最低位的1
    return cnt;
}

// 集合 {0, 2, 4} 表示为：
// 二进制：10101 = 21

int S = 0;           // 空集
S = set_bit(S, 0);   // 加入元素 0：S = 00001 = 1
S = set_bit(S, 2);   // 加入元素 2：S = 00101 = 5
S = set_bit(S, 4);   // 加入元素 4：S = 10101 = 21

// 检查元素 2 是否在集合中
bool has2 = check(S, 2);  // true

// 删除元素 2
S = clear_bit(S, 2);      // S = 10001 = 17

// 集合大小
int size = __builtin_popcount(S);  // 2

// 枚举 n 个元素的所有子集
void enumerate_subsets(int n) {
    for (int s = 0; s < (1 << n); s++) {
        cout << "子集 " << s << "（二进制 " << bitset<4>(s) << "）：{";
        for (int i = 0; i < n; i++) {
            if (check(s, i)) cout << i << " ";
        }
        cout << "}\n";
    }
}
// enumerate_subsets(3) 输出 2^3 = 8 个子集

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if (check(s, i)) sum += a[i];
        if (sum == target) ans++;
    }
    
    cout << ans << "\n";
}
// 复杂度：O(2^N × N)，N=20 时约 2×10^7，可以通过

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

int n;
int dist[20][20];
int dp[1 << 20][20];  // dp[mask][v] = 访问了 mask 中的城市，当前在 v，的最短距离

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];
    
    // 初始化
    for (auto& row : dp) fill(row, row + n, INT_MAX / 2);
    dp[1][0] = 0;  // 从城市 0 出发，mask=1（只访问了0）
    
    // 枚举所有状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INT_MAX / 2) continue;
            if (!check(mask, u)) continue;
            
            // 尝试移动到下一个未访问的城市 v
            for (int v = 0; v < n; v++) {
                if (check(mask, v)) continue;  // 已访问
                int new_mask = set_bit(mask, v);
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // 所有城市都访问后（mask = (1<<n)-1），回到城市 0
    int ans = INT_MAX;
    int full = (1 << n) - 1;
    for (int u = 1; u < n; u++)
        ans = min(ans, dp[full][u] + dist[u][0]);
    
    cout << ans << "\n";
    // 复杂度：O(2^N × N^2)，N=20 时约 4×10^8（偏大，N=15~18 通常可行）
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x; cin >> x;
    cout << __builtin_popcount(x) << "\n";
    cout << (x > 0 && (x & (x-1)) == 0 ? "是2的幂" : "不是2的幂") << "\n";
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, m; cin >> x >> m;
    while (m--) {
        int k; cin >> k;
        x ^= (1 << k);  // XOR 翻转第 k 位
    }
    cout << x << "\n";
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int cnt = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) sum += a[i];
        if (sum % 2 == 0) cnt++;
    }
    cout << cnt << "\n";
    // 答案总是 2^(n-1)（如果有奇数）
}

思路： 枚举所有非空子集，对每个子集计算异或和取最大。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 1; s < (1 << n); s++) {
        int xor_sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) xor_sum ^= a[i];
        ans = max(ans, xor_sum);
    }
    cout << ans << "\n";
}

进阶（N 较大时）： 用线性基（高斯消元）在 O(N × 30) 内找最大异或值。

核心思路： 对每头奶牛 i，用一个 N 位整数 before[i] 记录「在某一轮中，哪些奶牛排在 i 前面」。遍历每轮排名，对奶牛 i，排在 i 前面的所有奶牛 j 的第 j 位置 1。K 轮结束后，before[i] 逐位 AND 所有轮的结果——某位保持 1 说明那头奶牛在所有轮中都排在 i 前面。统计所有 before[i] 的 popcount 之和。

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int K, N;
    cin >> K >> N;

    // before[i] 的第 j 位 = 奶牛 j 在所有已完成轮次中是否始终排在 i 前面
    vector<int> before(N, (1 << N) - 1);  // 初始全1，逐轮 AND

    for (int round = 0; round < K; round++) {
        // 读取排名：rank[0]=第1名的奶牛编号...
        vector<int> ranking(N);
        for (int p = 0; p < N; p++) cin >> ranking[p];

        // mask 记录当前已出现的奶牛（排在前面）
        int mask = 0;
        for (int p = 0; p < N; p++) {
            int cow = ranking[p] - 1;  // 转 0-indexed
            before[cow] &= mask;       // AND 上当前排在前面的奶牛集合
            mask |= (1 << cow);        // 将当前奶牛加入已出现集合
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++)
        ans += __builtin_popcount(before[i]);
    cout << ans << "\n";
}

复杂度分析： 时间 O(K × N)，空间 O(N)。每位用一个 int 做 K 次 AND 操作，非常高效。

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

int main() {
    // 对向量排序——升序（默认）
    vector<int> v = {5, 2, 8, 1, 9, 3};
    sort(v.begin(), v.end());
    // v 现在是：{1, 2, 3, 5, 8, 9}

    for (int x : v) cout << x << " ";
    cout << "\n";

    // 降序排序
    sort(v.begin(), v.end(), greater<int>());
    // v 现在是：{9, 8, 5, 3, 2, 1}

    // 对数组排序
    int arr[] = {4, 2, 7, 1, 5};
    int n = 5;
    sort(arr, arr + n);  // 排序 arr[0..n-1]
    // arr 现在是：{1, 2, 4, 5, 7}

    return 0;
}

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

int main() {
    // 创建 pair
    pair<int, int> point = {3, 5};         // (x, y)
    pair<string, int> student = {"Alice", 95};  // (姓名, 成绩)

    // 访问元素：.first 和 .second
    cout << point.first << " " << point.second << "\n";    // 3 5
    cout << student.first << ": " << student.second << "\n"; // Alice: 95

    // pair 支持比较：先比较 .first，相同时比较 .second
    pair<int,int> a = {1, 3};
    pair<int,int> b = {1, 5};
    cout << (a < b) << "\n";   // 1（真）—— .first 相同，比较 .second：3 < 5

    // 非常常见的模式：用 pair 按第二元素排序
    vector<pair<int,int>> v = {{3,9},{1,2},{4,1},{1,5}};
    sort(v.begin(), v.end());     // 先按 .first 排序，再按 .second 排序
    // 结果：{1,2}, {1,5}, {3,9}, {4,1}

    return 0;
}

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

int main() {
    map<string, int> phoneBook;

    // 插入键值对
    phoneBook["Alice"] = 555001;
    phoneBook["Bob"] = 555002;
    phoneBook["Charlie"] = 555003;

    // 按键查找
    cout << phoneBook["Alice"] << "\n";  // 555001

    // 遍历（始终按键的**排序顺序**！）
    for (auto& entry : phoneBook) {
        cout << entry.first << " -> " << entry.second << "\n";
    }
    // 打印：
    // Alice -> 555001
    // Bob -> 555002
    // Charlie -> 555003

    // 删除键
    phoneBook.erase("Charlie");
    cout << phoneBook.size() << "\n";  // 2

    return 0;
}

map<string, int> freq;

// 危险：访问不存在的键会以值 0 创建它！
cout << freq["apple"] << "\n";  // 打印 0，但现在 "apple" 已经在 map 里了！
cout << freq.size() << "\n";    // 1——即使我们只是「查了一下」，并没有「插入」！

// 安全方式一：先检查 count
if (freq.count("apple") > 0) {
    cout << freq["apple"] << "\n";  // 安全——键已存在
}

// 安全方式二：用 .find()
auto it = freq.find("apple");
if (it != freq.end()) {          // .end() 表示「未找到」
    cout << it->second << "\n";  // it->second 是值
}

vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
map<string, int> freq;

for (const string& w : words) {
    freq[w]++;  // 如果 "w" 不存在，以 0 创建，然后递增为 1
}

// freq: apple→3, banana→2, cherry→1
for (auto& p : freq) {
    cout << p.first << " 出现了 " << p.second << " 次\n";
}

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

int main() {
    set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2);   // 重复——被忽略！set 仍是 {2, 5, 8}
    s.insert(1);

    // s 现在是：{1, 2, 5, 8}（自动排序，无重复）

    // 检查成员资格
    cout << s.count(2) << "\n";   // 1（存在）
    cout << s.count(7) << "\n";   // 0（不存在）

    // 删除
    s.erase(2);   // s = {1, 5, 8}

    // 遍历（始终排序）
    for (int x : s) cout << x << " ";
    cout << "\n";   // 1 5 8

    // 最小值和最大值
    cout << *s.begin() << "\n";   // 1（最小；* 解引用迭代器）
    cout << *s.rbegin() << "\n";  // 8（最大；r = 反向）

    cout << s.size() << "\n";  // 3

    return 0;
}

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

int main() {
    stack<int> st;

    st.push(1);    // [1]         （顶部在右侧）
    st.push(2);    // [1, 2]
    st.push(3);    // [1, 2, 3]

    cout << st.top() << "\n";   // 3（查看顶部，不移除）
    st.pop();                    // 移除顶部 → [1, 2]
    cout << st.top() << "\n";   // 2

    cout << st.size() << "\n";  // 2
    cout << st.empty() << "\n"; // 0（不为空）

    return 0;
}

string expr = "((a+b)*(c-d))";
stack<char> parens;
bool balanced = true;

for (char ch : expr) {
    if (ch == '(') {
        parens.push(ch);         // 开括号：压栈
    } else if (ch == ')') {
        if (parens.empty()) {    // 闭括号但没有对应的开括号
            balanced = false;
            break;
        }
        parens.pop();            // 找到匹配：弹出开括号
    }
}

if (!parens.empty()) balanced = false;  // 还有未匹配的开括号

cout << (balanced ? "匹配" : "不匹配") << "\n";

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

int main() {
    queue<int> q;

    q.push(10);   // [10]
    q.push(20);   // [10, 20]
    q.push(30);   // [10, 20, 30]

    cout << q.front() << "\n";  // 10（排在最前——最先离开）
    cout << q.back() << "\n";   // 30（排在最后——最后离开）

    q.pop();                     // 从前面移除 → [20, 30]
    cout << q.front() << "\n";  // 20

    cout << q.size() << "\n";   // 2

    return 0;
}

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

int main() {
    // 最大堆：始终给你最大值
    priority_queue<int> maxPQ;

    maxPQ.push(5);
    maxPQ.push(1);
    maxPQ.push(8);
    maxPQ.push(3);

    // 按降序弹出
    while (!maxPQ.empty()) {
        cout << maxPQ.top() << " ";  // 始终是当前最大值
        maxPQ.pop();
    }
    cout << "\n";  // 打印：8 5 3 1

    return 0;
}

// 最大堆（默认）——优先给最大值
priority_queue<int> maxPQ;

// 最小堆——优先给最小值（注意额外的模板参数！）
priority_queue<int, vector<int>, greater<int>> minPQ;

minPQ.push(5);
minPQ.push(1);
minPQ.push(8);
minPQ.push(3);

while (!minPQ.empty()) {
    cout << minPQ.top() << " ";
    minPQ.pop();
}
// 打印：1 3 5 8（最小值优先）

unordered_map<string, int> freq;
freq["apple"]++;
freq["banana"]++;
freq["apple"]++;

cout << freq["apple"] << "\n";   // 2（与 map 接口相同）

unordered_set<int> seen;
seen.insert(5);
seen.insert(10);
cout << seen.count(5) << "\n";   // 1（找到）
cout << seen.count(7) << "\n";   // 0（未找到）

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

// 只读遍历（复制每个元素——对 int 没问题，对 string 浪费）
for (int x : nums) {
    cout << x << " ";
}

// 引用：不复制，可修改元素
for (int& x : nums) {
    x *= 2;   // 就地翻倍每个元素
}

// const 引用：不复制，只读（大类型的最佳方式）
for (const auto& x : nums) {
    cout << x << " ";
}

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // 升序排序
    sort(v.begin(), v.end());
    // v = {1, 1, 2, 3, 4, 5, 6, 9}

    // 二分查找（只能用于**已排序**的序列！）
    cout << binary_search(v.begin(), v.end(), 5) << "\n";  // 1（找到）
    cout << binary_search(v.begin(), v.end(), 7) << "\n";  // 0（未找到）

    // lower_bound：第一个 >= 目标值的位置
    auto it = lower_bound(v.begin(), v.end(), 4);
    cout << *it << "\n";   // 4
    cout << (it - v.begin()) << "\n";  // 下标：3

    // upper_bound：第一个 > 目标值的位置
    auto it2 = upper_bound(v.begin(), v.end(), 4);
    cout << (it2 - v.begin()) << "\n";  // 下标：4（第一个 > 4 的元素）
    // [lo, hi] 范围内的元素个数：upper_bound(hi+1) - lower_bound(lo)

    // 最小值和最大值
    cout << *min_element(v.begin(), v.end()) << "\n";  // 1
    cout << *max_element(v.begin(), v.end()) << "\n";  // 9

    // 所有元素之和
    long long total = accumulate(v.begin(), v.end(), 0LL);
    cout << total << "\n";  // 31

    // 统计出现次数
    cout << count(v.begin(), v.end(), 1) << "\n";  // 2

    // 反转
    reverse(v.begin(), v.end());

    // 用一个值填充
    fill(v.begin(), v.end(), 0);  // 全为零

    return 0;
}

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

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

    int n;
    cin >> n;

    // 第一步：用 map 统计词频
    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        freq[word]++;   // 如果 word 是新的，以 0 创建，然后递增
    }

    // 第二步：按字母顺序打印所有单词（map 按键有序迭代）
    cout << "所有单词：\n";
    for (auto& entry : freq) {
        // entry.first = 单词，entry.second = 计数
        cout << entry.first << ": " << entry.second << "\n";
    }

    // 第三步：找最频繁的单词
    // 对 map 用 max_element：按值（.second）比较
    auto best = max_element(
        freq.begin(),
        freq.end(),
        [](const pair<string,int>& a, const pair<string,int>& b) {
            return a.second < b.second;  // 按计数比较
        }
    );

    cout << "\n最频繁的：\"" << best->first << "\"（出现了 "
         << best->second << " 次）\n";

    return 0;
}

思路： 把 N 个整数存入集合，对每个查询检查 s.count(x)。

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

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

    int n;
    cin >> n;

    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (s.count(x) ? "YES" : "NO") << "\n";
    }

    return 0;
}

关键点：

• s.count(x) 找到时返回 1，未找到时返回 0
• while (q--) 是常见惯用法：循环执行 q 次（每次 q 递减）
• 使用 set 每次查询 O(log N)，比线性搜索 O(N) 快得多

思路： 用 map<char, int> 统计字符频率，遍历 map 自动按字母顺序输出。

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

int main() {
    string s;
    cin >> s;

    map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    for (auto& entry : freq) {
        cout << entry.first << ": " << entry.second << "\n";
    }

    return 0;
}

关键点：

• for (char c : s) 遍历字符串中的每个字符
• freq[c]++ 第一次访问时以值 0 创建条目，然后递增
• map 遍历始终按键有序——字符自动按字母顺序输出

思路： 把每个字符压栈，然后全部弹出——LIFO 顺序正好是倒序。

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    for (char c : s) {
        st.push(c);
    }

    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }
    cout << "\n";

    return 0;
}

关键点：

• 栈的 LIFO 特性：最后压入的最先弹出 = 反转
• 访问 st.top() 或调用 st.pop() 前始终检查 !st.empty()
• 注意：reverse(s.begin(), s.end()); cout << s; 更简单——但用栈实现能理解概念

思路： 把所有名字加入队列，然后逐一弹出并打印直到队列为空。

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

int main() {
    queue<string> line;
    line.push("Alice");
    line.push("Bob");
    line.push("Charlie");
    line.push("Dave");
    line.push("Eve");

    while (!line.empty()) {
        cout << "Serving: " << line.front() << "\n";
        line.pop();
    }

    return 0;
}

关键点：

• queue.front() 不移除地访问第一个元素
• queue.pop() 移除队首元素（无返回值——如需值，在 pop() 前用 front()）
• 队列保持插入顺序——先压入的先弹出

思路： 全部压入最大堆优先队列，弹出 3 次得到最大的 3 个。

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

int main() {
    int n;
    cin >> n;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < 3 && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

关键点：

• priority_queue<int> 是最大堆——top() 始终给出最大值
• 弹出 3 次按顺序得到最大的 3 个值
• && !pq.empty() 防卫处理 N < 3 的边界情况

思路： 用 unordered_set 追踪已见过的值。对每个元素，只有还没见过时才打印。

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

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

    int n;
    cin >> n;

    unordered_set<int> seen;
    bool first = true;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (seen.count(x) == 0) {   // 还没见过 x
            seen.insert(x);
            if (!first) cout << " ";
            cout << x;
            first = false;
        }
    }
    cout << "\n";

    return 0;
}

关键点：

• 不能用普通 set，因为 set 会排序输出——我们要保持原始顺序
• unordered_set 提供 O(1) 均摊查找：比搜索向量快得多
• first 标志处理间隔（不打印前导/尾随空格）

思路： 用 map 统计计数，然后找最大计数。在所有出现该最大计数的单词中，取字典序最小的（map 遍历自然给出）。

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

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

    int n;
    cin >> n;

    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        freq[w]++;
    }

    string bestWord;
    int bestCount = 0;

    // map 按字母顺序迭代——最先见到的达到最大计数的单词胜出
    for (auto& entry : freq) {
        if (entry.second > bestCount) {
            bestCount = entry.second;
            bestWord = entry.first;
        }
    }

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

关键点：

• 用 >（严格大于）意味着我们保留第一个达到最大计数的单词
• 由于 map 按字母顺序迭代，第一个见到的最大计数单词就是字典序最小的
• 得益于 map 的有序特性，平局处理自动完成

思路： 对每个元素 x，检查 T - x 是否已在已见元素的集合中。如果是，找到了一对。

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

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

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

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

    for (int i = 0; i < n; i++) {
        int complement = t - arr[i];  // 需要 arr[i] + complement = t
        if (seen.count(complement)) {
            // complement 在 arr[i] 之前，按顺序打印：complement arr[i]
            cout << complement << " " << arr[i] << "\n";
        }
        seen.insert(arr[i]);
    }

    return 0;
}

关键点：

• 对每个元素 x，需要的「补数」是 T - x
• 如果补数已在「已见」集合中，它在数组前面出现 → 有效的对
• 这是用 set 的 O(N log N)（或用 unordered_set 的 O(N)），优于暴力 O(N²)
• 先打印 complement（它在输入中较早），再打印 arr[i]

思路： 用栈。压入开括号；见到闭括号时，检查栈顶是否是对应的开括号。

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    bool ok = true;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);    // 开括号：压栈
        } else {
            // 闭括号
            if (st.empty()) {
                ok = false;  // 没有对应的开括号
                break;
            }
            char top = st.top();
            st.pop();

            // 检查是否匹配
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                ok = false;
                break;
            }
        }
    }

    if (!st.empty()) ok = false;  // 还有未匹配的开括号

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

关键点：

• 核心思路：最近打开的括号必须是下一个关闭的
• 栈的 LIFO 特性完美模拟了「最近打开」的要求
• 三种失败条件：(1) 空栈时遇到闭括号；(2) 括号类型不匹配；(3) 末尾还有未关闭的括号

思路： 全部压入最大堆，弹出 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;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < k && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

关键点：

• 优先队列自动把最大值放在顶部
• 每次 pop() 移除当前最大值，下一个最大值浮现
• 替代方案：降序排序后取前 K 个——结果相同

思路： 用 map<string, long long> 作为库存，解析每条命令并相应更新。

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

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

    int m;
    cin >> m;

    map<string, long long> inventory;

    while (m--) {
        string cmd;
        cin >> cmd;

        if (cmd == "ADD") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] += qty;
        } else if (cmd == "REMOVE") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] -= qty;
            if (inventory[name] < 0) inventory[name] = 0;
        } else {  // QUERY
            string name;
            cin >> name;
            // 用 count 检查存在性，避免为缺失的商品创建条目
            if (inventory.count(name)) {
                cout << inventory[name] << "\n";
            } else {
                cout << 0 << "\n";
            }
        }
    }

    return 0;
}

关键点：

• inventory[name] += qty——若 name 不存在，以 0 创建后加 qty（正确！）
• QUERY 时用 inventory.count(name) 检查存在性，避免悄悄创建值为 0 的条目
• 数量用 long long 以防较大

思路： 用 deque（双端队列）维护一个有用下标的窗口。双端队列按值的递减顺序存储下标——deque.front() 始终是当前窗口最大值的下标。

#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];

    deque<int> dq;  // 存储下标，队首 = 当前最大值的下标

    for (int i = 0; i < n; i++) {
        // 移除已超出当前窗口的下标
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 从队尾移除值小于 arr[i] 的下标
        //（只要 arr[i] 还在窗口里，它们就不可能成为最大值）
        while (!dq.empty() && arr[dq.back()] <= arr[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // 从窗口满的位置（下标 k-1）开始打印最大值
        if (i >= k - 1) {
            cout << arr[dq.front()] << "\n";
        }
    }

    return 0;
}

关键点：

• 双端队列维护「单调递减队列」的下标
• 队首 = 当前窗口最大值的下标
• 加入新元素 arr[i] 时：从队尾移除所有 ≤ arr[i] 的元素（它们无用——arr[i] 更大且在窗口中待的时间更长）
• 当该下标不再在窗口内时（下标 < i - k + 1），从队首移除
• 总计 O(N)——每个下标最多压入和弹出各一次

思路： 对位置排序，对每个查询用 lower_bound 和 upper_bound 在 O(log N) 内找出范围内的数量。

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

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

    int n, q;
    cin >> n >> q;

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

    sort(pos.begin(), pos.end());  // 二分查找前必须排序

    while (q--) {
        int l, r;
        cin >> l >> r;

        // lower_bound(l)：第一个 >= l 的位置
        // upper_bound(r)：第一个 > r 的位置
        // [l, r] 内的元素个数 = 这两个迭代器之间的距离
        auto lo = lower_bound(pos.begin(), pos.end(), l);
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";  // 迭代器间距离 = 个数
    }

    return 0;
}

关键点：

• 先对位置排序——二分查找的前提条件
• lower_bound(pos.begin(), pos.end(), l) 返回第一个 ≥ l 的元素的迭代器
• upper_bound(pos.begin(), pos.end(), r) 返回第一个 > r 的元素的迭代器
• [l, r] 内元素个数 = 两迭代器之间的距离 = hi - lo
• 总复杂度：排序 O(N log N) + 查询 O(Q log N)——远优于暴力 O(N×Q)

// 构建前缀和数组 — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    // 第一步：读取输入（1-indexed）
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) cin >> A[i];

    // 第二步：构建前缀和
    vector<long long> P(n + 1, 0);  // P[0] = 0（基础情况）
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];   // ← 关键行：每个 P[i] = 到 i 为止所有元素之和
    }

    return 0;
}

// 区间求和查询 — 预处理 O(N)，每次查询 O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
long long A[MAXN];
long long P[MAXN];

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

    int n, q;
    cin >> n >> q;

    // 第一步：读取数组
    for (int i = 1; i <= n; i++) cin >> A[i];

    // 第二步：构建前缀和 — O(n)
    P[0] = 0;
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];
    }

    // 第三步：回答 q 个区间求和查询 — 每次 O(1)
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";  // ← 关键行：区间和公式
    }

    return 0;
}

// 多品种前缀和 — O(N + Q)
#include <bits/stdc++.h>
using namespace std;

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

    int n, q;
    cin >> n >> q;

    vector<int> breed(n + 1);
    vector<vector<long long>> P(4, vector<long long>(n + 1, 0));
    // P[b][i] = 位置 1..i 中品种 b 的奶牛数量

    // 第一步：为每种品种构建前缀和
    for (int i = 1; i <= n; i++) {
        cin >> breed[i];
        for (int b = 1; b <= 3; b++) {
            P[b][i] = P[b][i - 1] + (breed[i] == b ? 1 : 0);  // ← 关键行
        }
    }

    // 第二步：每次查询 O(1) 回答
    for (int i = 0; i < q; i++) {
        int l, r, b;
        cin >> l >> r >> b;
        cout << P[b][r] - P[b][l - 1] << "\n";
    }

    return 0;
}

// FJ 的草地 — 前缀和解法 O(N + Q)
#include <bits/stdc++.h>
using namespace std;

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

    int n, q;
    cin >> n >> q;

    // 第一步：读取草量并同步构建前缀和
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long g;
        cin >> g;
        P[i] = P[i - 1] + g;   // ← 关键行：增量前缀和
    }

    // 第二步：每次查询 O(1) 回答
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";
    }

    return 0;
}

P[1][1] = A[1][1] = 1
P[1][2] = 2 + 0 + 1 - 0 = 3
P[1][3] = 3 + 0 + 3 - 0 = 6
P[1][4] = 4 + 0 + 6 - 0 = 10
P[2][1] = 5 + 1 + 0 - 0 = 6
P[2][2] = 6 + 3 + 6 - 1 = 14
P[2][3] = 7 + 6 + 14 - 3 = 24
P[2][4] = 8 + 10 + 24 - 6 = 36
P[3][1] = 9 + 6 + 0 - 0 = 15
P[3][2] = 10 + 14 + 15 - 6 = 33
P[3][3] = 11 + 24 + 33 - 14 = 54
P[3][4] = 12 + 36 + 54 - 24 = 78
P[4][1] = 13 + 15 + 0 - 0 = 28
P[4][2] = 14 + 33 + 28 - 15 = 60
P[4][3] = 15 + 54 + 60 - 33 = 96
P[4][4] = 16 + 78 + 96 - 54 = 136

// 二维前缀和 — 构建 O(R×C)，查询 O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 1001, MAXC = 1001;
int A[MAXR][MAXC];
long long P[MAXR][MAXC];

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

    int R, C;
    cin >> R >> C;

    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            cin >> A[r][c];

    // 第一步：构建二维前缀和 — O(R × C)
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            P[r][c] = A[r][c]
                    + P[r-1][c]    // 上方矩形
                    + P[r][c-1]    // 左方矩形
                    - P[r-1][c-1]; // ← 关键行：消除重叠（被计算了两次）
        }
    }

    // 第二步：每次查询 O(1) 回答
    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long ans = P[r2][c2]
                      - P[r1-1][c2]    // 减去上方条带
                      - P[r2][c1-1]    // 减去左方条带
                      + P[r1-1][c1-1]; // 加回左上角
        cout << ans << "\n";
    }

    return 0;
}

// 差分数组实现区间更新 — O(N + M)
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    // diff[i] 表示从位置 i 开始，当前值发生了多少变化
    // 多开 1 位：当更新区间右端点 r = n 时，需要访问 diff[n + 1]
    vector<long long> diff(n + 2, 0);

    // 第一步：处理所有区间更新
    for (int i = 0; i < m; i++) {
        int l, r;
        long long v;
        cin >> l >> r >> v;

        diff[l] += v;      // 从 l 开始，增加 v 生效
        diff[r + 1] -= v;  // 从 r+1 开始，取消这次增加
    }

    // 第二步：对 diff 做前缀和，得到最终数组
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur;
        if (i < n) cout << " ";
    }
    cout << "\n";

    return 0;
}

// 二维差分数组 — 每次矩形更新 O(1)，最终重建 O(R × C)
#include <bits/stdc++.h>
using namespace std;

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

    int R, C, M;
    cin >> R >> C >> M;

    // 多开一圈哨兵：当 r2=R 或 c2=C 时，会访问 r2+1 或 c2+1
    vector<vector<long long>> diff(R + 2, vector<long long>(C + 2, 0));

    // 第一步：每次 O(1) 标记一个矩形更新
    while (M--) {
        int r1, c1, r2, c2;
        long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;

        diff[r1][c1]         += v;
        diff[r1][c2 + 1]     -= v;
        diff[r2 + 1][c1]     -= v;
        diff[r2 + 1][c2 + 1] += v;
    }

    // 第二步：二维前缀和重建最终网格
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            diff[r][c] += diff[r - 1][c]
                        + diff[r][c - 1]
                        - diff[r - 1][c - 1];
        }
    }

    // 第三步：输出最终网格
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cout << diff[r][c];
            if (c < C) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}

// Kadane 算法 — O(N) 时间，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<int> A(n);
    for (int &x : A) cin >> x;

    // Kadane 算法：O(n)
    long long maxSum = LLONG_MIN;  // 最小 long long
    long long current = 0;

    for (int i = 0; i < n; i++) {
        current += A[i];
        maxSum = max(maxSum, current);
        if (current < 0) current = 0;  // ← 关键行：和为负时重新开始
    }

    cout << maxSum << "\n";

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO 官方文件 I/O 可按需打开：
    // freopen("bcount.in", "r", stdin);
    // freopen("bcount.out", "w", stdout);

    int n, q;
    cin >> n >> q;

    vector<array<int, 4>> prefix(n + 1);  // 只使用下标 1..3

    for (int i = 1; i <= n; i++) {
        int breed;
        cin >> breed;
        prefix[i] = prefix[i - 1];        // 继承前 i-1 头的计数
        prefix[i][breed]++;               // 当前品种加 1
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        for (int b = 1; b <= 3; b++) {
            int count = prefix[r][b] - prefix[l - 1][b];
            cout << count << " \n"[b == 3];
        }
    }

    return 0;
}

复杂度： 预处理 O(N × 3)，每次查询 O(3)，总复杂度 O(N+Q)，空间 O(3N)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO 官方文件 I/O 可按需打开：
    // freopen("stacking.in", "r", stdin);
    // freopen("stacking.out", "w", stdout);

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

    vector<int> diff(n + 2, 0);  // 需要写到 b+1，最大可能是 n+1

    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        diff[a] += 1;
        diff[b + 1] -= 1;
    }

    vector<int> height(n + 1);
    int current = 0;
    for (int i = 1; i <= n; i++) {
        current += diff[i];
        height[i] = current;
    }

    sort(height.begin() + 1, height.end());
    cout << height[(n + 1) / 2] << "\n";  // n 为奇数，中位数下标固定

    return 0;
}

复杂度： 区间更新 O(K)，重建 O(N)，排序 O(N log N)，空间 O(N)。