6 块覆盖:边长 2L 的三角形

点右侧公式看它对应的块,或直接点图上的块。拖动滑块改变 L。

角块 1~3 补块 4~6 没盖住
L = 4,2L = 8
L=1L=2L=4L=8

对照源码

main.cpp:50-67,构建一层:6 个 max 就是上面那 6 个坐标
for (int t = 1; t <= lg; t++) {
    int half = 1 << (t - 1);                     // 这一层的块边长
    int quarter = (t >= 2) ? (1 << (t - 2)) : 0;  // 补块偏移;t = 1 时没有补块
    for (int i = 1; i + (1 << t) - 1 <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int best = f[pre][i][j];
            best = max(best, f[pre][i + half][j]);
            best = max(best, f[pre][i + half][j + half]);
            if (t > 1) {
                best = max(best, f[pre][i + half][j + quarter]);
                best = max(best, f[pre][i + quarter][j]);
                best = max(best, f[pre][i + quarter][j + quarter]);
            }
            f[cur][i][j] = best;
        }
    }
    swap(pre, cur);
}
main.cpp:72-87,查询:同一套模板,偏移换成 k - block 和 cha
for (int i = 1; i + k - 1 <= n; i++) {
    int bottom = i + k - 1;
    for (int j = 1; j <= i; j++) {
        int right = j + k - 1;
        int best = f[pre][i][j];
        best = max(best, f[pre][bottom - block + 1][j]);
        best = max(best, f[pre][bottom - block + 1][right - block + 1]);
        if (lg >= 1) {
            int cha = (k - block) / 2;
            best = max(best, f[pre][bottom - block + 1][j + cha]);
            best = max(best, f[pre][i + cha][j]);
            best = max(best, f[pre][i + cha][j + cha]);
        }
        answer += best;
    }
}

验收

① 新例推演:边长 16 的三角形,只放 3 个角块

把滑块拖到 L = 8(边长 16),只点「只看 3 个角块」。空出多少格?

参考答案与思路

28 格。三个角块各边长 8,下面的两个角块在底边上错开 16 - 8 = 8 格,中间留下一块边长 7 的倒三角:7 + 6 + … + 1 = 28。L 越大,这个空洞增长得越快,所以补块不能省。

② 条件解释:补块的偏移为什么是 L/2

块 4 的上顶点是 (i + L/2, j)。如果把偏移改成 L,会发生什么?

参考答案与思路

选第一个。偏移取 L 时块 4 的上顶点就是 (i, j)… 正好和块 1 一模一样,6 个块塌成 3 个,边长 8 的例子会空出 6 格没盖住。偏移必须取半边 L/2,让补块卡进中间那块倒三角。这也是 L 只能取 2 的幂的原因:取奇数时 L/2 不是整数,落不到格子上。

③ 核心代码应用:补全 main.cpp 里的三个下标

下面是构建一层里取 6 个块的那几行,空格处填什么?(用 half、quarter、i、j 组合,例如 i + half)

int best = f[pre][i][j];
best = max(best, f[pre][i + half][j]);
best = max(best, f[pre][i + half][j + ]);
if (t > 1) {
    best = max(best, f[pre][][j + quarter]);
    best = max(best, f[pre][i + quarter][]);
    best = max(best, f[pre][i + quarter][j + quarter]);
}
参考答案与思路

三个空依次是 half、i + half、j。

对着图看坐标:块 6 是 (i + L, j + L/2),块 3 是 (i + L, j + L),块 4 是 (i + L/2, j)。所以第一空是 half,第二空是 i + half,第三空是 j。