题意：Bessie 从 M 数到 N，把每个数都写下来。问数码 0~9 各出现了多少次。

思路

开一个 10 个元素的桶 cnt[0..9]。对区间里每个数，把它拆成各位数字，每拆出一位就往对应的桶里放一颗。

129 137

1 10 2 9 1 1 1 1 0 1

含义：0 出现 1 次、1 出现 10 次、2 出现 2 次 …… 8 出现 0 次、9 出现 1 次。

完整代码

#include <iostream>
using namespace std;

int cnt[10] = {0};          // 桶：cnt[d] = 数码 d 出现的次数

void countNumber(long long x){
    if(x == 0){ cnt[0]++; return; }     // 数字 0 本身（本题 M>=1 用不到）
    while(x > 0){
        cnt[x % 10]++;                  // 取末位，丢进对应的桶
        x /= 10;                        // 去掉末位
    }
}

int main(){
    long long M, N;
    cin >> M >> N;
    for(long long i = M; i <= N; i++){  // 区间长度 ≤ 5×10^5，直接枚举
        countNumber(i);
    }
    for(int d = 0; d < 10; d++){
        if(d) cout << " ";
        cout << cnt[d];
    }
    cout << endl;
    return 0;
}

易错点

• 用 int 存 M、N 是够的（2×10⁹ < 21亿），但用 long long 更保险。
• 输出是 10 个数字用空格隔开，注意最后一个后面不要多打空格（用 if(d) cout << " "; 或判断 d < 9）。
• 拆位必须用临时变量，不能直接改循环变量 i。

题意：在 1 到 n 的所有整数中，数字 x（0 ≤ x ≤ 9）共出现了多少次？

例：1 到 11 中，数字 1 在 1、10、11 里出现，共 4 次。

思路

枚举 1 到 n 的每个数，把每个数拆位，拆出来的每一位和 x 比一下，相等就答案 +1。

11 1

4

完整代码

#include <iostream>
using namespace std;
int main(){
    int n, x;
    cin >> n >> x;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int t = i;                      // ★ 用临时变量拆位，别把 i 本身改掉
        while(t > 0){
            if(t % 10 == x) ans++;      // 末位正好是 x，计数 +1
            t /= 10;                    // 去掉末位
        }
    }
    cout << ans << endl;
    return 0;
}

易错点

• 不要用 i 直接拆位——会用 i /= 10 把外层循环搞坏。必须 int t = i;。
• x = 0 的情况要能正确处理。因为 i 从 1 开始，不会遇到数字 0 本身，但 10、20、100 里的 0 会被正常统计到。
• 没必要求 i 有几位再循环——while(t > 0) 自动处理了。

题意：彩票每张 7 个号码（取值 1~33）。给出中奖号码和 n 张彩票，按「猜中几个号码」分别统计特等奖（7个）到六等奖（1个）各有几张。

不看位置，只看号码在不在中奖号码里。

2
23 31 1 14 19 17 18
12 8 9 23 1 16 7
11 7 10 21 2 9 31

0 0 0 0 0 1 1

第 1 张：中了 23、1 → 2 个 → 五等奖
第 2 张：中了 31 → 1 个 → 六等奖
输出顺序是「特等 一等 二等 三等 四等 五等 六等」。

完整代码

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;

    bool win[34] = {false};             // 桶：win[k] 标记号码 k 是不是中奖号
    for(int i = 0; i < 7; i++){
        int t; cin >> t;
        win[t] = true;
    }

    int result[8] = {0};                // result[k] = 中了 k 个号码的彩票张数
    for(int i = 0; i < n; i++){
        int hit = 0;
        for(int j = 0; j < 7; j++){
            int t; cin >> t;
            if(win[t]) hit++;           // O(1) 查桶
        }
        if(hit >= 1) result[hit]++;
    }

    // 题目要求：先输出特等奖(中7个)，再依次一等奖(6个)…六等奖(1个)
    for(int k = 7; k >= 1; k--){
        if(k < 7) cout << " ";
        cout << result[k];
    }
    cout << endl;
    return 0;
}

易错点

• 输出顺序是倒着的！题目要「特等奖、一等奖……六等奖」，也就是中 7 个的先输出。
  所以循环要写 for(k = 7; k >= 1; k--)，不是从小到大。
• 桶开 bool win[34] 就够（号码最大 33），下标 0 用不上也无所谓，多开一个更安全。
• 中 0 个号码的彩票不计入任何奖项，所以 result[0] 根本用不上，加个 if(hit >= 1) 更清楚。

题意：三个骰子分别有 S₁、S₂、S₃ 个面（面上是 1 到 Sᵢ）。掷出所有组合，哪个「三个点数之和」出现得最频繁？如果有并列，输出最小的那个和。

3 2 3

5

题目提示里给了全部 18 种组合：和 5 与和 6 各出现 5 次并列最多，取小的 → 5。

思路

三重循环枚举所有点数组合（最多 20×20×40 = 16000 种，非常小），把每个「和」丢进对应的桶。然后从小到大扫一遍桶，找出现次数最多的那个和。

完整代码

#include <iostream>
using namespace std;
int main(){
    int s1, s2, s3;
    cin >> s1 >> s2 >> s3;

    // 和的范围：最小 1+1+1 = 3，最大 20+20+40 = 80  ->  数组开到 85
    int cnt[85] = {0};

    // 三重循环枚举所有点数组合，把每个和丢进对应的桶
    for(int a = 1; a <= s1; a++)
        for(int b = 1; b <= s2; b++)
            for(int c = 1; c <= s3; c++)
                cnt[a + b + c]++;       // ★ 和是多少，就加在哪个桶

    int bestCount = 0, bestSum = 0;
    for(int s = 3; s <= 80; s++){       // 从小到大扫描
        if(cnt[s] > bestCount){         // ★ 用 > 而不是 >=
            bestCount = cnt[s];         //   并列时保留先遇到的（最小的和）
            bestSum = s;
        }
    }
    cout << bestSum << endl;
    return 0;
}

易错点

• 桶开太小：只开 20 会越界。记住 S₃ 上限是 40，最大和 80。
• 把 > 写成 >=：会输出最大的和而不是最小的。
• 三重循环的边界是 <= s1 不是 < s1——骰子面数是包含 Sᵢ 的。

题意：有一个 w×x×h 的实心玻璃立方体，由一个个 1×1×1 的小方块拼成，小方块用坐标 (i, j, k) 表示。 现在做 q 次切割，每次给出长方体空洞的两个对角点，落在里面的小方块会被激光蒸发。 问全部切完之后还剩多少个小方块。

思路

别去想「体积怎么减」这种数学做法——切割可能互相重叠，减法很容易算错。

换个角度：给每个小方块插一面小旗子，被切到的就插上旗。最后数一遍「没插旗的有几个」。 重叠多少次都无所谓，因为插第二次旗跟第一次没区别（true 还是 true）。

这就是 Day 6 学过的「标记桶」思想，只不过坐标从 1 个变成了 3 个。

• 开 bool cut[25][25][25]，全部默认 false（放全局就自动是 false）。
• 每次切割，用三层循环把 [x₁,x₂]×[y₁,y₂]×[z₁,z₂] 里的所有格子标成 true。
• 最后用三层循环数一遍 !cut[i][j][k] 的个数。

4 4 4
1
1 1 1 2 2 2

56

4×4×4 = 64 个小方块。切掉的是 i∈[1,2]、j∈[1,2]、k∈[1,2]，也就是 2×2×2 = 8 个。
64 − 8 = 56。

完整代码

#include <iostream>
using namespace std;

// 三维标记数组：cut[i][j][k] = true 表示小方块 (i,j,k) 被激光蒸发了
bool cut[25][25][25];

int main(){
    int w, x, h, q;
    cin >> w >> x >> h;          // 长 宽 高
    cin >> q;                    // 切割次数

    for(int t = 0; t < q; t++){
        int x1, y1, z1, x2, y2, z2;
        cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
        // 把长方体里每一个小方块都打上「已蒸发」的标记
        for(int i = x1; i <= x2; i++)
            for(int j = y1; j <= y2; j++)
                for(int k = z1; k <= z2; k++)   // ★ 三个上界分别是 x2 / y2 / z2
                    cut[i][j][k] = true;
    }

    int ans = 0;
    for(int i = 1; i <= w; i++)
        for(int j = 1; j <= x; j++)
            for(int k = 1; k <= h; k++)
                if(!cut[i][j][k]) ans++;   // 没被标记的才剩下

    cout << ans << endl;
    return 0;
}

易错点

• 三个循环的上界别写混。切割时上界是 x2, y2, z2，统计时上界才是 w, x, h。
• 变量名有坑。题目第一行是 w x h，但后面给的 6 个参数是按 (x₁,y₁,z₁),(x₂,y₂,z₂) 说的。 也就是说第二维（对应 w 的那个 x 上限）在切割参数里叫 y，读题时把对应关系写在纸上最保险。
• 别用「总体积减每次切掉的体积」——两次切割可能重叠，重复的部分会被减两次，答案偏小。
• 数组开 [25][25][25] 就够（上限 20），多开一点不心疼。

题意：每个阿拉伯数字都可以显示成 3×5 的点阵（X 是亮点，. 是暗点）。 给一个数字位数 n 和一串数字，把它们在显示屏上的效果打印出来，相邻两个数字之间要空一列。

思路：先打表，再按行拼

这题没有「算法」，考的是把一个大输出拆成规则的小块的能力。三步走：

