#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 ax1,ay1,ax2,ay2,bx1,by1,bx2,by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;
    
    long long ix1=max(ax1,bx1), iy1=max(ay1,by1);
    long long ix2=min(ax2,bx2), iy2=min(ay2,by2);
    
    if (ix2 <= ix1 || iy2 <= iy1) cout << 0;
    else cout << (ix2-ix1)*(iy2-iy1);
    cout << "\n";
}

思路： 用差分数组标记每个 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-1, y1~y2-1)
        diff[y1][x1]++;   diff[y2][x1]--;
        diff[y1][x2]--;   diff[y2][x2]++;
    }
    
    long long ans = 0;
    for (int i = 0; i <= 1000; i++)
        for (int j = 0; j <= 1000; j++) {
            if (i > 0) diff[i][j] += diff[i-1][j];
            if (j > 0) diff[i][j] += diff[i][j-1];
            if (i > 0 && j > 0) diff[i][j] -= diff[i-1][j-1];
            if (diff[i][j] > 0) ans++;
        }
    cout << ans << "\n";
}

#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_edge = (px==x1||px==x2) && (y1<=py&&py<=y2)
                    || (py==y1||py==y2) && (x1<=px&&px<=x2);
        bool inside = x1<px && px<x2 && y1<py && py<y2;
        if (on_edge) cout << "边界\n";
        else if (inside) cout << "内部\n";
        else cout << "外部\n";
    }
}

#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) 内找最大异或值。

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

    vector<long long> diff(n + 2, 0);  // 差分数组（多一位空间用于 R+1 情况）

    // 第一步：每次 O(1) 处理所有区间更新
    for (int i = 0; i < m; i++) {
        int l, r, v;
        cin >> l >> r >> v;
        diff[l] += v;      // ← 关键行：标记区间起点
        diff[r + 1] -= v;  // ← 关键行：标记终点+1 以撤销加法
    }

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

    return 0;
}

初始状态:           diff[1..6] = [0,  0,  0,  0,  0,  0]

更新(1,3,+2): diff[1]+=2, diff[4]-=2
              diff[1..6] = [2,  0,  0, -2,  0,  0]

更新(2,5,+3): diff[2]+=3, diff[6]-=3
              diff[1..6] = [2,  3,  0, -2,  0, -3]

更新(3,4,-1): diff[3]-=1, diff[5]+=1
              diff[1..6] = [2,  3, -1, -2,  1, -3]

前缀和重建：
i=1: running = 0+2 = 2  → result[1] = 2
i=2: running = 2+3 = 5  → result[2] = 5
i=3: running = 5-1 = 4  → result[3] = 4
i=4: running = 4-2 = 2  → result[4] = 2
i=5: running = 2+1 = 3  → result[5] = 3

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

const int MAXR = 1002, MAXC = 1002;
long long diff[MAXR][MAXC];  // 额外行列用于哨兵

void update(int r1, int c1, int r2, int c2, long long V) {
    diff[r1][c1]     += V;  // ← 左上角
    diff[r1][c2+1]   -= V;  // ← 右上+1
    diff[r2+1][c1]   -= V;  // ← 下+1左
    diff[r2+1][c2+1] += V;  // ← 下+1右+1（加回）
}

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

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

    memset(diff, 0, sizeof diff);

    // 第一步：每次 O(1) 应用所有矩形更新
    for (int i = 0; i < M; i++) {
        int r1, c1, r2, c2;
        long long V;
        cin >> r1 >> c1 >> r2 >> c2 >> V;
        update(r1, c1, r2, c2, V);
    }

    // 第二步：通过二维前缀和重建 — O(R × C)
    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];

    // 现在 diff[r][c] 存储 (r,c) 处的最终值
    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;
}

核心思路： O(N) 预计算前缀和，每次查询 O(1) 回答 P[R] - P[L-1]。

#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++) {
        int x; cin >> x;
        P[i] = P[i-1] + x;
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << P[r] - P[l-1] << "\n";
    }
}

复杂度： O(N + Q) —— 远好于朴素 O(N × Q)。

核心思路： 差分数组。每次区间加法只影响 diff 的 2 个位置，最终值通过前缀和得到。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<long long> diff(n + 2, 0);
    while (m--) {
        int l, r; long long v; cin >> l >> r >> v;
        diff[l] += v;
        diff[r+1] -= v;
    }
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }
}

