c++课课通9单元第3课课后题第3题折纸

Question

3.折纸。(paper,ls,64MB)[问题描述)
小林喜欢画画。他有一张width xheigh的纸,他在纸上的操作步骤如下:从直线x=xfold对折(是把左边的纸折到右边上面);把纸竖直对折成cnt+1等份,就是把最上面的折到下面,共操作cnt 次。现在小林画一个实心矩形,左下角的坐标是(x1,y1),右上角坐标是(x2,y2)。注意(xl,y1)和(x2,y2)是把纸折完之后的坐标，(0,0)是左下角坐标,小林画的那些格子的墨水都会渗到它对应的下层的那些格子。最后再次展开纸。
例如,如图9.3-3所示,小林有一张5x6的纸,他把直线x=2左边的纸折到右边去,cnt=2,则把纸竖直对折成3份。然后画一个矩形(白色),左下角坐标是(1,1),右上角坐标是(3,2)。再次展开得到最后一张图。现给出纸的width、height、xfold、cnt、x1、y1、x2、y2,请问画完之后,还有多少个格子是没有被渗到颜色的。
[输入格式]
第一行K,表示有K组测试数据,1≤K≤5。
每组测试数据一行,共8个整数:width、height、xfold、cnt、x1、yl、x2、y2。其中:1≤width,height≤10^9,0≤xfold≤width,0≤cnt≤1000,cnt+1能被height 整除,0≤x1<x2≤max(xfold,width-xfold),0≤y1<y2≤height/(cnt+1)。
[输出格式]
输出K行,每行一个整数,表示画完之后还有多少个格子没有被渗到颜色。
[样例输入]
1
5 6 2 2 1 1 3 2
[样例输出]
21

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以采用一种分治的方法。首先，我们将整个问题分解为几个子问题，每个子问题都是在折叠后的纸上寻找未被染色的格子数量。我们可以通过分析矩形和折痕的关系来确定哪些区域可能被染色，然后递归地处理这些子问题。

以下是解决问题的步骤：

1. 分析矩形与折痕的位置关系。
2. 根据折痕位置，将矩形划分为多个部分。
3. 对于每个部分，判断其是否会被染色。
4. 计算未被染色的部分，累加起来作为答案。

这是一个相对复杂的逻辑，我们需要编写一些辅助函数来处理这些问题。下面是C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

// 判断点是否在矩形内
bool isInside(int x, int y, int x1, int y1, int x2, int y2) {
    return (x >= x1 && x <= x2 && y >= y1 && y <= y2);
}

// 计算未被染色的格子数量
int countUnstainedCells(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2) {
    if (cnt == 0) { // 如果没有垂直折痕，只需考虑水平折痕
        if (x1 > xfold) { // 矩形完全在右侧
            return (height - y2 + y1) * (width - x2 + x1);
        } else if (x2 <= xfold) { // 矩形完全在左侧
            return (height - y2 + y1) * (xfold - x1 + x2);
        } else { // 矩形跨越折痕
            return (height - y2 + y1) * ((xfold - x1 + x2) + (width - x2 + x1));
        }
    } else { // 存在垂直折痕
        int verticalDivisions = height / (cnt + 1);

        // 将矩形划分到四个部分，并计算每个部分的未染色格子数
        int totalUnstained = 0;
        for (int i = 0; i <= cnt; ++i) { // 遍历每个垂直部分
            int startY = i * verticalDivisions;
            int endY = (i + 1) * verticalDivisions;

            if (isInside(x1, startY, x1, y1, x2, y2)) { // 上半部分
                totalUnstained += countUnstainedCells(width, verticalDivisions, xfold, cnt - 1, x1, startY, x2, min(endY, y2));
            }

            if (isInside(x1, endY, x1, y1, x2, y2)) { // 下半部分
                totalUnstained += countUnstainedCells(width, verticalDivisions, xfold, cnt - 1, x1, max(startY, y1), x2, y2);
            }

            if (isInside(xfold, startY, x2, y1, x2, y2)) { // 右侧部分
                totalUnstained += countUnstainedCells(width - xfold, verticalDivisions, 0, cnt - 1, 0, startY, x2 - xfold, min(endY, y2));
            }

            if (isInside(xfold, endY, x2, y1, x2, y2)) { // 左侧部分
                totalUnstained += countUnstainedCells(width - xfold, verticalDivisions, 0, cnt - 1, 0, max(startY, y1), x2 - xfold, y2);
            }
        }

        return totalUnstained;
    }
}

int main() {
    int K;
    cin >> K;
    while (K--) {
        int width, height, xfold, cnt, x1, y1, x2, y2;
        cin >> width >> height >> xfold >> cnt >> x1 >> y1 >> x2 >> y2;

        cout << countUnstainedCells(width, height, xfold, cnt, x1, y1, x2, y2) << endl;
    }

    return 0;
}

这个程序会根据给定的参数计算出未被染色的格子数量。你可以复制这段代码到C++编译器中运行并测试样例输入。如果你有任何疑问或需要进一步的帮助，请随时告诉我。