HU-6778 Windows Of CCPC(表を打って再帰する)

20969 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=6708
Time Limit:2000/1000 MS(Java/Others) メモリLimit:65536/65536 K(Java/Others)
Problem Description
In recent years,CCPC has developed rapidly and gained a large number of comppetitors.One contestant designed a design caled CCPC Windows.The 1-st order PC window is show ingthe figre:

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

We can easure find that the window of CCPC of order k is generated by taring the window of CCPC of order k−1 as C of order k,and the relt of inverting C/P in the window of CCPC of order k−1 as P オブライダー 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 LINE contains a positive integers k、(1≦k≦10)
Output
For each test case,you shoult out put the answer.
Sample Input

Sample Output

CC
PC
CCCC
PCPC
PPCC
CPPC
CCCCCCCC
PCPCPCPC
PPCCPPCC
CPPCCPPC
PPPPCCCC
CPCPPCPC
CCPPPPCC
PCCPCPPC

ソurce
2019中国大学生プログラム設計コンテスト(CCPC)-ネット選抜試合

この問題がややこしいのは改行符の処理です.メーターと再帰でできるような気がします.

再帰する
問題解決の考え方:
最初は4文字で、左下は他の3つと違っています.
最初の2つを使って、2つ目を4つの部分に分けて、左下と1つ目の反対、つまりPをCに変えて、CをPにして、残りは同じです.
全部で2^n行を出力します.一行の出力ができます.もし私が8行を出力したいなら、今は1行目を出力します.
では、総出力4行目の1行目は2回出力されます.
左下の角の部分を出力すると、これは総挙動4行の該当行が逆に1回出力され、1回出力されるのと同じです.

 1 #include 
 2 #include <string.h>
 3 #include 
 4 #include <string>
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
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("
");
75         }
76     }
77     return 0;
78 }

STLメーター

 1 #include 
 2 #include <string.h>
 3 #include 
 4 #include <string>
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
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]を前倒しして出力する場合は、2つのfor 1->2^kでいいです.暇があれば試してみてもいいです.

転載先:https://www.cnblogs.com/jiamian/p/11403395.html

pythonはBaiduの贴吧のピクチャーをダウンロードします.

WEB(html天気予報プラグインコード——iframeコントロールの呼び出しで実現