复杂度： O(N + M) —— 每次更新 O(1)，最后扫描 O(N)。

核心思路： 二维前缀和。P[i][j] = 从 (1,1) 到 (i,j) 的矩形和，对任意矩形查询用容斥相减。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m, q; cin >> n >> m >> q;
    vector<vector<long long>> P(n+1, vector<long long>(m+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x; cin >> x;
            P[i][j] = x + P[i-1][j] + P[i][j-1] - P[i-1][j-1];
        }
    while (q--) {
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1] << "\n";
    }
}

复杂度： O(N × M + Q)。

核心思路： 直接模拟——不需要复杂数据结构。沿路径走，对每个访问的格子递增二维计数器。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    map<pair<int,int>, int> cnt;
    int x = 0, y = 0; cnt[{x,y}]++;
    while (n--) {
        char dir; int steps; cin >> dir >> steps;
        int dx = (dir=='E') - (dir=='W');
        int dy = (dir=='N') - (dir=='S');
        while (steps--) {
            x += dx; y += dy;
            cnt[{x,y}]++;
        }
    }
    int doubleMowed = 0;
    for (auto& [pos, c] : cnt) if (c >= 2) doubleMowed++;
    cout << doubleMowed << "\n";
}

复杂度： O(总步数 × log)，受 map 操作主导。

核心思路： 二维差分数组。每次矩形更新只触及 4 个角。最终网格 = 差分数组的二维前缀和。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, q; cin >> n >> m >> q;
    vector<vector<long long>> D(n+2, vector<long long>(m+2, 0));
    while (q--) {
        int r1, c1, r2, c2; long long v;
        cin >> r1 >> c1 >> r2 >> c2 >> v;
        D[r1][c1] += v;
        D[r1][c2+1] -= v;
        D[r2+1][c1] -= v;
        D[r2+1][c2+1] += v;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << D[i][j] << " \n"[j == m];
}

复杂度： O(Q + N × M)。

核心思路： 在每个位置，要么开始新的子数组，要么延伸当前的。cur = max(A[i], cur + A[i])，追踪最优值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    long long best = LLONG_MIN, cur = 0;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        cur = max(x, cur + x);
        best = max(best, cur);
    }
    cout << best << "\n";
}

为什么当 cur+x < x 时从头开始？ 因为负的运行和只会损害未来的项——丢弃它，从当前元素重新开始。

追踪 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：

x=-2: cur=-2, best=-2
x=1:  cur=max(1,-2+1)=1, best=1
x=-3: cur=max(-3,1-3)=-2, best=1
x=4:  cur=max(4,-2+4)=4, best=4
x=-1: cur=max(-1,4-1)=3, best=4
x=2:  cur=5, best=5
x=1:  cur=6, best=6 ✓
x=-5: cur=1, best=6
x=4:  cur=5, best=6

复杂度： O(N) 时间，O(1) 空间。

朴素枚举所有 O(N²M²) 矩形对 500² 来说太慢。改进方案：

1. 用二维前缀和实现 O(1) 求和查询
2. 对子网格中的最大值：预处理二维稀疏表（或每行 RMQ）实现 O(1) 最大值查询
3. 边界和 = 总和 - 内部和（均通过前缀和）

总计：O(N²M²) 枚举 × O(1) 每次查询 = 对 N,M ≤ 500 在时间限制内。

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];   // 要插入的元素
        int j = i - 1;
        // 将大于 key 的元素向右移动一位
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;  // 把 key 放到正确位置
    }
}

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp(a.begin() + lo, a.begin() + hi + 1);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (tmp[i - lo] <= tmp[j - lo]) {
            a[k++] = tmp[i - lo];  // 左半部分更小，优先放入以保持稳定性
            i++;
        } else {
            a[k++] = tmp[j - lo];
            j++;
        }
    }
    while (i <= mid) { a[k++] = tmp[i - lo]; i++; }
    while (j <= hi)  { a[k++] = tmp[j - lo]; j++; }
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

// 对 arr[lo..hi] 用最后一个元素作枢轴进行分区。
// 返回枢轴的最终下标。
int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];   // 选最后一个元素为枢轴
    int i = lo - 1;        // i 指向「≤ 枢轴」区域的末尾

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // 把 arr[j] 纳入 ≤ 枢轴区域
        }
    }
    swap(arr[i + 1], arr[hi]);  // 把枢轴放到最终位置
    return i + 1;               // 返回枢轴的下标
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;           // 基础情况：子数组长度 ≤ 1
    int p = partition(arr, lo, hi); // p 是枢轴的最终位置
    quickSort(arr, lo, p - 1);      // 排序左子数组
    quickSort(arr, p + 1, hi);      // 排序右子数组
}

