本文主要是介绍洛谷 P1498 南蛮图腾，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
自从到了南蛮之地，孔明不仅把孟获收拾的服服帖帖，而且还发现了不少少数民族的智慧，他发现少数民族的图腾往往有着一种分形的效果，在得到了酋长的传授后，孔明掌握了不少绘图技术，但唯独不会画他们的图腾，于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙，作为一个好孙子的孙子的孙子的孙子……你能做到吗？
输入输出格式
输入格式：
每个数据一个数字，表示图腾的大小（此大小非彼大小） n<=10
输出格式：
这个大小的图腾
输入输出样例
输入样例#1：
2
输出样例#1：
/\/__\/\ /\ /__\/__\
输入样例#2：
3
输出样例#2：
/\/__\/\ /\/__\/__\/\ /\/__\ /__\/\ /\ /\ /\ /__\/__\/__\/__\
解法：分治
第三遍，分治是一个把原问题不断的分解为形式相同规模更小的问题。
这题则很明显是个分治问题
最小的问题是需要画出像这样一个的图形
那么我们只需要把原问题分解为无数个这样小的图形合成即可。
用一个char数组保存每个位置的字符，每次从最左下角的字符进行处理填充完整个图形需要的字符
然后找到下一个需要处理的位置即可。
分治也太神奇了吧。
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;
const int maxn = 2e3 + 10;
char g[maxn][maxn];
void build(int a, int b, int n)
{if(n == 1){g[a][b] = g[a - 1][b + 1] = '/';g[a][b + 1] = g[a][b + 2] = '_';g[a][b + 3] = g[a - 1][b + 2] = '\\';}else{build(a, b, n - 1);//此位置build(a - (1 << (n - 1)), b + (1 << (n - 1)), n - 1);上面1个build(a ,b + (1 << n), n - 1);//右边1个}
}
int main()
{// freopen("/Users/vector/Desktop/testdata.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;int h = 1 << n, w = 1 << (n + 1);//计算出行数和列数for(int i = 1; i <= h; i++)for(int j = 1; j <= w; j++)g[i][j] = ' ';build(h, 1, n);//从左下角开始进行处理for(int i = 1; i <= h; i++,cout << endl)for(int j = 1; j <= w; j++)cout << g[i][j];return 0;
}
这篇关于洛谷 P1498 南蛮图腾的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
