企业官网建设流程全解析

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

一道有意思的题目。需要先从前几次折叠中寻找规律，然后做题。

发现每一步都是折叠90度，而且从横向左侧开始。那么每次折叠后会从横变竖，或者从竖变横，且不是顺时针，就是逆时针。那么只要直到每次转动的顺逆时针序列，就能把图画出来。

我的总体步骤如下：
1. 计算出每个折痕的顺逆时针。2. 通过顺逆时针拿到每个点的坐标和横竖。3.在二维数组中画出。

第一步：

首先需要观察前几次折叠的折痕序列，从中寻找规律。这里假设0为顺时针，1为逆时针。

叠一次：1

叠两次：110

叠三次：1101100

叠四次：110110011100100

我们会首先注意到，下一次的折痕个数，是上一次的两倍+1。如果n为折叠次数，对应纸片的数量是2^n。对应折痕个数是2^n - 1。

我们观察到，下一次折痕的序列的前面部分，正好是前一个序列的值。最中间的数正好是1。

在注意到，后面部分也和前一个序列的值非常相似，就是前一个序列的值的最终中间位置反了一下（1变为0，0变为1）。

这些观察到的规律是正确的。这是因为，每次折叠实际上是一个递归行为。

"下一次折痕的序列的前面部分，正好是前一个序列的值"。这是因为，我们对子序列进行折叠的操作，和对上一个序列折叠的操作实际上是一样的，因此对应的折痕序列相同。（试想，你你先把值叠了一下，然后去掉上半部分不要。留下的下半部分和原来的纸是一样的，都是一张横纸。因此对原纸折叠和对下半部分折叠，折痕是一样的）

“最中间的数正好是1”，那是因为是最开始折叠的一次，按照题目是逆时针的。

“后面部分也和前一个序列的值非常相似，就是前一个序列的值的最终中间位置反了一下（1变为0，0变为1”，事实上，它是前一个序列的值反向，然后对所有值取反。为什么？观察折起来之后的纸，头尾是对应的，一致对应到中间，即1对应n，2对应n-1 .... 。而且对应的折痕的角度是反向的。AC代码中也是这么计算的。至于看起来是前一个序列的值的最终中间位置反了一下，这是因为前一个序列本身就有这样的特点，即本身就是递归的反向生成的。

第二步：

有了折痕序列之后，就来生成折痕图序列。为什么不直接放到二维图上？其实是可以的，但是那样后面归一化等操作麻烦，因此先生成序列。生成序列时，根据前一个纸片的位置，本次折叠角度，前一个纸的方向等，可以计算出新一张纸片位置，角度和方向。注意这里case有点多。这里的x和y允许负值。

第三步：

首先对折痕图序列进行处理。主要是做归一化：即最左边，最上面的值，从0，0开始。

然后是去掉输出每行中剩下不需要的空格。（否则会PE）。

最后生成二维图，并输出。

AC代码

#include <stdio.h> #include <string.h> #define MAXN 8195 // 每种折叠次数对应的折痕序列 0 顺时针 1 逆时针 int foldsArr[14][MAXN]; // foldn 现有的折叠次数长度 int n, foldn; // 折痕图序列 x y 0为_ 1为| int figureArr[MAXN][3]; int figureLen; // 折痕图 char figure[MAXN][MAXN]; int maxx, maxy; // 计算折痕序列长度 int getFoldsLen(int a) { return (1 << a) - 1; } // 生成折痕序列 void genFoldArr(int a) { if (a == 1) { foldsArr[1][0] = 1; return; } int i; int alen = getFoldsLen(a); int ailen = getFoldsLen(a - 1); for (i = 0; i < ailen; ++i) { foldsArr[a][i] = foldsArr[a - 1][i]; foldsArr[a][alen - 1 - i] = foldsArr[a - 1][i] == 1 ? 0 : 1; } foldsArr[a][ailen] = 1; } // 调试输出折痕序列 void outFoldArr() { int i, j, jmax; for (i = 1; i < foldn; ++i) { jmax = (1 << i) - 1; printf("%d: ", i); for (j = 0; j < jmax; ++j) printf("%d ", foldsArr[i][j]); printf("\n"); } } // 调试输出折痕图序列 void outFigureArr() { int i; // 折痕序列长度 int len = getFoldsLen(n); for (i = 0; i <= len; ++i) printf("-- %d %d %d\n", figureArr[i][0], figureArr[i][1], figureArr[i][2]); putchar('\n'); } /* StepsX[i][j][k] i=0 _ i=1 | j为折痕的0和1 k=0 往左或者往上 k=1 往右或者往下 StepsX 值为x坐标 StepsY 值为y坐标 StepsD 值为下一步方向，就是k */ int StepsX[2][2][2] = {{{0, -1}, {-1, 0}}, {{1, 0}, {1, 0}}}; int StepsY[2][2][2] = {{{-1, 1}, {-1, 1}}, {{1, -1}, {-1, 1}}}; int StepsD[2][2][2] = {{{0, 1}, {1, 0}}, {{1, 0}, {0, 1}}}; // 生成折痕图序列 void genFigureArr() { int i; // 折痕序列长度 int len = getFoldsLen(n); // 生成折痕图序列 figureArr[0][0] = 0; figureArr[0][1] = 0; figureArr[0][2] = 0; int d = 1; // 方向 for (i = 0; i < len; ++i) { figureArr[i + 1][0] = figureArr[i][0] + StepsX[figureArr[i][2]][foldsArr[n][i]][d]; figureArr[i + 1][1] = figureArr[i][1] + StepsY[figureArr[i][2]][foldsArr[n][i]][d]; figureArr[i + 1][2] = figureArr[i][2] == 1 ? 0 : 1; d = StepsD[figureArr[i][2]][foldsArr[n][i]][d]; } } // 生成折痕图 void genFigure() { int i, j, k; // 折痕图序列长度 int len = getFoldsLen(n) + 1; int minx = figureArr[0][0]; int miny = figureArr[0][1]; maxx = 0; maxy = 0; for (i = 0; i < len; ++i) { if (minx > figureArr[i][0]) minx = figureArr[i][0]; if (miny > figureArr[i][1]) miny = figureArr[i][1]; } for (i = 0; i < len; ++i) { figureArr[i][0] -= minx; figureArr[i][1] -= miny; if (maxx < figureArr[i][0]) maxx = figureArr[i][0]; if (maxy < figureArr[i][1]) maxy = figureArr[i][1]; } memset(figure, 0, sizeof(figure)); for (i = 0; i < len; ++i) figure[figureArr[i][0]][figureArr[i][1]] = figureArr[i][2] == 1 ? '|' : '_'; } // 输出折痕图 void outFigure() { int i, j; // 所有空白转成空格 for (i = 0; i <= maxx; ++i) { for (j = 0; j <= maxy; ++j) figure[i][j] = figure[i][j] ? figure[i][j] : ' '; } // 末尾的空格不要否则PE for (i = 0; i <= maxx; ++i) { for (j = maxy; figure[i][j] == ' '; --j) figure[i][j] = 0; } for (i = maxx; i >= 0; --i) { printf("%s", figure[i]); putchar('\n'); } printf("^\n"); } int main() { int i; foldn = 1; while (scanf("%d", &n) > 0 && n > 0) { if (foldn <= n) { for (i = foldn; i <= n; ++i) genFoldArr(i); foldn = n + 1; } genFigureArr(); genFigure(); outFigure(); } return 0; }