洛谷题单指南-递推与递归-P1498 南蛮图腾

原题链接：https://www.luogu.com.cn/problem/P1498

题意解读：

观察样例，可以发现，当n = 1时，得到最基础的图案：

 /\
/__\

当n = 2时，将基础图案向下复制两个，并排，然后将之前的图案移到居中的位置

   /\
  /__\
 /\  /\
/__\/__\

当n = 3时，再将n = 2时的图案向下复制两个，并排，然后将之前的图片移动居中的位置

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

因此，可以从基础图案出发，按照以上过程，复制n - 1次，即可得到结果。

解题思路：

观察得知，图案的高度为2^n，图案的宽度为2^(n + 1)，n最大是10，因此高度最大1024，宽度最大2048

用一个char tt[2000][3000]足够存储所有的字符

初始时，需要将tt所有元素初始化为空格

再填充上基础图案

每次复制时，先在下方复制两个图案，然后把原图案清空，最后把下方的一个图案复制回原图案的位置，但要能保证居中对齐

具体操作请参考代码注释。

100分代码：

#include <bits/stdc++.h>
using namespace std;

char tt[2000][3000]; //高度最多1024，宽度最多2048
int n;

int main()
{
    cin >> n;

    memset(tt, ' ', sizeof(tt)); //每个字符都初始化为空格

    //初始化n=1的情况
    tt[1][1] = ' ', tt[1][2] = '/', tt[1][3] = '\\', tt[1][4] = ' ';
    tt[2][1] = '/', tt[2][2] = '_', tt[2][3] = '_', tt[2][4] = '\\';

    int h = 2, w = 4; //高度h，宽度w
    for(int i = 1; i < n; i++) //复制n-1次
    {
        for(int j = 1; j <= h; j++) //向下复制2个并排
        {
            for(int k = 1; k <= w; k++)
            {
                tt[j + h][k] = tt[j + h][k + w] = tt[j][k];
                tt[j][k] = ' '; //清空原来的图案
            }
        }

        for(int j = 1; j <= h; j++) //向上复制一个，居中对齐
        {
            for(int k = 1; k <= w; k++)
            {
                tt[j][k + w / 2] = tt[j + h][k];
            }
        }

        h *= 2, w *= 2;
    }

    //输出结果
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++) cout << tt[i][j];
        cout << endl;
    }
    
    return 0;
}