1. 打表：把 0~9 的点阵写死成一个表。这里用 string pat[10][5]， 也就是「10 个数字 × 每个 5 行 × 每行 3 个字符」的二维字符串数组。
2. 一行一行地输出：最外层循环 r 从 0 到 4，代表 5 行。
3. 每行里按顺序拼接每个数字：内层循环 i 从 0 到 n−1， 输出 pat[数字][r]；不是第一个数字时，先输出一个 . 当间隔列。

0~9 的点阵表（对照样例抄下来最稳）

10
0123456789

XXX...X.XXX.XXX.X.X.XXX.XXX.XXX.XXX.XXX
X.X...X...X...X.X.X.X...X.....X.X.X.X.X
X.X...X.XXX.XXX.XXX.XXX.XXX...X.XXX.XXX
X.X...X.X.....X...X...X.X.X...X.X.X...X
XXX...X.XXX.XXX...X.XXX.XXX...X.XXX.XXX

完整代码

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

// 打表：pat[d][r] = 数字 d 的第 r 行（0 <= d <= 9, 0 <= r <= 4）
string pat[10][5] = {
    {"XXX", "X.X", "X.X", "X.X", "XXX"},   // 0
    {"..X", "..X", "..X", "..X", "..X"},   // 1
    {"XXX", "..X", "XXX", "X..", "XXX"},   // 2
    {"XXX", "..X", "XXX", "..X", "XXX"},   // 3
    {"X.X", "X.X", "XXX", "..X", "..X"},   // 4
    {"XXX", "X..", "XXX", "..X", "XXX"},   // 5
    {"XXX", "X..", "XXX", "X.X", "XXX"},   // 6
    {"XXX", "..X", "..X", "..X", "..X"},   // 7
    {"XXX", "X.X", "XXX", "X.X", "XXX"},   // 8
    {"XXX", "X.X", "XXX", "..X", "XXX"}    // 9
};

int main(){
    int n;
    string s;
    cin >> n >> s;                 // ★ 用 string 读，前导 0 不会丢

    for(int r = 0; r < 5; r++){    // 一行一行地输出
        for(int i = 0; i < (int)s.size(); i++){
            if(i) cout << ".";                     // 数字之间一列间隔
            cout << pat[s[i] - '0'][r];            // 查表
        }
        cout << endl;
    }
    return 0;
}

易错点

• 用 int 读那串数字 → 前导 0 丢掉，位数也可能超出 int 范围。必须用 string。
• 间隔列漏了或多打了。每行长度应该是 3n + (n−1)。可以用 if(i) cout << "."; 来避免行首/行末多一个点。
• 循环顺序写成「先按数字、再按行」 → 输出会变成一个数字挤在一起，不是横排。必须是外层行、内层数字。
• 点阵表是「背下来或者对着样例抄」，抄错一个 X 就是 WA。写完把样例跑一遍最保险。

题意：给一个不大于 9 的正整数 n，输出 n×n 的蛇形方阵： 从左上角填 1 开始，顺时针一圈一圈往里填，直到填满 n²。 每个数字占 3 个字符，不够的前面补空格。

思路：当前方向 + 撞墙就右转

新手最容易想到的做法是「写四个阶段：先往右走 n 格，再往下走 n−1 格，再往左走 n−1 格……」—— 能写出来，但层数一多，边界就要调半天，非常容易错一位。

更稳的写法是状态机，三步就能说清：

1. 站在 (0, 0)，方向 d = 0（朝右）。
2. 循环 v 从 1 到 n²：先在当前格子填 v，然后试着往 d 方向走一步。
3. 如果下一步出界或者已经填过数，就 d = (d+1) % 4（右转），再走。

这样每一圈都不用单独写，程序会自己绕进去。

走一遍 n = 4 的过程

结果就是下面这张方阵：

红色是第二圈（内层）的数字。

4

  1  2  3  4
 12 13 14  5
 11 16 15  6
 10  9  8  7

注意每行开头：第 1 行前面有 2 个空格（因为 1 是个位数），第 2~4 行前面只有 1 个空格。 这就是 %3d 的效果——右对齐，宽度 3。

完整代码

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

int a[15][15];                       // 蛇形方阵，0 表示还没填

// 方向数组：0 右、1 下、2 左、3 上（顺时针）
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

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

    int x = 0, y = 0, d = 0;         // 从 (0,0) 出发，朝右
    for(int v = 1; v <= n * n; v++){
        a[x][y] = v;                 // ★ 先填当前格，再考虑往哪走
        int nx = x + dx[d], ny = y + dy[d];
        // 撞墙（出界）或者撞到已填过的格子，就右转
        if(nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] != 0){
            d = (d + 1) % 4;         // ★ 右转
            nx = x + dx[d];
            ny = y + dy[d];
        }
        x = nx;
        y = ny;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            printf("%3d", a[i][j]);  // ★ 每个数字占 3 个字符，右对齐
        printf("\n");
    }
    return 0;
}

易错点

• 「先填再走」写反了 → 最后一格跑到方阵外面或者被覆盖，WA。
• 只判断出界，忘了判断「已经填过」 → 内圈会一直转圈覆盖已有的数字（会死循环或者填错）。两个条件必须都要有。
• 输出宽度写成 %3d 但其实要求不同：这题就是一个数字 3 格、无额外空格。 别自己脑补成「数字之间再加空格」。
• 方阵数组的初始化：全局数组默认是 0，刚好能用来表示「没填过」。如果写成局部数组记得初始化。
• 方向数组的顺序：必须是「右 下 左 上」才是顺时针。写成「上 右 下 左」就变成从中间开始了。

题意：给出 n（1 ≤ n ≤ 20），输出杨辉三角的前 n 行。 每行相邻两个数之间空一格，行末不要多空格。

思路：每个数 = 上一行「左上 + 正上」

看样例的规律：

1
1 1
1 2 1        // 2 = 上一行的 1 + 1
1 3 3 1      // 3 = 上一行的 1 + 2（第一个 3），另一个 3 = 2 + 1
1 4 6 4 1    // 6 = 上一行的 3 + 3
1 5 10 10 5 1

换成下标写法（行、列都从 1 开始数）：

位置上长什么样

看第 5 行第 3 列的 6：左上 a[4][2] = 3，正上 a[4][3] = 3，3 + 3 = 6 ✔

6

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

完整代码

#include <iostream>
using namespace std;

int a[25][25];                       // a[i][j] 存第 i 行第 j 个数（从 1 开始）

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

    for(int i = 1; i <= n; i++){
        a[i][1] = 1;                 // 每行第一个是 1
        a[i][i] = 1;                 // 每行最后一个是 1
        for(int j = 2; j < i; j++)
            a[i][j] = a[i-1][j-1] + a[i-1][j];   // ★ 左上 + 正上
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            if(j > 1) cout << " ";   // ★ 数字之间一个空格，行末不留空格
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

易错点

• 忘了给两端赋 1 → 整张表全是 0 或者乱掉。
• 行末多一个空格 → 有些评测机判 WA。用 if(j > 1) 控制。
• 数组开小了：行、列都从 1 用到 n，所以至少要开 [n+1][n+1]。开 25 就够用，别开 [20][20]。
• 递推公式记反：是 a[i-1][j-1] + a[i-1][j]，不是 a[i-1][j] + a[i-1][j+1]。记不住就对着样例第 5 行的 6 推一遍。
• 这题是「用上一行算这一行」的典型，也叫递推。Day 17 会专门学递推，今天的杨辉三角就是它的热身。

题意：给一个作文标题，问标题里有多少个字符。 标题里可能有大小写字母、数字、空格和换行符，但统计时空格和换行符不算。

思路

这题只有一句话的思路：用 getline 把整行读进来（这样空格才不会丢），然后数一数有几个字符不是空格。

为什么不能用 cin >> s？因为 cin >> 一遇到空格就停。 样例 2 是 Ca 45，用 cin >> 只能读到 Ca， 答案会算成 2 而不是 4。这就是今天第 2 节那个坑的正确用法：需要空格 → 用 getline。

那「换行符不算」怎么处理？很简单：getline 读出来的字符串里本来就不包含换行符， 它把换行符当结束标志吃掉了。所以我们只要排除空格就行。

234

3

Ca 45

4

样例 2 的说明里写得很清楚：有 1 个大写字母、1 个小写字母、2 个数字字符，还有 1 个空格。 空格不算，所以是 4。

完整代码

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

int main(){
    string s;
    getline(cin, s);                 // ★ 读入一整行，空格也会被读进来

    int ans = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] != ' ') ans++;       // ★ 空格不算，其余字符都算
    }
    cout << ans << endl;
    return 0;
}

易错点

• 用 cin >> s → 空格后面的内容全丢，样例 2 会输出 2。
• 把空格也数进去 → 样例 2 会输出 5。题目明确说空格不算。
• 只读一个字符（用 cin >> c）→ 标题不止一个字符，直接错。
• 多读一行：这题只有一行输入。如果写 while(getline(cin, s)) 累加， 在洛谷上其实也能过，但没必要，而且如果行末有多余空行就会出错。
• 如果前面有 cin >> 读数字，记得先 cin.ignore()（这题没有，但要养成条件反射）。

题意：办公软件会自动把字母变成大写。输入一个字符串， 把里面所有小写字母变成大写字母，其余字符原样输出。

思路

遍历字符串的每一个字符：如果是小写字母，就把它换成对应的大写字母；其他字符（数字、标点）一律不动。

