Day 7 · 二维数组 + 第一周复盘

题意：有一个 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 会专门学递推，今天的杨辉三角就是它的热身。