// 计数排序（稳定，O(N+W)）
// 要求：所有元素在 [0, W) 范围内
void countingSort(vector<int>& a, int W) {
    int n = a.size();
    vector<int> cnt(W, 0), out(n);

    // 第一步：统计每个值的出现次数
    for (int x : a) cnt[x]++;

    // 第二步：变为前缀和（cnt[i] = 最终 <= i 的元素个数）
    for (int i = 1; i < W; i++) cnt[i] += cnt[i-1];

    // 第三步：从后向前放置（保证稳定性！）
    for (int i = n - 1; i >= 0; i--) {
        out[--cnt[a[i]]] = a[i];
    }
    a = out;
}

// 对键范围已知的使用示例：
// countingSort(arr, 100);  // 所有元素在 [0, 99]

// 基数排序（以 10 为基数的十进制版本）
// O(N * d)，d 为最大数的十进制位数
void radixSort(vector<int>& a) {
    int maxVal = *max_element(a.begin(), a.end());
    int n = a.size();

    // 从最低位（个位）到最高位逐位排序
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> cnt(10, 0), out(n);

        // 统计当前位的频率
        for (int i = 0; i < n; i++)
            cnt[(a[i] / exp) % 10]++;

        // 前缀和
        for (int i = 1; i < 10; i++)
            cnt[i] += cnt[i-1];

        // 从后向前放置（稳定性保证）
        for (int i = n-1; i >= 0; i--) {
            int digit = (a[i] / exp) % 10;
            out[--cnt[digit]] = a[i];
        }
        a = out;
    }
}

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

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

    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    // 升序排序
    sort(v.begin(), v.end());

    // 降序排序
    sort(v.begin(), v.end(), greater<int>());

    // 只排序向量的一部分（下标 2 到 5，含）
    sort(v.begin() + 2, v.begin() + 6);

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

    return 0;
}

struct Cow {
    string name;
    int weight;
    int height;
};

// 按体重升序；体重相同时按身高降序
bool cmpCow(const Cow &a, const Cow &b) {
    if (a.weight != b.weight) return a.weight < b.weight;  // 较轻的优先
    return a.height > b.height;                             // 打平：较高的优先
}

int main() {
    vector<Cow> cows = {{"Bessie", 500, 140}, {"Elsie", 480, 135}, {"Moo", 500, 138}};

    sort(cows.begin(), cows.end(), cmpCow);

    for (auto &c : cows) {
        cout << c.name << " " << c.weight << " " << c.height << "\n";
    }
    // 输出：
    // Elsie 480 135
    // Bessie 500 140
    // Moo 500 138
    return 0;
}

// 二分查找 — O(log N)
#include <bits/stdc++.h>
using namespace std;

// 在有序 arr 中返回 target 的下标，未找到返回 -1
int binarySearch(const vector<int> &arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // ← 关键行：避免溢出（不要用 (lo+hi)/2）

        if (arr[mid] == target) {
            return mid;         // 找到！
        } else if (arr[mid] < target) {
            lo = mid + 1;       // 目标在右半部分
        } else {
            hi = mid - 1;       // 目标在左半部分
        }
    }

    return -1;  // 未找到
}

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << binarySearch(v, 7) << "\n";   // 3（下标）
    cout << binarySearch(v, 6) << "\n";   // -1（未找到）
    return 0;
}

// STL 二分操作 — 全部 O(log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};

    // lower_bound：第一个 >= target 的迭代器
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << *lb << "\n";                    // 3（第一个 3）
    cout << lb - v.begin() << "\n";         // 1（下标）

    // upper_bound：第一个 > target 的迭代器
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << *ub << "\n";                    // 5（所有 3 后面的第一个元素）
    cout << ub - v.begin() << "\n";         // 3（下标）

    // 统计出现次数：upper_bound - lower_bound
    int count_of_3 = upper_bound(v.begin(), v.end(), 3)
                   - lower_bound(v.begin(), v.end(), 3);
    cout << count_of_3 << "\n";   // 2

    // 检查是否存在
    bool exists = binary_search(v.begin(), v.end(), 7);
    cout << exists << "\n";  // 1

    // 找 <= target 的最大值（向下取整）
    auto it = upper_bound(v.begin(), v.end(), 6);
    if (it != v.begin()) {
        --it;
        cout << *it << "\n";  // 5（<= 6 的最大值）
    }

    return 0;
}