样例给的是 Luogu4!，里面有数字 4 和感叹号 !， 输出 LUOGU4! 说明这两者必须原样保留。 所以不能无脑对所有字符做加法——数字 '4' 加 32 会变成 'T'，那就错了。

Luogu4!

LUOGU4!

完整代码

#include <iostream>
#include <string>
#include <cctype>                    // islower / toupper 都在这里
using namespace std;

int main(){
    string s;
    cin >> s;                        // 题目保证没有空格，用 cin 读最省事

    for(int i = 0; i < (int)s.size(); i++){
        if(islower(s[i]))            // ★ 是小写字母才转换
            s[i] = toupper(s[i]);
    }

    cout << s << endl;
    return 0;
}

for(char &c : s) c = toupper(c);   // 注意 &，否则改的是副本

易错点

• 对所有字符无脑 - 32 → 数字和标点会被改坏。必须先判断是不是小写字母。
• 用范围 for 但忘了 & → for(char c : s) c = toupper(c); 改的是副本， 输出还是原来的小写，看起来「代码没错但答案不对」。
• 忘了 #include <cctype> → 编译报错说找不到 islower。
• 这题没有空格，cin >> s 就够。但如果题目改成「可能含空格」， 就必须换成 getline，而且输出也不能用 cout << s 就完事（其实可以，只是读入要改）。

题意：密码是把原文字符串里每个字母往后移动 n 位得到的， 并且 z 的下一个字母是 a（绕回去）。 给原文和 n，求密码。

思路

核心就是第 5 节那个「绕圈」公式。为什么不能直接 s[i] + n？

所以必须先把字母换算成 0~25 的编号，加完偏移后对 26 取余， 再换算回字母。这样 'z'（编号 25）加 1 变成 26，26 % 26 = 0，回到 'a'。

顺带说一句：因为 'a' 的编号是 97，你可以直接拿字母本身来取模—— 但那样写出来的数字是 97、98 之类的，别人看不懂，自己过两天也看不懂。 减掉 'a' 让编号从 0 开始，代码才读得懂。

1
qwe

rxf

q→r、w→x、e→f，每个都往后一位。

完整代码

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

int main(){
    int n;
    string s;
    cin >> n >> s;                   // n 是数字，s 是字母串（无空格）

    for(int i = 0; i < (int)s.size(); i++){
        // ★ 先转成 0~25，加 n 后对 26 取模，再转回字母
        s[i] = 'a' + (s[i] - 'a' + n) % 26;
    }

    cout << s << endl;
    return 0;
}

易错点

• 直接 s[i] += n → z 之后的字母会跑到 { | } 这些符号上去，WA。
• 取模位置写错：必须是 (c - 'a' + n) % 26，不能是 (c - 'a') % 26 + n。
• 用 char 存中间结果时溢出：如果先 char t = s[i] + n;， n 大时可能超出 char 范围。直接在 int 里算完再赋回 s[i] 最安全（上面的写法就是这样）。
• 读入顺序：n 在第一行、字符串在第二行，用 cin >> n >> s 一次读完最简洁。 如果非要混用 getline，别忘了 cin.ignore()。
• 如果 n 的下限可能是 0 或者负数（本题不是），记得先 n = (n % 26 + 26) % 26; 规范化。

题意：老式手机键盘上，要按出字母得按数字键好几下 （比如按出 x 要按 9 键两下：第一下出 w，第二下变成 x）。 0 键按一下出一个空格。给一句只含小写字母和空格的句子， 问在手机上打出来至少要按多少下。

思路：先造一张「按键次数表」

题目给了键盘的排列方式（原题配了图）。老式手机的规律是：

用样例验算一遍

输入是 i have a dream：

加起来正好 23，和样例输出一致。

i have a dream

23

完整代码

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

// press[c - 'a'] = 按出字母 c 需要按几下
// 按键分组：2:abc  3:def  4:ghi  5:jkl  6:mno  7:pqrs  8:tuv  9:wxyz
int press[26] = {
    1, 2, 3,        // a b c
    1, 2, 3,        // d e f
    1, 2, 3,        // g h i
    1, 2, 3,        // j k l
    1, 2, 3,        // m n o
    1, 2, 3, 4,     // p q r s  ← 4 个字母，别漏了最后的 4
    1, 2, 3,        // t u v
    1, 2, 3, 4      // w x y z  ← 同上
};

int main(){
    string s;
    getline(cin, s);                 // ★ 句子里有空格，必须 getline

    int ans = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] == ' ') ans += 1;    // ★ 空格按 0 键，算一下
        else ans += press[s[i] - 'a'];
    }

    cout << ans << endl;
    return 0;
}

易错点

• 用 cin >> s 读 → 只读到第一个空格为止，后面的内容全丢，答案会小很多。
• 忘了给空格计数 → 样例会输出 19 而不是 23。
• 打表抄错：7 键（pqrs）和 9 键（wxyz）是 4 个字母， 写成 1,2,3 就少一截，z 查表还会读到数组外面去。
• 数组长度写 25 → 'z' - 'a' = 25 直接越界。必须有 26 个元素（下标 0~25）。
• 句子里只有小写字母和空格，所以 else 分支不用再判别的字符类型。如果题目放宽到含大写字母， 就得先 tolower 再查表。

题意：给一个整数 N（可能是负数），把它的各位数字顺序倒过来组成新数。 新数必须是「正常的整数写法」：除非原数就是 0，否则反转后最高位不能是 0 —— 说白了就是要把末尾的 0 丢掉。

思路

三步走，正好对应第 2 节的三个细节：

① 摘符号：用 bool neg 记住是不是负数，然后把 n 取绝对值变成正数。
② 反转：rev = rev * 10 + n % 10; n /= 10; 循环到 n == 0。 这个写法会自动丢掉末尾的 0（前导 0 被 0 * 10 吃掉）。
③ 补符号：如果原来是负数，把 rev 取负再输出。

123

321

-380

-83

样例 2 的 -380 里，那个 0 就是「反转后变成前导 0」的那个 0 —— 必须丢掉，所以是 -83 而不是 -083。

完整代码

#include <iostream>
using namespace std;

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

    bool neg = (n < 0);       // 先记住符号，把负数变成正数再处理
    if(neg) n = -n;

    long long rev = 0;
    while(n > 0){
        rev = rev * 10 + n % 10;   // 取末位，接到新数的末尾
        n /= 10;                   // 丢掉末位
    }

    if(neg) rev = -rev;
    cout << rev << endl;
    return 0;
}

易错点

• 忘了负号：直接把负数丢进 while，n % 10 会出负数，结果一团乱。一定要先摘符号。
• 以为要手动删前导 0：不用！rev * 10 + 0 在 rev 还是 0 的时候等于 0，前导 0 自动没了。 如果你自己再写一段去零代码，反而容易写错。
• 用 string 反转也行（reverse + 去前导 0），但那样要处理负号字符，比算术法麻烦。这题用算术法最省事。
• 输出别忘换行 —— 这题的输出只有一行，但习惯上还是 cout << rev << endl;。

题意：还是数字反转，但这次的「数」有四种长相：整数、小数、分数、百分数。 规则是：每种格式的各个数字块内部各自反转，格式符号（小数点、斜杠、百分号）的位置完全不动。

思路

① 读成字符串，然后看它里面有什么符号，分成四类：

末尾是 '%'      → 百分数
其中有 '.'      → 小数
其中有 '/'      → 分数
都没有          → 整数

注意判断顺序：先判 %，因为百分数里只会出现 %，不会同时出现别的符号。 然后判 . 和 /（题面保证不会同时出现）。

② 写两个去零函数。这是本题最容易出错的地方：

· 整数部分反转后可能带前导 0（600 → 006 → 要变成 6）→ 用 stripLeft
· 小数部分反转后可能带末尾 0（084 → 480 → 要变成 48）→ 用 stripRight

方向是反的！记混了这题就全错。为什么方向不同？因为小数点前是「整数」，整数不能有前导 0； 小数点后是「小数」，小数不能有多余的末尾 0 —— 它们各自遵守自己那一侧的书写规范。

③ 每种情况拼回去：

注意分数和百分数的两段都用 revInt（去前导 0），只有小数的后半段用 revDec（去末尾 0）。 因为题目说「分数与整数翻转相关规定见上」「百分数见与整数翻转相关内容」—— 也就是说它们都按整数规矩来。

5087462

2647805

600.084

6.48

700/27

7/72

8670%

768%

完整代码

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

// 去掉前导 0；如果全是 0，就保留一个 "0"
string stripLeft(string s){
    int i = 0;
    while(i < (int)s.size() - 1 && s[i] == '0') i++;
    return s.substr(i);
}

// 去掉末尾 0；如果全是 0，就保留一个 "0"
string stripRight(string s){
    int j = (int)s.size() - 1;
    while(j > 0 && s[j] == '0') j--;
    return s.substr(0, j + 1);
}

// 整数部分的反转：整体反转 + 去掉前导 0
string revInt(string s){
    reverse(s.begin(), s.end());
    return stripLeft(s);
}

// 小数部分的反转：整体反转 + 去掉末尾 0
string revDec(string s){
    reverse(s.begin(), s.end());
    return stripRight(s);
}

int main(){
    string s;
    cin >> s;
    int n = s.size();

    if(s[n - 1] == '%'){
        // 百分数：只反转数字部分，% 留在最后
        cout << revInt(s.substr(0, n - 1)) << "%" << endl;
    }
    else if(s.find('.') != string::npos){
        // 小数：整数部分、小数部分各自反转，小数点不动
        int p = s.find('.');
        cout << revInt(s.substr(0, p)) << "."
             << revDec(s.substr(p + 1)) << endl;
    }
    else if(s.find('/') != string::npos){
        // 分数：分子、分母各自反转，斜杠不动
        int p = s.find('/');
        cout << revInt(s.substr(0, p)) << "/"
             << revInt(s.substr(p + 1)) << endl;
    }
    else{
        // 整数
        cout << revInt(s) << endl;
    }
    return 0;
}

