2018年全国多校算法寒假训练营练习比赛（第一场）G 圆圈

链接：https://www.nowcoder.com/acm/contest/67/G
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

    圈圈圆圆圈圈，lulu小朋友最近看喜羊羊看多了，老是受刺激就画圆圈，听到小于8的数字时，还会画出十分有规律的圆圈，现在你需要根据样例观察出规律，编写程序，根据输入的数字n（n<8）,输出对应的圆圈。

输入描述:

第一行是样例数T（T<9）第2到2+T-1行每行有一个整数n（n<8），代表lulu听到的数字

输出描述:

听到对应数字时，输出对应样子的圆圈。

示例1

输入

14
20
31
42
53

输出

1O
2 O
3O O
4 O
5    O
6   O O
7    O
8 O     O
9O O   O O
10 O     O
11    O
12   O O
13    O
14             O
15            O O
16             O
17          O     O
18         O O   O O
19          O     O
20             O
21            O O
22             O
23    O                 O
24   O O               O O
25    O                 O
26 O     O           O     O
27O O   O O         O O   O O
28 O     O           O     O
29    O                 O
30   O O               O O
31    O                 O
32             O
33            O O
34             O
35          O     O
36         O O   O O
37          O     O
38             O
39            O O
40             O

说明

当n=0时输出O当n=1时输出*OO*O*O当n=2时输出****O***O*O****O*O*****OO*O***O*O*O*****O****O***O*O****O上面的'O'是大写英文字母O，'*'代表空格，每一行最后一个O后面不带空格。

备注:

对于100%的数据，0<T<9;0<=n<8;

做法:

每一块的宽和高可以先算出来

然后递归输出

比如输出一个以 (x,y) 坐标为基准的大小为k的图片

可以由递归地由

(x,y)坐标为基准的大小为k-1的图片

(x+w,y-w)坐标为基准的大小为k-1的图片

(x+w,y+w)坐标为基准的大小为k-1的图片

(x+w*2,y)坐标为基准的大小为k-1的图片 构成

递归构造即可

代码：

1 1 #include<iostream>
2 2 using namespace std;
3 3 #include<cstring>
4 4 #include<cstdlib>
5 5 #include<string>
6 6 int f[10]={0};
7 7 char s[2500][2500];
8 8 int maxh=0;
9 9 void paint(int x,int &w){
1010     if(x<0){
1111         w=0;
1212         return;
1313     }
1414     if(f[x]>0){
1515         w=f[x];
1616         return;
1717     }
1818     if(x==0){
1919         w=1;
2020         return;
2121     }
2222     int ww=0;
2323     paint(x-1,ww);
2424     w=ww*3;
2525     return;
2626 }
2727 int getf(int x){
2828     int w=0;
2929     paint(x,w);
3030     return w;
3131 }
3232 int maxn[2500];
3333 void dfs(int x,int y,int k){
3434     if(k==0){
3535         if(x>maxh)
3636         maxh=x;
3737         if(maxn[x]<y)
3838         maxn[x]=y;
3939         s[x][y]='O';
4040         return;
4141     }
4242     int w=getf(k-1);
4343     dfs(x,y,k-1);
4444     dfs(x+w,y-w,k-1);
4545     dfs(x+w,y+w,k-1);
4646     dfs(x+w*2,y,k-1);
4747 }
4848 int main(){
4949     int t;
5050     scanf("%d",&t);
5151     int n;
5252     for(int i=1;i<=t;i++){
5353         scanf("%d",&n);
5454         int k=getf(n-1);
5555         k=k+getf(n-1)/2+1;
5656         for(int i=0;i<=2499;i++)
5757             maxn[i]=0;
5858         maxh=0;
5959         memset(s,0,sizeof(s));
6060         dfs(1,k,n);
6161         for(int i=1;i<=maxh;i++){
6262             for(int j=1;j<=maxn[i];j++){
6363                 if(s[i][j]==0)
6464                     s[i][j]=' ';
6565                 putchar(s[i][j]);
6666             }
6767             putchar('\n');
6868         }
6969     }
7070     return 0;
7171 }