// 二分答案 — O(N log N log(最大距离))
#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> stalls;

// 能否放置 c 头奶牛使任意两头间距 >= minDist？
bool canPlace(int minDist) {
    int placed = 1;           // 第一头放在马厩 0
    int lastPos = stalls[0];  // 最后放置的奶牛的位置

    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPos >= minDist) {  // 这个马厩足够远
            placed++;
            lastPos = stalls[i];
        }
    }
    return placed >= c;  // 放了 c 头奶牛吗？
}

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

    cin >> n >> c;
    stalls.resize(n);
    for (int &x : stalls) cin >> x;
    sort(stalls.begin(), stalls.end());  // 必须先排序！

    // 二分答案：最大可能的最小距离是多少？
    int lo = 1, hi = stalls.back() - stalls.front();
    int answer = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) {
            answer = mid;    // mid 可行，尝试更大的
            lo = mid + 1;
        } else {
            hi = mid - 1;    // mid 不可行，尝试更小的
        }
    }

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

排序后：[1, 2, 4, 8, 9]
lo=1, hi=8

mid=4：canPlace(4)？
  在 1 放奶牛。下一个 ≥ 1+4=5 的：8，放在 8。
  下一个 ≥ 8+4=12：没有。总共放了 2 头 < 3。返回 false。
  → hi = 3

mid=2：canPlace(2)？
  在 1 放。下一个 ≥ 3：4，放在 4。
  下一个 ≥ 6：8，放在 8。总共 3 头 ≥ 3。返回 true。
  → answer=2, lo=3

mid=3：canPlace(3)？
  在 1 放。下一个 ≥ 4：4，放在 4。
  下一个 ≥ 7：8，放在 8。总共 3 头 ≥ 3。返回 true。
  → answer=3, lo=4

lo=4 > hi=3：结束。答案 = 3

// 代码片段 — 完整程序请参考攻击性奶牛示例
// 能否从绳子中切出 K 段长度 >= len 的？
bool canCut(vector<int> &ropes, long long len, int K) {
    long long count = 0;
    for (int r : ropes) count += r / len;  // 每根绳子能切出的段数
    return count >= K;
}

// 二分：最大化 len 使 canCut(len) 为真
long long lo = 1, hi = *max_element(ropes.begin(), ropes.end());
long long answer = 0;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canCut(ropes, mid, K)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}

// 通用模板 — 根据题目调整 lo、hi 和 check()
long long lo = 最小可能答案;
long long hi = 最大可能答案;
long long answer = lo;  // 若无有效答案则为 -1

while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) {       // mid 可行
        answer = mid;       // 保存
        lo = mid + 1;       // 尝试更好的（取决于题目是更大还是更小）
    } else {
        hi = mid - 1;       // mid 不可行，降低
    }
}

// 坐标压缩 — O(N log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> A = {100, 500, 200, 100, 700, 200};

    // 第一步：获取有序唯一值
    vector<int> sorted_unique = A;
    sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()),
                        sorted_unique.end());
    // sorted_unique = {100, 200, 500, 700}

    // 第二步：将每个原始值映射到压缩后的下标
    vector<int> compressed(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        compressed[i] = lower_bound(sorted_unique.begin(), sorted_unique.end(), A[i])
                        - sorted_unique.begin();
        // 100→0, 200→1, 500→2, 700→3
    }

    for (int x : compressed) cout << x << " ";
    cout << "\n";  // 0 2 1 0 3 1

    return 0;
}

// 检查：能否将任务分配给 K 个工人，使每人工作量 <= T？
bool canFinish(vector<int>& tasks, int K, long long T) {
    int workers = 1;
    long long current = 0;
    for (int t : tasks) {
        if (t > T) return false;  // 单个任务超过 T——不可能
        if (current + t > T) {
            workers++;             // 开始新工人
            current = t;
            if (workers > K) return false;
        } else {
            current += t;
        }
    }
    return true;
}