易错点

• 用 long long 读输入 → 20 位整数直接溢出。必须当字符串读。
• 两个去零函数用反了：小数部分用 stripLeft 会把 .0987654321 变成 .987654321，错。 记住口诀：点前点后都反转，点前去头、点后去尾。
• 把去零函数写成能删空：while(s[i]=='0') i++; 遇到 "0" 会返回空串。 必须加 i < size()-1 的保护。
• 判断顺序：百分号要最先判（用 s[n-1] == '%'），否则可能被别的分支抢走。
• 以为分数要「约分」：题面明说「分数不约分」，1200/30 就是 21/3，不要自作聪明化简成 7/1。
• 以为要交换分子分母：题面明说「不交换」——分子还是分子，只是内部反转。

题意：把彗星名和小组名各转换成一个数字：每个字母按 A=1、B=2 …… Z=26 换成分值，然后全部乘起来。 如果两个数字除以 47 的余数相同，输出 GO，否则输出 STAY。

思路

① 字母 → 分值：s[i] - 'A' + 1。因为 'A' - 'A' = 0，加 1 就是 1；'Z' - 'A' = 25，加 1 就是 26。✅

② 边乘边取模：

res = res * (s[i] - 'A' + 1) % 47;

③ 比一下余数，相等输出 GO，不等输出 STAY。

COMETQ
HVNGAT

GO

ABSTAR
USACO

STAY

样例 1 手算核对：COMETQ = 3×15×13×5×20×17 = 994500，994500 mod 47 = 27； HVNGAT = 8×22×14×7×1×20 = 344960，344960 mod 47 = 27。相等 → GO ✅
样例 2：ABSTAR = 13680，13680 mod 47 = 3；USACO = 17955，17955 mod 47 = 1。不相等 → STAY ✅

完整代码

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

// 把一个名字转换成数字：所有字母的积，A=1, Z=26
// 边乘边取模，避免数字变大（取模可以和乘法交换顺序）
int nameToNumber(string s){
    int res = 1;
    for(int i = 0; i < (int)s.size(); i++){
        res = res * (s[i] - 'A' + 1) % 47;
    }
    return res;
}

int main(){
    string comet, group;
    cin >> comet >> group;          // 第 1 行彗星名，第 2 行小组名

    if(nameToNumber(comet) == nameToNumber(group))
        cout << "GO" << endl;
    else
        cout << "STAY" << endl;

    return 0;
}

易错点

• 写成 s[i] - 'A'：这样 A 会变成 0，整串乘积变成 0，全错。别忘了 + 1。
• 写成 s[i] - 'a' + 1：输入是大写字母，用小写公式会得到负数（'A'-'a' = -32）。看准大小写。
• 忘记 res 要初始化为 1：乘积的初始值必须是 1，写成 0 的话结果永远是 0。
• 输出的是 GO / STAY 全大写，不是 Go、go。输出字符串要一个字母一个字母对着题面抄。
• 本题名字顺序是「先彗星、后小组」，但因为两边都要算、只比余数，谁先谁后不影响结果。读的时候按输入顺序读就行。

题意：给一个 M 进制（1 < M < 10）的数 N， 把它按「十进制展开式」的样子打印出来：每位的数字 × M 的该位次幂，系数为 0 的项要省略，项与项之间用 + 连接。

注意：题目只要打印这个式子，不要你真的算出十进制结果，也不要输出等号。

思路

① 用 string 存 N，因为可能有 1000 位。

② 从左往右扫每一位，设字符串长度为 len，下标为 i（从 0 开始），那么这一位的幂次是：

幂次 = len - 1 - i

比如 "10101" 长度 5：下标 0 是最高位，幂次 4；下标 4 是最低位，幂次 0。✅

③ 系数是 0 就跳过：if(n[i] == '0') continue;。题目明确说「当系数为 0 时，该单项式要省略」。

④ 处理加号：用一个 bool first 标记。是第一个要输出的项，前面不加 +；否则先输出一个 +。

以样例 2 10101 为例，走一遍：

2 10101

1*2^4+1*2^2+1*2^0

完整代码

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

int main(){
    int m;              // 进制
    string n;           // 位数可能到 1000 位，必须用字符串存
    cin >> m >> n;

    int len = n.size();
    bool first = true;  // 是不是第一个要输出的单项式

    for(int i = 0; i < len; i++){
        if(n[i] == '0') continue;      // 系数为 0，整项省略
        if(!first) cout << "+";        // 不是第一项，前面补一个加号
        first = false;
        cout << n[i] << "*" << m << "^" << (len - 1 - i);
    }

    if(first) cout << 0;   // 保险：万一这个数全是 0（题面数据不会出现）
    cout << endl;
    return 0;
}

易错点

• 把 N 读成整数：最多 1000 位，读进去就废了。必须 string n。
• 幂次算错：是 len - 1 - i，不是 i，也不是 len - i。 最高位是 len-1 次，最低位是 0 次 —— 一定要在心里验算一个 5 位的例子。
• 加号加在项后面 → 末尾多一个 +。要用 first 标记，加号加在项前面。
• 系数为 0 的项还输出 → 多出 0*2^3 这种，格式错。题面明确要求省略。
• 最后一行的换行：题目说「共一行」，加个 endl 结尾最稳妥。

题意：给出平面上不共线的三个点的坐标（实数），求这三点围成的三角形的周长，保留两位小数。

思路

这题是「把公式封装成函数」的教科书例子。三点围成的三角形，三条边正好是 AB、BC、CA：

周长 = dist(A,B) + dist(B,C) + dist(C,A)

写一个 dist(x1, y1, x2, y2) 求两点距离，然后调用三次 —— 这就是函数最大的价值：公式只写一遍，用几次调几次。

输入是三行、每行两个数，但 cin 会自动跳过所有空白（空格、换行都算空白）， 所以直接 cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; 一次读完就行，完全不用管它在哪一行换行。

0 0
0 3
4 0

12.00

手算核对：(0,0)-(0,3) 长度 3；(0,3)-(4,0) 长度 √(16+9) = 5；(4,0)-(0,0) 长度 4。3+5+4 = 12 → 12.00 ✅

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

// 求两点之间的距离（今天的主角：把公式封装成函数）
double dist(double x1, double y1, double x2, double y2){
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

int main(){
    double x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    double ans = dist(x1, y1, x2, y2)
               + dist(x2, y2, x3, y3)
               + dist(x3, y3, x1, y1);

    printf("%.2f\n", ans);     // 保留两位小数
    return 0;
}

易错点

• 用 int 读坐标：输入 0.5 这种小数会被读成 0，直接错。坐标是实数就必须 double。
• 用 float：精度只有 7 位左右，本题数据小，勉强能过，但没必要冒这个险 —— 竞赛里小数一律 double。
• 写成 (x2-x1)^2：C++ 里 ^ 是异或，不是乘方！必须老老实实写成 (x2-x1)*(x2-x1)，或者用 pow(x2-x1, 2)（不推荐，慢且返回 double）。
• 忘写 #include <cmath>：sqrt 找不到。用 printf 则要 <cstdio>。
• 输出用 cout << ans：会打出 12 或 12.0000000 这样的一串，不是两位小数。要么 printf("%.2f")，要么 cout << fixed << setprecision(2)（后者要 <iomanip>）。

题意：读入 n 个正整数，把其中的合数和 1 全部筛掉，按原顺序输出剩下的素数，用空格隔开。

思路

① 先把 n 个数读进数组（题目明确要求用数组存）。

② 写 isPrime 函数，即第 4 节的模板一：小于 2 直接否掉，然后从 2 试到 √n。

③ 遍历数组，是素数就输出，注意用 first 标记控制空格，避免行尾多一个空格。

5
3 4 5 6 7

3 5 7

完整代码

#include <iostream>
using namespace std;

// 判断一个数是不是质数
bool isPrime(int n){
    if(n < 2) return false;                     // 0 和 1 都不是质数
    for(int i = 2; (long long)i * i <= n; i++){ // 只需试到 sqrt(n)
        if(n % i == 0) return false;
    }
    return true;
}

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

    int a[105];
    for(int i = 0; i < n; i++) cin >> a[i];      // 题目要求先全部存进数组

    bool first = true;
    for(int i = 0; i < n; i++){
        if(isPrime(a[i])){
            if(!first) cout << " ";              // 不是第一个才补空格
            first = false;
            cout << a[i];
        }
    }
    cout << endl;
    return 0;
}

易错点

• isPrime 忘了 n < 2 的特判：那么 1 会被判成素数输出 —— 而本题的 a_i 正好可以等于 1。
• 循环写成 i <= n：会慢到 10⁵ 次，而且逻辑上也多余（试到 √n 就够）。
• 循环写成 i < n / 2：虽然结果对，但没必要试那么多。用 i * i <= n 最省事。
• 行尾多一个空格：某些评测会比较严格。用 first 标记，或写 if(i != 0) cout << " ";。
• 数组开太小：n ≤ 100，开 a[105] 够了，但别开 a[100]（下标只到 99）。

题意：输入 x 和 y，第一行输出 [x, y] 区间里闰年的个数，第二行按从小到大输出所有闰年年份，空格隔开。

