|
|
中間漏了一個題目,極度惡心的 Packing Rectangles.上次做USACO的時候我就是直接跳
過去的,以至于現在我依然保留對它的恐懼.這恐怕很大程度上是心理因素而不是能力問題,但是
我是一個崇尚莊周的人,按照我們以前班主任的說法就是自由主義泛濫,所以我決定順著我的心
意:先跳過去.對我而言 Packing Rectangles 的惡心程度可以跟后面的PRIME3相匹敵.
這次做The Clocks,沒有像以前那樣利用數組表示變換,而是選擇了直接用一個長整類型
表示時鐘狀態(為了寫寫C++的位操作),畢竟,情況只有4^9種.每一個變換最多只能用3次,這
個大家自然是知道的,因為用四次或四次以上便已經多繞了圈圈.所以enu()過程旨在枚舉每種
變換使用的次數,情況共有4^9.
其他的部分通過注釋應該能看懂了.
1 /*
2 ID:31440461
3 PROG:clocks
4 LANG:C++
5 */
6 #include<iostream>
7 using namespace std;
8 const int key[9]={1131776,86016,20800,66576,17732,4161,1300,21,325};
9 int org=0,final[9],cou[9],ans=100;
10
11
12 /* 這個是調試的時候用的
13 void poutput(int x)
14 {
15 for (int i=0;i<9;i++) cout << ((x >> (8-i)*2) & 3) << ' ';
16 cout << endl;
17 return;
18 }
19 */
20
21 /* 這個函數的功能是 返回x經y變換后的結果 */
22 int transf(int x,int y)
23 {
24 int num=0;
25 for (int i=0;i<9 ;i++ )
26 {
27 int tmp=((x >> (i*2) ) + (y >> (i*2) )) & 3;
28 num+=tmp << (i*2);
29 }
30 return num;
31 }
32
33
34 void check(int tot)
35 {
36 int x=org;
37 for (int i=0;i<9 ;i++ )
38 for (int j=0;j<cou[i] ;j++ ) x=transf(x,key[i]);
39 if ((x==0)&&(tot<ans))
40 {
41 for (int i=0;i<9 ;i++ ) final[i]=cou[i];
42 ans=tot;
43 }
44 return;
45 }
46
47 /* 枚舉每種變換所用的次數 */
48 void enu(int stp,int tot)
49 {
50 if (stp>8)
51 {
52 check(tot);
53 return;
54 }
55 for (int i=3;i>=0 ;i-- )
56 {
57 cou[stp]=i;
58 enu(stp+1,tot+i);
59 }
60 }
61
62 void output()
63 {
64 for (int i=0;i<9;i++)
65 for (int j=0;j<final[i] ;j++ )
66 { ans--;
67 if (ans>0)
68 cout << (i+1) << ' ';
69 else cout << (i+1) << endl;
70 }
71 }
72
73 int main()
74 {
75 freopen("clocks.in","r",stdin);
76 freopen("clocks.out","w",stdout);
77 /*
78 一個鐘最多有四種狀態:3 6 9 12(0)
79 可以用 01 10 11 00 這樣的兩位二進制數表示
80 一個這樣的鐘
81 3 3 3
82 6 6 6
83 9 12 3
84 被我表示成
85 01 01 01
86 10 10 10
87 11 00 01
88 =
89 010101101010110001
90 連變換操作也用對應的方法表示了,變換信息存儲在key[]數組中
91 */
92 for (int i=0;i<9 ;i++ )
93 {
94 int x;
95 cin >> x;
96 org=(org << 2)+(x/3)%4;
97 }
98 enu(0,0);
99 output();
100 return 0;
101 }
102
key[]常數里那些數是通過這個代碼產生的:
1 #include<iostream>
2 #include<string>
3 using namespace std;
4
5 int main()
6 {
7 freopen("data.in","r",stdin);
8 freopen("data.out","w",stdout);
9 for (int i=1;i<=9 ;++i )
10 {
11 string s;
12 cin >> s;
13 int num=0;
14 for (int j=0;j<s.size() ;++j ) num+=(1 << (('I'-s[j])*2));
15 cout << num << ',';
16 }
17 return 0;
18 }
19
而"data.in"文件中所包含的數據如下:
ABDE
ABC
BCEF
ADG
BDEFH
CFI
DEGH
GHI
EFHI
補充:我本來不想走尋常路的,因為我的目標是熟悉C++而不是學習算法,USACO上的種種我
已經基本掌握了,所以我寫了下面這個迭代深搜+位操作的代碼,結果超時了(按理說不應該啊!).
貼上失敗的代碼:
1 /*
2 ID:31440461
3 PROG:clocks
4 LANG:C++
5 */
6 #include<iostream>
7 using namespace std;
8 const int key[9]={1131776,86016,20800,66576,17732,4161,1300,21,325};
9 int org=0,step[10000],lim=0,cou[9];
10 bool flg=0;
11 /* 這個函數的功能是 返回x經y變換后的結果 */
12 int transf(int x,int y)
13 {
14 int num=0;
15 for (int i=0;i<9 ;i++ )
16 {
17 int tmp=((x >> (i*2) ) + (y >> (i*2) )) & 3;
18 num+=tmp << (i*2);
19 }
20 return num;
21 }
22 /* 這個是調試的時候用的
23 void output(int x)
24 {
25 for (int i=0;i<9;i++) cout << ((x >> (8-i)*2) & 3) << ' ';
26 cout << endl;
27 return;
28 }
29 */
30 void handle(int cur,int stp)
31 {
32 if (flg) return;
33 if (cur==0)
34 {
35 for (int i=0;i<stp-1 ;++i ) cout << step[i] << ' ';
36 (stp>0)?cout << step[stp-1] << endl:cout << endl;/*搞清楚直接就是答案的時候要不要輸出換行符!*/
37 flg=1;
38 return;
39 }
40 if (stp>=lim) return;
41 for (int i=0;i<9 ;++i )
42 {
43 /*
44 一個變換最多用三次,用四次等價于沒用過,用五次等價于用一次
45 這里的cou[i]記錄了第i號變換已經使用的次數
46 */
47 if (cou[i]>=3) continue;
48 step[stp]=i+1;
49 cou[i]++;
50 handle( transf(cur,key[i]) , stp+1 );
51 cou[i]--;
52 }
53 }
54
55 int main()
56 {
57 freopen("clocks.in","r",stdin);
58 freopen("clocks.out","w",stdout);
59 /*
60 一個鐘最多有四種狀態:3 6 9 12(0)
61 可以用 01 10 11 00 這樣的兩位二進制數表示
62 一個這樣的鐘
63 3 3 3
64 6 6 6
65 9 12 3
66 被我表示成
67 01 01 01
68 10 10 10
69 11 00 01
70 =
71 010101101010110001
72 連變換操作也用對應的方法表示了,變換信息存儲在key[]數組中
73 */
74 for (int i=0;i<9 ;i++ )
75 {
76 int x;
77 cin >> x;
78 org=(org << 2)+(x/3)%4;
79 }
80 /*
81 // 測試一下transf()函數的正確性
82 output(org);
83 output(transf(org,key[7]));
84 */
85 //memset(cou,0,sizeof(cou));
86 while (!flg)
87 {
88 handle(org,0);
89 lim++;
90 }
91
92 return 0;
93 }
94
|