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

输入

输出

O
 O
O O
 O
    O
   O O
    O
 O     O
O O   O O
 O     O
    O
   O O
    O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O
    O                 O
   O O               O O
    O                 O
 O     O           O     O
O O   O O         O O   O O
 O     O           O     O
    O                 O
   O O               O O
    O                 O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             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 #include<iostream>
 2 using namespace std;
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<string>
 6 int f[10]={0};
 7 char s[2500][2500];
 8 int maxh=0;
 9 void paint(int x,int &w){
10     if(x<0){
11         w=0;
12         return;
13     }
14     if(f[x]>0){
15         w=f[x];
16         return;
17     }
18     if(x==0){
19         w=1;
20         return;
21     }
22     int ww=0;
23     paint(x-1,ww);
24     w=ww*3;
25     return;
26 }
27 int getf(int x){
28     int w=0;
29     paint(x,w);
30     return w;
31 }
32 int maxn[2500];
33 void dfs(int x,int y,int k){
34     if(k==0){
35         if(x>maxh)
36         maxh=x;
37         if(maxn[x]<y)
38         maxn[x]=y;
39         s[x][y]='O';
40         return;
41     }
42     int w=getf(k-1);
43     dfs(x,y,k-1);
44     dfs(x+w,y-w,k-1);
45     dfs(x+w,y+w,k-1);
46     dfs(x+w*2,y,k-1);
47 }
48 int main(){
49     int t;
50     scanf("%d",&t);
51     int n;
52     for(int i=1;i<=t;i++){
53         scanf("%d",&n);
54         int k=getf(n-1);
55         k=k+getf(n-1)/2+1;
56         for(int i=0;i<=2499;i++)
57             maxn[i]=0;
58         maxh=0;
59         memset(s,0,sizeof(s));
60         dfs(1,k,n);
61         for(int i=1;i<=maxh;i++){
62             for(int j=1;j<=maxn[i];j++){
63                 if(s[i][j]==0)
64                     s[i][j]=' ';
65                 putchar(s[i][j]);
66             }
67             putchar('\n');
68         }
69     }
70     return 0;
71 }

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