思路

① 先把 isLeap(y) 函数写好（模板二：400 → 100 → 4 的顺序判断）。

② 数个数：从 x 到 y 走一遍，是闰年就 cnt++，先输出 cnt。

③ 再输出年份：从 x 到 y 再走一遍（或者把两步合并），是闰年就输出 + 空格处理。

两次循环其实可以合成一次，但这里分两步写更清楚：题目要求先给出总数，再列出明细， 分两步正好对应题目的输出顺序，不容易乱。

1989 2001

3
1992 1996 2000

手算核对：1989~2001 之间能被 4 整除的有 1992、1996、2000。 其中 2000 是世纪年，但能被 400 整除，所以是闰年 ✅（如果是 1900，就要被剔掉）

完整代码

#include <iostream>
using namespace std;

// 判断闰年：能被 4 整除但不能被 100 整除，或者能被 400 整除
bool isLeap(int y){
    if(y % 400 == 0) return true;
    if(y % 100 == 0) return false;
    return y % 4 == 0;
}

int main(){
    int x, y;
    cin >> x >> y;

    int cnt = 0;
    for(int i = x; i <= y; i++)
        if(isLeap(i)) cnt++;
    cout << cnt << endl;

    bool first = true;
    for(int i = x; i <= y; i++){
        if(isLeap(i)){
            if(!first) cout << " ";
            first = false;
            cout << i;
        }
    }
    cout << endl;
    return 0;
}

易错点

• 漏掉 400 的规则：写成 y % 4 == 0 && y % 100 != 0 就完了，2000 会被漏掉，样例直接挂。
• 判断顺序反了：先判 100 再判 400，2000 会被 100 那条规则提前否掉。必须先 400。
• 循环边界写成 i < y：区间是闭区间 [x, y]，要用 i <= y，否则会漏掉 y 这一年。
• 行尾多空格：同样用 first 标记处理。
• 忘了先输出个数：题目要两行输出，顺序不能反。

题意：输入一个偶数 N，把 4 到 N 之间的每一个偶数都写成「两个质数之和」， 每行一个，形如 10=3+7。如果一个偶数有多种拆法，输出第一个加数最小的那一种。

题面举的例子很关键：10 = 3+7 = 5+5，必须输出 10=3+7（3 比 5 小），写 10=5+5 判错。

思路

① 先用埃氏筛把 2~N 的质数全部标记出来。

埃氏筛的思路特别朴素：从 2 开始，把每个质数的倍数全部划掉。 2 是质数 → 划掉 4、6、8……；3 是质数 → 划掉 9、12、15……；下一个没被划掉的就是质数，继续划……

for(int i = 2; i * i <= N; i++)
    if(isPrime[i])                       // i 本身没被划掉 → i 是质数
        for(int j = i * i; j <= N; j += i)
            isPrime[j] = false;          // 把 i 的倍数全部划掉

② 对每个偶数 n，从小到大试 a：

for(int a = 2; a <= n / 2; a++){
    if(isPrime[a] && isPrime[n - a]){
        cout << n << "=" << a << "+" << n - a << endl;
        break;                       // ★ 找到第一个就停，这才保证 a 最小
    }
}

③ 外层循环从 4 开始，每次 +2，对应题目要求的那 (N−2)/2 个偶数。

10

4=2+2
6=3+3
8=3+5
10=3+7

4 = 2+2；6 = 3+3；8 = 3+5（8 还能拆成 5+3，但 3 更小）；10 = 3+7（不是 5+5）—— 正是题目要求的「第一个加数最小」。

完整代码

#include <iostream>
using namespace std;

// 埃氏筛：把 2~N 里所有质数标记出来，放在 main 外面（全局数组自动清零）
bool isPrime[10005];

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

    for(int i = 2; i <= N; i++) isPrime[i] = true;          // 先假设都是质数
    for(int i = 2; i * i <= N; i++){
        if(isPrime[i]){                                     // i 是质数
            for(int j = i * i; j <= N; j += i)
                isPrime[j] = false;                         // i 的倍数全部划掉
        }
    }

    for(int n = 4; n <= N; n += 2){          // 从 4 开始，每个偶数都要验证
        for(int a = 2; a <= n / 2; a++){     // a 从小到大试，第一个成功的 a 最小
            if(isPrime[a] && isPrime[n - a]){
                cout << n << "=" << a << "+" << n - a << endl;
                break;                       // 找到一个就够，换下一个偶数
            }
        }
    }
    return 0;
}

易错点

• 找到一对就继续试别的 a：忘了 break，会输出多行、或者把最后的 a 打印出来（那就成了「第一个加数最大」）。必须 break。
• 素组数组开小了：N 最大 10000，开 bool isPrime[10005] 刚好够；开 isPrime[10000] 会越界。
• 外层循环写成 n <= N; n++：会输出奇数行（3=…、5=… 这些偶数才需要验证）。要写 n += 2。
• 内层从 a = 1 开始：1 不是质数，虽然 isPrime[1] 是 false 不会出错，但从 2 开始更清楚。
• 全局数组忘了初始化为 true：这是我代码里唯一「要手动做」的初始化 —— 全局数组默认全是 false（=「还不是质数」）， 所以要先 for(i = 2; i <= N; i++) isPrime[i] = true; 把 2~N 假设成质数，再筛。
• 把筛法写成对每个偶数都重新判断质数：那样虽然 N ≤ 10000 也能过，但复杂度差一个量级。 「一次预处理、多次查询」是今天最值得带走的思维方式。

题意：给出 N 个同学的姓名和三科成绩，找出总分最高的那位， 输出他的姓名和原始三科成绩（注意：不是输出总分，是输出原始的三科分数）。 如果有多个人总分并列最高，输出输入靠前的那位。

思路

这题是结构体的「Hello World」，用打擂台的思路就够了，不需要真的排序：

1. 把 N 个同学读进结构体数组，顺手算出每个人的 total。
2. 假设第 0 个同学最厉害（best = 0）。
3. 从第 1 个开始逐个挑战擂主：只要我的总分严格大于擂主，我就当新擂主。
4. 输出擂主的姓名和三科成绩。

「并列时输出靠前的」怎么实现？关键在第 3 步的「严格大于」—— 用 > 而不是 >=。总分相等时擂台不换人，自然就保留了靠前的那位。

3
senpai 114 51 4
lxl 114 10 23
fafa 51 42 60

senpai 114 51 4

三个人总分：senpai = 114+51+4 = 169，lxl = 114+10+23 = 147，fafa = 51+42+60 = 153。最高的是 senpai。

完整代码

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

// 结构体：把「一个同学的全部信息」打包成一个整体
struct Student {
    string name;                    // 姓名
    int chinese, math, english;     // 三科成绩
    int total;                      // 派生字段：总分（读入之后算出来）
} a[1005];                          // 结构体数组：一次声明 1005 个同学

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        // 结构体数组的输入：a[i] 是一个整体，用 a[i].字段 逐个点名
        cin >> a[i].name >> a[i].chinese >> a[i].math >> a[i].english;
        a[i].total = a[i].chinese + a[i].math + a[i].english;
    }

    int best = 0;                   // best 记住「目前最厉害的同学」的下标
    for(int i = 1; i < n; i++){
        if(a[i].total > a[best].total){   // ★ 用 > 不用 >=：并列时保留靠前的
            best = i;
        }
    }

    cout << a[best].name << " " << a[best].chinese << " "
         << a[best].math << " " << a[best].english << endl;
    return 0;
}

易错点

• 输出的是三科原始成绩，不是总分！题目说「输出最厉害的学生各项信息（姓名、各科成绩）」， 很多人顺手把 total 输出了，直接 0 分。
• 比较用了 >=：并列时后面的会顶掉前面的，违反了「输出靠前的那位」。
• 结构体定义末尾的 }; 分号忘了写。
• 姓名是 string，要用 #include <string>（虽然很多编译器不写也能过， 但规范起见写上）。

题意：n 个学生，每人有语文、数学、英语三科成绩。按下面的规则排出一个唯一确定的名次，然后输出前 5 名的学号和总分。

排序规则：① 总分从高到低；② 总分相同时语文从高到低；③ 总分和语文都相同时学号小的在前。

思路

这是结构体 + 多关键字排序的标准题。

1. 读入时把学号也存进结构体（a[i].id = i;）——排序会把顺序打乱，学号必须跟着人走。
2. 顺手算总分。
3. 写三行 cmp，把三个优先级依次排好。
4. sort 之后，前 5 个就是获奖的同学，输出 id 和 total。

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

6 265
4 264
3 258
2 244
1 237

手算验证：1 号 237、2 号 244、3 号 258、4 号 264、5 号 220、6 号 265。按总分降序正好是 6、4、3、2、1。

完整代码

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

struct Student {
    int id;                         // 学号
    int chinese, math, english;     // 三科成绩
    int total;                      // 总分
} a[305];

// 比较函数：返回 true 表示 x 应该排在 y 前面
bool cmp(const Student &x, const Student &y){
    if(x.total != y.total) return x.total > y.total;         // ① 总分高的在前
    if(x.chinese != y.chinese) return x.chinese > y.chinese;  // ② 语文高的在前
    return x.id < y.id;                                      // ③ 学号小的在前
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        a[i].id = i;                                    // ★ 学号 = 输入行号，必须存下来
        cin >> a[i].chinese >> a[i].math >> a[i].english;
        a[i].total = a[i].chinese + a[i].math + a[i].english;
    }

    // 注意：数据存在 a[1] ~ a[n]，所以是 sort(a+1, a+n+1, cmp)
    sort(a + 1, a + n + 1, cmp);

    for(int i = 1; i <= 5; i++){
        cout << a[i].id << " " << a[i].total << endl;
    }
    return 0;
}