// 对 T 二分 — 用「lo < hi」模板（最小化答案）
long long lo = *max_element(tasks.begin(), tasks.end());  // T 的最小可能值
long long hi = accumulate(tasks.begin(), tasks.end(), 0LL);  // T 的最大值（1 个工人）

while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canFinish(tasks, K, mid)) hi = mid;  // mid 可行，尝试更小
    else lo = mid + 1;                        // mid 不可行，需要更大
}
cout << lo << "\n";  // 最小可能最大时间（循环结束时 lo == hi）

// 统计 N×M 乘法表中 <= X 的值的个数
long long countLE(long long X, int N, int M) {
    long long count = 0;
    for (int i = 1; i <= N; i++) {
        count += min((long long)M, X / i);
        // 第 i 行的值是 i, 2i, ..., Mi
        // 第 i 行中 <= X 的个数：min(M, floor(X/i))
    }
    return count;
}

// 二分查找第 K 小
long long lo = 1, hi = (long long)N * M;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (countLE(mid, N, M) >= K) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

// 注意：以下代码假设已定义：#define all(v) (v).begin(), (v).end()
vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};
//               0  1  2  3  4  5  6   7

// ── lower_bound：第一个 >= x 的位置 ──
lower_bound(all(v), 3)  → 下标 1  （第一个 3）
lower_bound(all(v), 4)  → 下标 3  （第一个 >= 4 的元素，即 5）
lower_bound(all(v), 12) → 下标 8  （越界：没有 >= 12 的元素）

// ── upper_bound：第一个 > x 的位置 ──
upper_bound(all(v), 3)  → 下标 3  （所有 3 之后的第一个元素）
upper_bound(all(v), 4)  → 下标 3  （与上同：没有 4）
upper_bound(all(v), 11) → 下标 8  （越界）

// ── 派生操作 ──
// 统计 x 的出现次数：
int cnt = upper_bound(all(v), 3) - lower_bound(all(v), 3);  // cnt = 2

// x 是否存在？
binary_search(all(v), x)  // O(log N)，返回 bool

// <= x 的最大值（向下取整）：
auto it = upper_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);

// >= x 的最小值（向上取整）：
auto it = lower_bound(all(v), x);
if (it != v.end()) cout << *it;

// < x 的最大值（严格向下取整）：
auto it = lower_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);

// < x 的元素个数：
lower_bound(all(v), x) - v.begin()

// <= x 的元素个数：
upper_bound(all(v), x) - v.begin()

// [a, b] 范围内的元素个数：
upper_bound(all(v), b) - lower_bound(all(v), a)

// 自定义谓词二分查找
// 在 [lo, hi] 范围内找第一个 pred(i) 为真的下标
// 假设：pred 单调，即 false...false, true...true

int lo = 0, hi = n - 1, answer = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (/* mid 上的某个条件 */) {
        answer = mid;
        hi = mid - 1;  // 找更小的下标
    } else {
        lo = mid + 1;
    }
}

// 示例：第一个 arr[i] - arr[0] >= D 的下标
// （对有序数组，arr[i] - arr[0] 单调非递减，
//  所以这个谓词是单调的：假...假，真...真）
// ⚠️ 关键要求：谓词必须单调，二分查找才有效！
{
    int lo = 0, hi = n - 1, firstFar = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] - arr[0] >= D) {
            firstFar = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
}

// 浮点数二分查找（基于精度）
double lo_f = 0.0, hi_f = 1e9;
for (int iter = 0; iter < 100; iter++) {  // 100 次迭代 → 误差 < 1e-30
    double mid = (lo_f + hi_f) / 2;
    if (check(mid)) hi_f = mid;
    else lo_f = mid;
}
// 答案：lo_f（或 hi_f，两者收敛到相同值）

// 三分查找：求单峰函数 f 在 [lo, hi] 上的极大值
// 前提：f 先增后减（单峰）
// 时间：连续情况 O(log((hi-lo)/eps))，整数情况 O(log N)

// f 必须在调用前声明/定义
double ternarySearch(double lo, double hi) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;  // 极大值在 [m1, hi] 中
        else hi = m2;                 // 极大值在 [lo, m2] 中
    }
    return (lo + hi) / 2;  // 极大值点（收敛后 lo ≈ hi）
}

