HDU-6708 Windows Of CCPC（打表，递归）

http://acm.hdu.edu.cn/showproblem.php?pid=6708

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

In recent years, CCPC has developed rapidly and gained a large number of competitors .One contestant designed a design called CCPC Windows .The 1-st order CCPC window is shown in the figure:

And the 2-nd order CCPC window is shown in the figure:

We can easily find that the window of CCPC of order k is generated by taking the window of CCPC of order k−1 as C of order k,and the result of inverting C/P in the window of CCPC of order k−1 as P of order k.

And now I have an order k ,please output k-order CCPC Windows , The CCPC window of order k is a 2^k∗2^k matrix.

Input

The input file contains T test samples.(1<=T<=10)
The first line of input file is an integer T.
Then the T lines contains a positive integers k , (1≤k≤10)

Output

For each test case,you should output the answer .

Sample Input

Sample Output

CC

PC

CCCC

PCPC

PPCC

CPPC

CCCCCCCC

PCPCPCPC

PPCCPPCC

CPPCCPPC

PPPPCCCC

CPCPPCPC

CCPPPPCC

PCCPCPPC

Source

2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

这题比较麻烦的就是换行符的处理了，感觉可以用打表和递归做

递归

解题思路：

最开始是4个字符左下角那个和其余3个不一样，

用最初的可以拼成第2个，把第2个分成4部分，左下角和第一个相反，也就是P变为C，C变为P，其余相同。

一共要输出2^n行，那么可以一行一行的输出，假设我要输出总行为8行，现在要输出第1行，

那么其实是输出总行为4行的第1行输出两遍，

当输出左下角的部分时，这是总行为4行的相应行相反输出1遍，在输出1遍相同的。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 const int maxn=1e5+;

 using namespace std;

 //ios::sync_with_stdio(false);

 //    cin.tie(NULL);

 //n表示图案一共有n层，row表示目前的层数 ，f表示是正常输出还是反着输出

 void solve(int n,int row,int f)

 {

     if(n==)

     {

         if(f==)

         {

             if(row==)

                 printf("CC");

             else

                 printf("PC");

         }

         else

         {

             if(row==)

                 printf("PP");

             else

                 printf("CP");

         }

         return ;

     }

     int t=row%(n/);//t表示该图案row行是上一阶的多少行

     if(t==)

         t=n/;

     if(f==)

     {

         if(row>n*1.0/)

             solve(n/,t,);

         else

             solve(n/,t,);

         solve(n/,t,);

     }

     else if(f==)

     {

         if(row>n*1.0/)

             solve(n/,t,);

         else

             solve(n/,t,);

         solve(n/,t,);

     }

 }

 int main()

 {

     int n,T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         n=<<n;

         for(int i=;i<=n;i++)

         {

             solve(n,i,);

             printf("\n");

         }

     }

     return ;

 }

STL打表

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <math.h>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 const int mod=1e9+;

 //const double PI=acos(-1);

 const int maxn=1e5+;

 using namespace std;

 //ios::sync_with_stdio(false);

 //    cin.tie(NULL);

 vector<string> vt[];

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie(NULL);  

     vt[].push_back("CC");

     vt[].push_back("PC");

     for (int i = ; i <= ; i++)

     {

         for (vector<string>::iterator it1 = vt[i - ].begin(); it1 != vt[i - ].end(); it1++)

         {

             vt[i].push_back(*it1 + *it1);

         }

         for (vector<string>::iterator it1 = vt[i - ].begin(); it1 != vt[i - ].end(); it1++)

         {

             string s1 = *it1;

             string s2 = "";

             for (string::iterator it2 = s1.begin(); it2 != s1.end(); it2++) {

                 if (*it2 == 'C')

                     s2 += 'P';

                 else

                     s2 += 'C';  

             }

             vt[i].push_back(s2 + *it1);

         }

     }

     int T;

     cin >> T;

     while (T--)

     {

         int i;

         cin >> i;

         for (vector<string>::iterator it1 = vt[i].begin(); it1 != vt[i].end(); it1++)

         {

             cout << *it1 << endl;

         }

     }

     return ;

 }

还可以根据行数找规律

提前打表G[2^10+1][2^10+1]，输出时两个for 1->2^k就行了，有空可以尝试一下

巴特西