code

先 po 一下 $\color{red}{\tt\text{code}}$ ：

#include<bits/stdc++.h>
#define _ 0
using namespace std;
char g[20000][20000];
int n;
void print()
{
	for(int i=1;i<=pow(2,n);i++)
	{
		for(int j=1;j<=pow(2,n+1);j++)
			putchar(g[i][j]);
		putchar('\n');
	}
	return;
}
void draw(int x,int y)//打个小表
{
	g[x-1][y+1]='/';
	g[x][y]='/';
	g[x-1][y+2]='\\';
	g[x][y+3]='\\';
	g[x][y+1]='_';
	g[x][y+2]='_';
	return;
}
void clone(int px,int py,int nx,int ny)
{
	for(int i=px;i<=pow(2,n);i++)
		for(int j=1;j<=py;j++)
			g[nx-px+i][ny-py+j]=g[i][j];
	return; 
}
void work(int step)//鬼畜预警！！！
{
	if(step>=n)
		return;
	clone(pow(2,n)-pow(2,step)+1,pow(2,step+1),pow(2,n)-pow(2,step+1)+1,3*pow(2,step));//在右上角clone。
	clone(pow(2,n)-pow(2,step)+1,pow(2,step+1),pow(2,n)-pow(2,step)+1,pow(2,step+2));//在右边clone。
	work(step+1);//式子自己推
}	
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=pow(2,n);i++)
		for(int j=1;j<=pow(2,n+1);j++)
			g[i][j]=' ';
	draw(pow(2,n),1);
	work(1);
	print();
	return ~~(0^_^0);//嘤嘤嘤
}

思路

简直是个毒瘤题。。。

不过一定不要打表！放弃吧！

#part 1

每个数据一个数字，表示图腾的大小（此大小非彼大小） $n<=10$

“彼大小”是什么？研究数据吧！

#0

1
 /\
/__\

$n=1,\text{底边}=1$ 。

#1

2
   /\
  /__\
 /\  /\
/__\/__\

$n=2,\text{底边}=2$ 。

#2

3
       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

$n=3,\text{底边}=4$ 。

#n

$n=n,\text{底边}=2^{n-1}$ 。

#part 2

确定输出的面积。

由 #1 知，长即 $4(\text{字符数})\times2^{n-1}=2^{n+1}$ 。

类似地，宽即 $2\times2^{n-1}=2^n$ 。

为了便于输出，开一个二维数组存图。

$n<=10$ ，也就是说开 $2^{n+1}\times2^n=2^{10+1}\times2^{10}=2048\times1024$ 大小即可。

#part 3

如何构造图形？

经观察，这些图形都是由一个基本元素图形构成：

 /\
/__\

当 $n=2$ 时：

   /\
  /__\
 /\  /\
/__\/__\  //#2

很明显，由 $3$ 个基本元素组成。

当 $n=3$ 时：

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\  //#3

很明显，由 $3$ 个 #2 图形组成。所以，#n 图形由 $3$ 个 #n-1 图形组成。

end

思路：

先在左下角 draw() 一个基本元素，再在右上角，右边 clone() $2$ 个，再把这个图形 clone() $2$ 个…，clone() $n-1$ 次，即可。

END

彩蛋：“南蛮图腾”其实是谢尔宾斯基三角形！

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/ca2b323e820c/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 递归

最后更新：2023-08-21, 23:18:20

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

P1498 南蛮图腾

code

思路

#part 1

#0

#1

#2

#n

#part 2

#part 3

end

END