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 2k∗2k 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)
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
3 1 2 3
Sample Output
CC
PC
CCCC
PCPC
PPCC
CPPC
CCCCCCCC
PCPCPCPC
PPCCPPCC
CPPCCPPC
PPPPCCCC
CPCPPCPC
CCPPPPCC
PCCPCPPC
Source
这题比较麻烦的就是换行符的处理了，感觉可以用打表和递归做
递归
解题思路：
最开始是4个字符左下角那个和其余3个不一样，
用最初的可以拼成第2个，把第2个分成4部分，左下角和第一个相反，也就是P变为C，C变为P，其余相同。
一共要输出2^n行，那么可以一行一行的输出，假设我要输出总行为8行，现在要输出第1行，
那么其实是输出总行为4行的第1行输出两遍，
当输出左下角的部分时，这是总行为4行的相应行相反输出1遍，在输出1遍相同的。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <map> 11 #include <math.h> 12 const int INF=0x3f3f3f3f; 13 typedef long long LL; 14 const int mod=1e9+7; 15 //const double PI=acos(-1); 16 const int maxn=1e5+10; 17 using namespace std; 18 //ios::sync_with_stdio(false); 19 // cin.tie(NULL); 20 21 //n表示图案一共有n层，row表示目前的层数 ，f表示是正常输出还是反着输出 22 void solve(int n,int row,int f) 23 { 24 if(n==2) 25 { 26 if(f==1) 27 { 28 if(row==1) 29 printf("CC"); 30 else 31 printf("PC"); 32 } 33 else 34 { 35 if(row==1) 36 printf("PP"); 37 else 38 printf("CP"); 39 } 40 return ; 41 } 42 int t=row%(n/2);//t表示该图案row行是上一阶的多少行 43 if(t==0) 44 t=n/2; 45 if(f==1) 46 { 47 if(row>n*1.0/2) 48 solve(n/2,t,0); 49 else 50 solve(n/2,t,1); 51 solve(n/2,t,1); 52 } 53 else if(f==0) 54 { 55 if(row>n*1.0/2) 56 solve(n/2,t,1); 57 else 58 solve(n/2,t,0); 59 solve(n/2,t,0); 60 } 61 } 62 63 int main() 64 { 65 int n,T; 66 scanf("%d",&T); 67 while(T--) 68 { 69 scanf("%d",&n); 70 n=1<<n; 71 for(int i=1;i<=n;i++) 72 { 73 solve(n,i,1); 74 printf("\n"); 75 } 76 } 77 return 0; 78 }
STL打表
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <map> 11 #include <math.h> 12 const int INF=0x3f3f3f3f; 13 typedef long long LL; 14 const int mod=1e9+7; 15 //const double PI=acos(-1); 16 const int maxn=1e5+10; 17 using namespace std; 18 //ios::sync_with_stdio(false); 19 // cin.tie(NULL); 20 21 vector<string> vt[15]; 22 23 int main() 24 { 25 ios::sync_with_stdio(false); 26 cin.tie(NULL); 27 28 vt[1].push_back("CC"); 29 vt[1].push_back("PC"); 30 for (int i = 2; i <= 10; i++) 31 { 32 for (vector<string>::iterator it1 = vt[i - 1].begin(); it1 != vt[i - 1].end(); it1++) 33 { 34 vt[i].push_back(*it1 + *it1); 35 } 36 for (vector<string>::iterator it1 = vt[i - 1].begin(); it1 != vt[i - 1].end(); it1++) 37 { 38 string s1 = *it1; 39 string s2 = ""; 40 for (string::iterator it2 = s1.begin(); it2 != s1.end(); it2++) { 41 if (*it2 == ‘C‘) 42 s2 += ‘P‘; 43 else 44 s2 += ‘C‘; 45 46 } 47 vt[i].push_back(s2 + *it1); 48 } 49 } 50 int T; 51 cin >> T; 52 while (T--) 53 { 54 int i; 55 cin >> i; 56 for (vector<string>::iterator it1 = vt[i].begin(); it1 != vt[i].end(); it1++) 57 { 58 cout << *it1 << endl; 59 } 60 } 61 return 0; 62 }
还可以根据行数找规律
提前打表G[2^10+1][2^10+1]，输出时两个for 1->2^k就行了，有空可以尝试一下