// 整数三分查找（f 定义在整数上时）：
int ternarySearchInt(int lo, int hi) {
    // 用 > 2 而非 >= 2：保留至少 3 个候选值再暴力枚举。
    // 范围缩至 2 时，m1 == m2（因为 (hi-lo)/3 == 0），会死循环。
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1 + 1;
        else hi = m2 - 1;
    }
    // 检查剩余候选值 [lo, hi]（最多 3 个元素）
    int best = lo;
    for (int x = lo + 1; x <= hi; x++)
        if (f(x) > f(best)) best = x;
    return best;
}

核心思路： 排序后，相似的值相邻。最近的一对总是排序后的相邻元素。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    int best = INT_MAX;
    for (int i = 1; i < n; i++)
        best = min(best, a[i] - a[i-1]);
    cout << best << "\n";
}

为什么是相邻的？ 若 |a[i] - a[j]| 最小且 j > i+1，则 a[i+1] 在它们之间，所以 a[i+1]-a[i] ≤ a[j]-a[i]，矛盾。

复杂度： O(N log N)。

核心思路： 扫描线。每个开始 +1，每个结束 -1，运行和 = 当前重叠数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<pair<int,int>> evs;
    for (int i = 0; i < n; i++) {
        int s, e; cin >> s >> e;
        evs.push_back({s, +1});
        evs.push_back({e, -1});
    }
    // 相同时间时先处理结束（delta=-1），「相切」的区间不计为重叠
    sort(evs.begin(), evs.end(),
         [](auto& a, auto& b){ return a.first != b.first ? a.first < b.first : a.second < b.second; });
    int cur = 0, best = 0;
    for (auto& [t, d] : evs) { cur += d; best = max(best, cur); }
    cout << best << "\n";
}

对区间 [(1,4), (2,6), (3,5)] 的追踪：

事件：(1,+1), (2,+1), (3,+1), (4,-1), (5,-1), (6,-1)
扫描：  1       2       3       2       1       0
最大：3（时刻 3 时三个区间同时活跃）

复杂度： O(N log N)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for (int& x : a) cin >> x;
    // nth_element 重新排列，使 a[k-1] 到达正确的有序位置
    nth_element(a.begin(), a.begin() + (k-1), a.end());
    cout << a[k-1] << "\n";
}

替代方案：二分答案

int lo = *min_element(a.begin(), a.end());
int hi = *max_element(a.begin(), a.end());
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    int cnt = count_if(a.begin(), a.end(), [&](int x){ return x <= mid; });
    if (cnt >= k) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

复杂度： nth_element 平均 O(N)，最坏 O(N²)；二分答案 O(N log(最大值))。

核心思路： 对答案 D 二分。可行性：贪心地从最左侧马厩开始放奶牛，每次跳到距离 ≥ D 的下一个。

#include <bits/stdc++.h>
using namespace std;
int N, C;
vector<int> p;

bool canPlace(int D) {
    int placed = 1, last = p[0];
    for (int i = 1; i < N; i++) {
        if (p[i] - last >= D) { placed++; last = p[i]; }
        if (placed >= C) return true;
    }
    return false;
}

int main() {
    cin >> N >> C;
    p.resize(N); for (int& x : p) cin >> x;
    sort(p.begin(), p.end());

    int lo = 1, hi = p.back() - p.front(), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    cout << ans << "\n";
}

复杂度： O(N log N + N log(最大距离))。

核心思路： 对答案 T 二分。可行性：贪心为每个画家填充画板，超过 T 时换下一个画家，若 ≤ K 个画家就够，T 可行。

#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<long long> W;

bool canFinish(long long T) {
    int painters = 1;
    long long cur = 0;
    for (long long w : W) {
        if (w > T) return false;  // 单块画板超出预算
        if (cur + w > T) { painters++; cur = w; }
        else cur += w;
    }
    return painters <= K;
}

int main() {
    cin >> N >> K;
    W.resize(N); for (long long& x : W) cin >> x;
    long long lo = *max_element(W.begin(), W.end());  // 下界：最宽的画板
    long long hi = accumulate(W.begin(), W.end(), 0LL);  // 上界：总宽度
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
}

复杂度： O(N log(总宽度))。

排序陷阱：

• ❌ 比较器用 > 代替 <（排序需要严格弱序）
• ❌ 比较器返回 a <= b——违反严格弱序，可能导致未定义行为
• ❌ 比较器有副作用或随机性——必须是确定性的

二分查找陷阱：