易错点

• 三个关键字的顺序写反。优先级是总分 → 语文 → 学号，一层一层往下筛。
• 把 if(x.total != y.total) 写成 if(x.total > y.total)， 会让总分相等的人错误地按学号重排。
• 忘记存学号，排序后完全不知道输出谁。
• sort 右端点漏了 +1，最后一个学生没排序。
• 输出只有 5 行，别写成 n 行。

题意：给出 n 个人的姓名、出生年、月、日，按年龄从大到小输出姓名。 如果两个人年龄相同（年月日完全一样），输入靠后的同学先输出。

思路

先想清楚一件事：「年龄大」等价于「出生日期早」。所以「年龄从大到小」就是「出生日期从小到大」。

日期怎么比大小？就是看日历的习惯：先比年，年相同再比月，月相同再比日。 这正好又是三段式 cmp：

先比 y（早的在前）→ 再比 m（早的在前）→ 再比 d（早的在前）

3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1

Luowen
Yangchu
Qiujingya

Luowen 1991 年最早 → 年龄最大 → 排第一；Qiujingya 1993 年最晚 → 最小 → 排最后。

完整代码

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

struct Person {
    string name;        // 姓名
    int y, m, d;        // 出生年、月、日
    int id;             // 输入顺序（第几个读进来的）
} a[105];

// 比较函数：返回 true 表示 x 应该排在 y 前面（年龄大的在前）
bool cmp(const Person &x, const Person &y){
    if(x.y != y.y) return x.y < y.y;    // 出生年份小 → 年龄大 → 排前面
    if(x.m != y.m) return x.m < y.m;    // 同年再比月
    if(x.d != y.d) return x.d < y.d;    // 同月再比日
    return x.id > y.id;                 // ★ 生日完全相同：输入靠后的先输出
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        a[i].id = i;
        cin >> a[i].name >> a[i].y >> a[i].m >> a[i].d;
    }

    sort(a + 1, a + n + 1, cmp);

    for(int i = 1; i <= n; i++){
        cout << a[i].name << endl;
    }
    return 0;
}

易错点

• 把日期当成一个整数比（比如 y*10000+m*100+d）——这题碰巧也能过， 但更清楚的写法就是三段 if，可读性高得多。
• 年月日的比较方向搞反。题目要「年龄大在前」=「出生早在前」= x.y < y.y， 不是 >。写下 cmp 之前先在纸上念一遍题目要求。
• 并列时用 x.id < y.id：那会变成「输入靠前的先输出」，跟题目要求正好相反。
• 姓名是 string 不是 char，输出时直接 cout << a[i].name。

题意：有 N 个标了三维坐标 (x, y, z) 的点，所有点的高度 z 互不相同。 要从最低的点爬到最高的点，经过每一个点，而且每走一步高度都必须上升。 一步的距离是两点的三维欧几里得距离，求总距离（保留三位小数）。

思路

这题的巧妙之处在「把三维问题变成一维排序问题」。

题目的约束是「每一步高度 z 都必须上升」，而且「经过每一个点」。 那么攀爬路径其实已经被唯一确定了——就是把所有点按 z 从小到大排一排，依次走过去。

排完序，从 p[0] 顺着算到 p[n-1]，把相邻两点的三维距离加起来就行。

三维距离公式

平面上两点距离你会了：√((x₂-x₁)² + (y₂-y₁)²)。三维就是再多加一项 z：

√( (x₂-x₁)² + (y₂-y₁)² + (z₂-z₁)² )

平方差了再开根，用 sqrt()（需要 #include <cmath>）。

5
2 2 2
1 1 1
4 4 4
3 3 3
5 5 5

6.928

按 z 排序后是 (1,1,1) (2,2,2) (3,3,3) (4,4,4) (5,5,5)， 每相邻两点的距离都是 √(1+1+1) = √3 ≈ 1.7320508，四段共 ≈ 6.9282 → 保留三位小数 6.928。

完整代码

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

struct Point {
    int x, y, z;        // 三维坐标
} p[50005];

// 按高度 z 从小到大排，就得到了攀爬的先后顺序
bool cmp(const Point &a, const Point &b){
    return a.z < b.z;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
    }

    sort(p, p + n, cmp);            // 排序之后，p[0] 最低，p[n-1] 最高

    double ans = 0.0;
    for(int i = 1; i < n; i++){
        // 三维欧几里得距离：先算差值再平方，最后开根号
        double dx = p[i].x - p[i-1].x;
        double dy = p[i].y - p[i-1].y;
        double dz = p[i].z - p[i-1].z;
        ans += sqrt(dx * dx + dy * dy + dz * dz);
    }

    printf("%.3f\n", ans);          // 保留三位小数
    return 0;
}

易错点

• 用 int 算平方和：(p[i].x-p[i-1].x) 的平方可能超出 int 范围。 先赋给 double 变量再平方，或者写 (double) 强转。
• 忘了 #include <cmath>：sqrt 找不到。
• 输出格式：题目要求保留 3 位小数，cout << ans 会打出 6.9282 这种一堆位数，直接 WA。
• 数组开小了：N ≤ 50000，开 p[50005]，别开成 1005。
• 不要试图去找「最短路径」——路径是被题目条件唯一确定的，只需要排序 + 累加。

题意：明明生成了 N 个 1 到 1000 之间的随机整数，其中重复的只保留一个。 要求先输出去重后有多少个不同的数（M），再把这些数从小到大排好序输出。

思路

题目要求的是「去重 + 排序」两件事，而这两件事有天然的联系：排完序之后，相同的数一定挨在一起， 于是「去重」就退化成了「删掉相邻的重复项」。

两种写法：

1. 通用写法：sort 排序 → unique 去重相邻重复项 → 得到新的长度 m。
2. 桶写法：开一个 vis[1005]，读到哪个数就给哪个桶插旗； 最后从 1 扫到 1000，有旗子的数字天然就是升序且不重复的。

10
20 40 32 67 40 20 89 300 400 15

8
15 20 32 40 67 89 300 400

10 个数里 20 和 40 各出现了两次，去重后剩 8 个。

完整代码（写法一：sort + unique）

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

int a[105];

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

    sort(a, a + n);                         // ① 排序

    // ② 去重：unique 把不重复的元素挪到前面，返回「新区间末尾」的指针
    int m = unique(a, a + n) - a;

    cout << m << endl;                      // ③ 先输出去重后的个数
    for(int i = 0; i < m; i++){
        if(i) cout << " ";                  // 数字之间一个空格，末尾不多打
        cout << a[i];
    }
    cout << endl;
    return 0;
}

完整代码（写法二：标记桶）

#include <iostream>
using namespace std;

int a[105];
bool vis[1005];     // 桶：vis[v] 标记数字 v 出现过

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        vis[a[i]] = true;       // 出现过的数，在它自己的桶里插一面旗
    }

    int m = 0;
    for(int v = 1; v <= 1000; v++){
        if(vis[v]) m++;         // 从小到大扫桶，顺便数出有多少个不同的数
    }

    cout << m << endl;
    int printed = 0;
    for(int v = 1; v <= 1000; v++){
        if(vis[v]){
            if(printed) cout << " ";
            cout << v;
            printed++;
        }
    }
    cout << endl;
    return 0;
}

8
15 20 32 40 67 89 300 400

易错点

• 先 unique 再 sort：unique 只删相邻重复项，没排序时重复的数不挨着，一个也删不掉。顺序不能反。
• 忘了输出 M：题目要输出两行，第一行是不同数的个数，很容易只输出排序结果。
• 输出末尾多打空格：洛谷一般能容忍行末空格，但用 if(i) cout << " "; 的写法更规范。
• 桶写法里桶的大小要开到 1000 以上（数值上限 1000，所以 vis[1005]）， 开成 vis[1000] 在读入 1000 时会越界。

题意：给出 n 个正整数，把它们首尾相接拼成一排，组成一个最大的整数，输出这个整数。

思路：这题的关键是「两个数谁该排前面」

先说一个错误但非常诱人的想法：把数字当字符串，按字典序从大到小排，然后拼起来。

它对样例居然是对的！但它是错的。看这个反例：

（上面两组我都真的编译运行验证过：我的正确程序输出 331 和 991； 专门写了一个「字典序降序」的错误版本，输出的正是 313 和 919。）

如果 a + b > b + a，那么 a 应该排在 b 前面

为什么这样比是对的

三个理由，说服你自己：

1. a+b 和 b+a 的长度一定相同（都是「a 的长度 + b 的长度」）。 长度相同的字符串比大小，就是纯粹的数值比大小，不用考虑位数问题。这一点非常关键—— 如果长度不同，「位数多的更大」和「字典序更大」就不一定一致了。
2. 它回答的正是题目要问的问题。题目要总长度最大，而在「a 在前」和「b 在前」之间二选一时， 局部最优就是选拼接串更大的那种排法。当这个「两两比较」规则被 sort 全局应用之后，得到的整体拼接串就是最大的。
3. 它满足严格弱序：当 a+b == b+a 时（比如 a=b，或者 {"12","1212"} 这种）， cmp 两边都返回 false，视为「等价」。所以它可以安全地交给 sort。

3
13 312 343

34331213

4
7 13 4 246

7424613