• ❌ mid = (lo + hi) / 2——lo+hi 很大时溢出，用 lo + (hi - lo) / 2
• ❌ 死循环：未找到目标时 lo = mid（而不是 mid+1）
• ❌ 「第一个/最后一个位置」变体中的边界错误——先画出不变量
• ❌ 浮点数二分：用精度终止条件 while (hi - lo > 1e-9)

二分答案陷阱：

• ❌ 检查函数不单调——二分查找无效！验证：若 D 可行，D-1 也可行吗？
• ❌ 边界太紧（遗漏边界情况）：将 lo 设为最小可能答案，hi 设为明确可行的上界

// 双指针 — 排序 O(N log N) + 搜索 O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    sort(arr.begin(), arr.end());  // 必须先排序

    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << arr[left] << " + " << arr[right] << " = " << target << "\n";
            left++;
            right--;  // 同时移动两个指针
        } else if (sum < target) {
            left++;   // 和太小：左指针右移（增大和）
        } else {
            right--;  // 和太大：右指针左移（减小和）
        }
    }

    return 0;
}

状态：left=0(1), right=7(8)
  和 = 1+8 = 9 ✓ → 打印 (1,8)，left++，right--

状态：left=1(2), right=6(7)
  和 = 2+7 = 9 ✓ → 打印 (2,7)，left++，right--

状态：left=2(3), right=5(6)
  和 = 3+6 = 9 ✓ → 打印 (3,6)，left++，right--

状态：left=3(4), right=4(5)
  和 = 4+5 = 9 ✓ → 打印 (4,5)，left++，right--

状态：left=4, right=3 → left >= right，停止

所有对：(1,8)，(2,7)，(3,6)，(4,5)

// O(N²) — 远优于 O(N³) 暴力
sort(arr.begin(), arr.end());
for (int i = 0; i < n - 2; i++) {
    int left = i + 1, right = n - 1;
    while (left < right) {
        int sum = arr[i] + arr[left] + arr[right];
        if (sum == target) {
            cout << arr[i] << " " << arr[left] << " " << arr[right] << "\n";
            left++; right--;
        } else if (sum < target) left++;
        else right--;
    }
}

// 固定大小滑动窗口 — O(N)
#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 &x : arr) cin >> x;

    // 计算第一个窗口的和
    long long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];

    long long maxSum = windowSum;

    // 滑动窗口：加 arr[i]，减 arr[i-k]
    for (int i = k; i < n; i++) {
        windowSum += arr[i];        // 新元素进入窗口
        windowSum -= arr[i - k];   // 旧元素离开窗口
        maxSum = max(maxSum, windowSum);
    }

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

// 可变大小窗口 — O(N)
#include <bits/stdc++.h>
using namespace std;

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

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    int left = 0;
    long long windowSum = 0;
    int minLen = INT_MAX;

    for (int right = 0; right < n; right++) {
        windowSum += arr[right];   // 扩张：加入右端元素

        // 满足约束时从左收缩
        while (windowSum >= target) {
            minLen = min(minLen, right - left + 1);
            windowSum -= arr[left];
            left++;                // 收缩：移除左端元素
        }
    }

    if (minLen == INT_MAX) cout << 0 << "\n";  // 不存在这样的子数组
    else cout << minLen << "\n";

    return 0;
}

// 可变窗口：最多 K 个不同值的最长子数组
int left = 0, maxLen = 0;
map<int, int> freq;  // 窗口内每个值的频率

for (int right = 0; right < n; right++) {
    freq[arr[right]]++;

    // 有 > k 个不同值时收缩
    while ((int)freq.size() > k) {
        freq[arr[left]]--;
        if (freq[arr[left]] == 0) freq.erase(arr[left]);
        left++;
    }

    maxLen = max(maxLen, right - left + 1);
}
cout << maxLen << "\n";

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, T; cin >> n >> T;
    vector<int> a(n); for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    long long cnt = 0;
    int L = 0, R = n - 1;
    while (L < R) {
        int s = a[L] + a[R];
        if (s == T) {
            if (a[L] == a[R]) {
                // [L..R] 内所有对都有效
                long long len = R - L + 1;
                cnt += len * (len - 1) / 2;
                break;
            }
            // 统计两侧的重复值
            long long cl = 1, cr = 1;
            while (L+1 < R && a[L+1] == a[L]) { cl++; L++; }
            while (R-1 > L && a[R-1] == a[R]) { cr++; R--; }
            cnt += cl * cr;
            L++; R--;
        } else if (s < T) L++;
        else R--;
    }
    cout << cnt << "\n";
}

复杂度： O(N log N)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<double> a(n); for (double& x : a) cin >> x;
    double windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += a[i];
    double maxSum = windowSum;
    for (int i = k; i < n; i++) {
        windowSum += a[i] - a[i-k];
        maxSum = max(maxSum, windowSum);
    }
    cout << fixed << setprecision(5) << maxSum / k << "\n";
}

复杂度： O(N)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string S, T; cin >> S >> T;
    unordered_map<char,int> need, have;
    for (char c : T) need[c]++;
    int formed = 0, required = need.size();
    int L = 0, minLen = INT_MAX, minL = 0;
    for (int R = 0; R < (int)S.size(); R++) {
        have[S[R]]++;
        if (need.count(S[R]) && have[S[R]] == need[S[R]]) formed++;
        while (formed == required) {
            if (R - L + 1 < minLen) { minLen = R-L+1; minL = L; }
            have[S[L]]--;
            if (need.count(S[L]) && have[S[L]] < need[S[L]]) formed--;
            L++;
        }
    }
    if (minLen == INT_MAX) cout << "no solution\n";
    else cout << S.substr(minL, minLen) << "\n";
}

样例： S="ADOBECODEBANC"，T="ABC" → "BANC" 复杂度： O(|S| + |T|)。

数组 A：[2, 1, 5, 6, 2, 3]
下标：    0  1  2  3  4  5

处理 i=0 (A[0]=2)：栈为空 → 压入 0
栈：[0]          // 栈存放未解决元素的下标

处理 i=1 (A[1]=1)：A[1]=1 < A[0]=2 → 直接压入
栈：[0, 1]

处理 i=2 (A[2]=5)：
  A[2]=5 > A[1]=1 → 弹出 1，NGE[1] = 2  (A[2]=5 是 A[1] 的下一个更大元素)
  A[2]=5 > A[0]=2 → 弹出 0，NGE[0] = 2  (A[2]=5 是 A[0] 的下一个更大元素)
  栈为空 → 压入 2
栈：[2]

处理 i=3 (A[3]=6)：
  A[3]=6 > A[2]=5 → 弹出 2，NGE[2] = 3
  压入 3
栈：[3]

处理 i=4 (A[4]=2)：A[4]=2 < A[3]=6 → 直接压入
栈：[3, 4]

处理 i=5 (A[5]=3)：
  A[5]=3 > A[4]=2 → 弹出 4，NGE[4] = 5
  A[5]=3 < A[3]=6 → 停止，压入 5
栈：[3, 5]

结束：栈中剩余 [3, 5] → NGE[3] = NGE[5] = -1（右侧无更大元素）

结果：NGE = [2, 2, 3, -1, 5, -1]
验证：
  A[0]=2，下一个更大是 A[2]=5 ✓
  A[1]=1，下一个更大是 A[2]=5 ✓
  A[2]=5，下一个更大是 A[3]=6 ✓
  A[3]=6，无更大 → -1 ✓

// 用单调栈求下一个更大元素 — O(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> A(n);
    for (int& x : A) cin >> x;

    vector<int> nge(n, -1);   // nge[i] = 下一个更大元素的下标，不存在则为 -1
    stack<int> st;             // 单调递减栈（存下标）

    for (int i = 0; i < n; i++) {
        // 当栈顶元素小于 A[i] 时
        // → 当前元素 A[i] 是那些元素的 NGE
        while (!st.empty() && A[st.top()] < A[i]) {
            nge[st.top()] = i;  // ← 关键：记录栈顶的 NGE
            st.pop();
        }
        st.push(i);  // 压入当前下标（尚未解决）
    }
    // 栈中剩余元素没有 NGE → 已初始化为 -1

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

    return 0;
}

// 上一个更小元素：对每个 i，找最近的 j < i 使得 A[j] < A[i]
vector<int> pse(n, -1);  // pse[i] = 上一个更小元素的下标，不存在则为 -1
stack<int> st;

for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] >= A[i]) {
        st.pop();  // 弹出 >= A[i] 的元素（它们不是「上一个更小」）
    }
    pse[i] = st.empty() ? -1 : st.top();  // 栈顶就是上一个更小
    st.push(i);
}