样例 1：343 > 312 > 13（两两拼接比较后），拼成 34331213。
样例 2：顺序是 7、4、246、13 → 拼成 7424613。

完整代码

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

string s[25];

// ★ 核心比较规则：如果 a 接在 b 前面比 b 接在 a 前面更大，a 就排在前面
bool cmp(const string &a, const string &b){
    return a + b > b + a;
}

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

    sort(s, s + n, cmp);

    for(int i = 0; i < n; i++) cout << s[i];
    cout << endl;
    return 0;
}

读入直接读成 string，不做任何转换——因为最后要的就是拼接出来的字符串， 中间用不用 int 根本没意义，而且 int 也存不下 10 位数拼起来的结果。

易错点

• 用 int / long long 去拼：20 个数各 10 位，拼起来最多 200 位， 什么整数类型都存不下，必须用 string。
• cmp 写成 a > b（字典序降序）：样例能过，隐藏数据必挂，见上面的反例。
• cmp 写成 a + b >= b + a：多了个等号，破坏严格弱序，属于未定义行为， 可能崩也可能排错。必须用严格的 >。
• cmp 里反复做字符串拼接在数据量大时会有开销，但本题 n ≤ 20，完全无所谓。
• 输出是一个整数（没有空格、没有换行分组），别在中间加空格——加了就变成另一个东西了。

题意：n 个候选人，每人有一个票数，票数可能非常大（最多 100 位）。 输出票数最多的那个人的号数（第几行输入的），再输出他的票数。保证没有并列。

思路：大数比大小，两步走

实现上用「打擂台」比排序更简单，毕竟 n 只有 20：

1. 读第一个候选人，把他当擂主（记住他的字符串和号数）。
2. 后面每个人来挑战：先比长度，长度相同再比字典序，赢了就换擂主。
3. 最后输出擂主的号数和票数。

5
98765
12365
87954
1022356
985678

4
1022356

5 个票数里，1022356 是唯一一个 7 位数，其他都是 5 位或 6 位数，所以位数最多的一定最大 → 第 4 个人当选。这题样例本身就体现了「先比长度」的重要性：985678（6 位）比 98765（5 位）大， 但比 1022356（7 位）小。

完整代码

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

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

    string best = "";       // 目前票数最多的那个数
    int bestId = 0;         // 它的号数

    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;

        bool better = false;
        if(bestId == 0){
            better = true;                                  // 第一个候选人，直接当擂主
        }else if(s.size() != best.size()){
            better = (s.size() > best.size());              // ① 位数多的数一定更大
        }else{
            better = (s > best);                            // ② 位数相同，用字典序比
        }

        if(better){
            best = s;
            bestId = i;
        }
    }

    cout << bestId << endl;
    cout << best << endl;
    return 0;
}

易错点

• 用 long long 读票数：100 位数字直接溢出，读进来就是垃圾值。必须用 string。
• 只按字典序比、忘了先比长度："9" 会被判为大于 "10"，答案就错了。
• 把号数搞成 0-based：输出要求的是「第一个候选人到第 n 个候选人」，第一行是 1 不是 0。
• 并列怎么办：题面保证不存在票数相同的候选人，所以不用处理。 如果真遇到，用严格大于（better 只在严格更大时为 true）就会保留靠前的那位。

题意：一条桥最多容纳两节车厢，转 180 度就能交换相邻两节车厢。 要用这个操作把车厢按编号从小到大排好，问最少要转多少次。

思路：把「旋转」翻译成「相邻交换」

题目绕了一大圈，本质就是一句：你有一个操作，可以交换数组里相邻的两个元素，问最少几次能让数组升序。

而「最少次数」这个问题的答案非常干净：

所以这题的代码骨架就是「冒泡排序 + 一个计数器」。N ≤ 1000 时 O(N²) 是 10⁶ 次操作，轻松通过。

4
4 3 2 1

6

4 3 2 1 的逆序对：(4,3)(4,2)(4,1)(3,2)(3,1)(2,1)，共 6 对 → 需要 6 次旋转。也可以手数：第一轮 3 次交换、第二轮 2 次、第三轮 1 次，3+2+1 = 6。

完整代码（冒泡，最简单）

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

int a[1005];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];   // cin 自动跳过换行，分行输入也不怕

    int cnt = 0;
    // 冒泡排序：每一轮把当前最大的车厢「冒」到最右边
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - 1 - i; j++){
            if(a[j] > a[j+1]){          // 相邻两节逆序，必须旋转一次
                swap(a[j], a[j+1]);
                cnt++;                  // 每交换一次记一步
            }
        }
    }

    cout << cnt << endl;
    return 0;
}

进阶版：归并排序数逆序对（O(N log N)）

如果 N 变成 10⁵，冒泡的 O(N²) 就超时了。这时用归并排序，在合并两段的时候顺手把逆序对统计出来：

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

int a[1005], tmp[1005];
long long cnt = 0;          // 逆序对个数

// 归并排序：顺便统计跨越左右两半的逆序对
void mergeSort(int l, int r){
    if(l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]){
            tmp[k++] = a[i++];
        }else{
            tmp[k++] = a[j++];
            cnt += (mid - i + 1);   // 左半段剩下的 i..mid 全都比 a[j] 大
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r)   tmp[k++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = tmp[t];
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    mergeSort(0, n - 1);
    cout << cnt << endl;
    return 0;
}

易错点

• 用 getline 读数据：题面明说数据可能分行，分行读会把一行当成一整份，直接错。 用 cin >> 或 scanf 逐个读数字最稳。
• 把 1005 写成 1000：N 最大 1000，数组至少要 a[1001]，开 a[1005] 更保险。
• 以为要「排序后输出」：题目只要输出次数，不要输出排好序的车厢序列。
• 内层循环边界写成 j < n - 1 而不是 j < n - 1 - i： 多跑一些不影响正确性（只是慢一点），但内层访问到 a[n] 就越界了，必须带 - i。
• 以为「最少」是随便走走看运气：这题答案是确定的（逆序对数），不需要搜索。

题意：n 个人排队接水，第 i 个人要接 Tᵢ 分钟。一个人的等待时间不算自己接水的时间。 要你排出一种顺序，让所有人的平均等待时间最小，并输出这个顺序和平均等待时间（保留两位小数）。 如果两个人的接水时间相同，编号更小的排前面。

思路

贪心策略：接水时间短的先上。

为什么？一个人接水的时候，他后面所有人都在等他。所以一个人接水时间越长， 他被「算进别人的等待时间」里的次数就越多。

换句话说是这样：排在第 i 位的人（从 1 数），他的接水时间会被后面 n − i 个人各等一次。 所以他对总等待时间的贡献是 Tᵢ × (n − i)。

乘数 (n − i) 在队伍前面很大、后面很小。要让总和最小， 就应该让大的 Tᵢ 配上小的乘数 —— 也就是让接水慢的人排到后面去。

10
56 12 1 99 1000 234 33 55 99 812

3 2 7 8 1 4 9 6 10 5
291.90

第一行输出的是人的编号（不是时间）。按时间升序排：1 (3号) → 12 (2号) → 33 (7号) → 55 (8号) → 56 (1号) → 99 (4号) → 99 (9号) → 234 (6号) → 812 (10号) → 1000 (5号)。
注意两个 99：4 号在 9 号前面，因为 4 号编号更小 —— 这就是「时间相同按编号」的体现。

完整代码

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Person {
    int id;   // 原来的编号（1 开始）
    int t;    // 接水时间
};

Person a[1005];

// 排序规则：接水时间小的排前面；时间相同时编号小的排前面
bool cmp(const Person &p, const Person &q){
    if(p.t != q.t) return p.t < q.t;
    return p.id < q.id;                 // ★ 时间相同按编号升序，不能漏
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        a[i].id = i;
        cin >> a[i].t;
    }
    sort(a + 1, a + n + 1, cmp);        // 下标从 1 开始，所以是 a+1 到 a+n+1

    long long total = 0;                // ★ 总等待时间最大约 5×10^11，必须 long long
    for(int i = 1; i <= n; i++){
        // 排在第 i 位的人接水时，后面 n-i 个人都在等他
        total += 1LL * a[i].t * (n - i); // ★ 1LL 先转 long long，再乘，防止中途溢出
    }

    for(int i = 1; i <= n; i++){
        if(i > 1) cout << " ";
        cout << a[i].id;
    }
    cout << "\n";
    // ★ 先转 double 再除，否则会做整数除法，小数部分直接没了
    cout << fixed << setprecision(2) << (double)total / n << "\n";
    return 0;
}

易错点

• 不用 long long：总等待时间能到 5×10¹¹，int 存不下，会输出负数或者莫名其妙的数。
• 乘法写成 a[i].t * (n - i)：两边都是 int，会先按 int 算完再赋给 long long，中间就已经溢出了。
  必须写 1LL * a[i].t * (n - i)，让编译器一开始就按 64 位算。
• 平均值写成 total / n：这是整数除法，2919 / 10 会得到 291 而不是 291.9。
  要写 (double)total / n，并且加上 fixed << setprecision(2) 才会输出两位小数。
• 输出的是编号不是时间：第一行要输出 3 2 7 8 …（人的编号），把接水时间输出出去就废了。
• 时间相同时忘了按编号升序：样例里两个 99 就是专门用来考这个的，顺序错了会 WA。
• 数组下标从 1 开始却只开了 1000：题目 n 最大 1000，需要用到 a[1000]，所以至少开 1001，本文开 1005 留余量。

题意：有一堆纪念品，每件有个价格。要把它们分组发下去，规则是： 每组最多 2 件，而且每组两件的价格之和不能超过 w。问最少要分多少组。

思路

贪心策略：先排序，然后每次拿「现在最重的」去试试能不能和「现在最轻的」凑一组。

能凑上就两个一起走；凑不上就说明最重的那件跟谁配都超标，只能自己占一组。

为什么这样贪是对的

用交换论证，重点想清楚一件事：最重的那件纪念品怎么办最划算？

设现在最重的是 r，最轻的是 l。假设 P_l + P_r ≤ w（它俩能配）。

100
9
90
20
20
30
50
60
70
80
90

6

排序后：20 20 30 50 60 70 80 90 90。配对过程：
90 配 20 → 110 超标，90 单独一组；
90 配 20 → 同样超标，90 单独一组；
80 配 20 → 100 ✅ 一组；70 配 20 → 90 ✅ 一组；60 配 30 → 90 ✅ 一组；50 剩自己 → 一组。
一共 6 组。

完整代码

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

int p[30005];

int main(){
    int w, n;
    cin >> w;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> p[i];

    sort(p, p + n);              // 从小到大排序，双指针才好用

    int l = 0, r = n - 1, ans = 0;
    while(l <= r){               // ★ 用 <= 而不是 < ，否则中间剩一个会被漏掉
        if(l == r){
            ans++;               // ★ 只剩一件，自己一组
            break;
        }
        if(p[l] + p[r] <= w){
            // 最轻的能配上最重的，就让它们一组（这样最重的不会浪费）
            l++;
            r--;
            ans++;
        } else {
            // 最重的配谁都超重（连最轻的都配不上），只能自己一组
            r--;
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

易错点

• 循环写成 while(l < r)：中间剩下的单独一件会被漏掉，答案偏小。
• 忘记 l == r 的特判：会变成「自己和自己配对」。
• 贪心策略选错：比如「贵的配贵的」（第 2 节的反例 A 就是它），或者「轻的配轻的」——都会错。
• 输入格式：w 在第一行、n 在第二行，然后 n 行每行一个价格。不要连续读成「一行两个数」，虽然用 cin >> 读其实都能过，但要看清题面。
• 以为一件纪念品可能超过 w：题目保证了 Pᵢ ≤ w，所以不用写「放不下就输出无解」那种逻辑。

题意：你和一堆石头，第 i 块高 hᵢ，地面高度 h₀ = 0。 从高度 x 跳到高度 y 消耗体力 (x − y)²。你必须把每块石头都跳一遍，最后停在哪块都行 （但不能跳回地面）。问：最多能消耗多少体力？

思路

这题要的是最大体力，而体力是「高度差的平方」。平方这个东西有个特点：

贪心策略：

1. 把高度从小到大排好序。
2. 从地面（高度 0）出发，先跳到最高的那块石头。
3. 然后跳到最矮的那块。
4. 再跳到第二高的，再跳到第二矮的……像拉锯齿一样在两端之间来回横跳。

为什么每步都跳到两端之一？因为排好序之后，离当前点最远的那个高度，一定在两端。 既然越远越耗体力，那一端必然是候选。

为什么是「交替」而不是「一直跳最高」？因为你不能跳回地面，也不能重复跳同一块石头。 跳到最高处之后再想跳远，就只能去最矮处；到了最矮处再想跳远，就只能回高处 —— 自然就形成了交替。

2
2 1

5

3
6 3 5

49

样例 1：地面 → 2（耗 2²=4）→ 1（耗 (2−1)²=1），共 5。
样例 2：排序后是 3 5 6。地面 → 6（耗 36）→ 3（耗 (6−3)²=9）→ 5（耗 (5−3)²=4），共 49。

完整代码

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

int h[305];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);          // 从小到大排好，方便从两端交替取

    long long ans = 0;       // ★ 答案能到 3×10^10，必须 long long
    int l = 0, r = n - 1;
    long long cur = 0;       // 当前位置的高度，一开始站在地上 h0 = 0
    bool takeRight = true;   // 先跳最高的

    while(l <= r){
        long long nxt;
        if(takeRight){
            nxt = h[r];      // 拿当前最高的
            r--;
        } else {
            nxt = h[l];      // 拿当前最矮的
            l++;
        }
        ans += (nxt - cur) * (nxt - cur);   // 消耗 (差值)²
        cur = nxt;
        takeRight = !takeRight;             // ★ 下一次换成另一端
    }
    cout << ans << "\n";
    return 0;
}

易错点

• 用 int 存答案：最大能到 3×10¹⁰，必爆。这是本题最容易丢分的地方。
• 算平方时没转 long long：h[r] - h[l] 是 int，两个 int 相乘还是 int。
  本文代码里 nxt 和 cur 都声明成了 long long，所以自动就按 64 位算了。
• 跳跃方向搞反：题目要的是最大体力，不是最小。别习惯性地求最小。
• 忘了从地面出发：第一跳是从高度 0 起跳的，不是从某块石头起跳。cur 的初值必须是 0。
• 最后停在原地不动：题目说得很清楚，必须每块石头都跳到，不能跳过某些石头。所以循环必须在 l <= r 里把每一个都取走。
• 不能跳回地面：所以最后一步一定是停在某块石头上，不能加一步「跳回地面」。

题意：n 个糖果盒排成一排，第 i 盒有 aᵢ 颗糖。每次可以从某一盒里吃掉一颗。 目标是让任意两个相邻盒子的糖果数之和都不超过 x。问最少要吃几颗。

思路

从左往右一盒一盒地看。看第 i−1 盒和第 i 盒的时候，如果它俩的和超了 x， 那多出来的部分必须被吃掉，没得商量（因为只有这两盒能改，前面已经处理完了，不能反悔）。

问题只在于：吃哪一盒？

⚠️ 反例：无脑「只削右边」是错的

计划原文的提示是「一旦相邻两堆之和超过 x 就削掉右边的」。如果真的一行照抄，会挂在这组数据上：

3 2
4 1 3

4

无脑削右边：4 + 1 = 5 > 2，超出 3 颗，从第 2 盒削 3 颗 —— 可第 2 盒只有 1 颗，削完变成 −2，程序算出 3。
正确方案：第 1 盒吃 2 颗（4→2），第 2 盒吃 1 颗（1→0），第 3 盒吃 1 颗（3→2），共 4 颗。

我实际把两种版本都编译运行过：错误的版本在这组数据上输出 3， 暴力枚举版本输出 4。所以这个补丁是必需的，不是可写可不写。

为什么这样贪是对的

每一步我们处理的都是「当前这一对 (i−1, i)」。此时第 i−2 盒及更左边都已经合法了， 后面的盒子还没被这对影响。所以：

• 超出 x 的那部分无论如何都要吃掉（不在这两盒吃，就没别的地方可吃了）。
• 在这两盒里，吃第 i 盒（右边）永远不比吃第 i−1 盒差：因为减少第 i 盒只会让它更小， 待会儿处理 (i, i+1) 时更容易达标；而减少第 i−1 盒对未来的配对毫无帮助。
• 所以「能吃右边就吃右边」是安全的；只有右边不够时，才不得不往左边借。

注意吃左边也不会破坏已经处理好的部分：第 i−1 盒变小， a[i−2] + a[i−1] 只会更小，之前那个约束依然满足。

3 3
2 2 2

1

6 1
1 6 1 2 0 4

11

5 9
3 1 4 1 5

0

样例 1：2+2 = 4 > 3，吃掉 1 颗 → 1。
样例 2：第 2 盒吃 6 颗、第 4 盒吃 2 颗、第 6 盒吃 3 颗，共 11。
样例 3：所有相邻和分别是 4、5、5、6，都不超过 9，一颗都不用吃 → 0。

完整代码

#include <iostream>
using namespace std;

long long a[100005];            // ★ aᵢ 最大 10^9，且相邻和会用到两个数相加

int main(){
    ios::sync_with_stdio(false);    // n 最大 10^5，加快读入
    cin.tie(0);

    int n;
    long long x;
    cin >> n >> x;
    for(int i = 0; i < n; i++) cin >> a[i];

    long long eaten = 0;            // ★ 答案最大 10^14，必须 long long
    for(int i = 1; i < n; i++){
        long long sum = a[i - 1] + a[i];
        if(sum > x){
            // 至少要吃掉这么多颗，才能让 (i-1, i) 这一对和不超标
            long long need = sum - x;
            if(a[i] >= need){
                // 右盒够吃：全从右盒吃（右盒以后还能再削，最划算）
                a[i] -= need;
            } else {
                // ★ 右盒不够吃！先把右盒吃空，剩下不够的从上一盒补
                long long rest = need - a[i];
                a[i] = 0;
                a[i - 1] -= rest;   // rest ≤ a[i-1]，绝不会吃成负数
            }
            eaten += need;
        }
    }
    cout << eaten << "\n";
    return 0;
}

易错点

• 只削右边忘了补锅：右盒不够吃时会吃成负数，答案偏小。这是本题最大的坑。
• 用 int：aᵢ 能到 10⁹，两个相加就 2×10⁹ 已经爆 int；答案能到 10¹⁴，更是必须 long long。
• 从右往左扫：那样会破坏「左边已经处理好、永不回头」的不变量，方向必须是从左到右。
• 忘了 x 可以是 0：x = 0 时每一对相邻和都必须 ≤ 0，因为糖果数非负，所以最终所有盒子都得是 0。
• 以为要排序：这题不能排序！盒子是按位置排的，「相邻」指的是原来的位置关系，排完序就全乱了。