|
|
中間漏了一個(gè)題目,極度惡心的 Packing Rectangles.上次做USACO的時(shí)候我就是直接跳
過(guò)去的,以至于現(xiàn)在我依然保留對(duì)它的恐懼.這恐怕很大程度上是心理因素而不是能力問(wèn)題,但是
我是一個(gè)崇尚莊周的人,按照我們以前班主任的說(shuō)法就是自由主義泛濫,所以我決定順著我的心
意:先跳過(guò)去.對(duì)我而言 Packing Rectangles 的惡心程度可以跟后面的PRIME3相匹敵.
這次做The Clocks,沒(méi)有像以前那樣利用數(shù)組表示變換,而是選擇了直接用一個(gè)長(zhǎng)整類(lèi)型
表示時(shí)鐘狀態(tài)(為了寫(xiě)寫(xiě)C++的位操作),畢竟,情況只有4^9種.每一個(gè)變換最多只能用3次,這
個(gè)大家自然是知道的,因?yàn)橛盟拇位蛩拇我陨媳阋呀?jīng)多繞了圈圈.所以enu()過(guò)程旨在枚舉每種
變換使用的次數(shù),情況共有4^9.
其他的部分通過(guò)注釋?xiě)?yīng)該能看懂了.
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 /* 這個(gè)是調(diào)試的時(shí)候用的
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 /* 這個(gè)函數(shù)的功能是 返回x經(jīng)y變換后的結(jié)果 */
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 /* 枚舉每種變換所用的次數(shù) */
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 一個(gè)鐘最多有四種狀態(tài):3 6 9 12(0)
79 可以用 01 10 11 00 這樣的兩位二進(jìn)制數(shù)表示
80 一個(gè)這樣的鐘
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 連變換操作也用對(duì)應(yīng)的方法表示了,變換信息存儲(chǔ)在key[]數(shù)組中
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[]常數(shù)里那些數(shù)是通過(guò)這個(gè)代碼產(chǎn)生的:
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"文件中所包含的數(shù)據(jù)如下:
ABDE
ABC
BCEF
ADG
BDEFH
CFI
DEGH
GHI
EFHI
補(bǔ)充:我本來(lái)不想走尋常路的,因?yàn)槲业哪繕?biāo)是熟悉C++而不是學(xué)習(xí)算法,USACO上的種種我
已經(jīng)基本掌握了,所以我寫(xiě)了下面這個(gè)迭代深搜+位操作的代碼,結(jié)果超時(shí)了(按理說(shuō)不應(yīng)該啊!).
貼上失敗的代碼:
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 /* 這個(gè)函數(shù)的功能是 返回x經(jīng)y變換后的結(jié)果 */
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 /* 這個(gè)是調(diào)試的時(shí)候用的
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;/*搞清楚直接就是答案的時(shí)候要不要輸出換行符!*/
37 flg=1;
38 return;
39 }
40 if (stp>=lim) return;
41 for (int i=0;i<9 ;++i )
42 {
43 /*
44 一個(gè)變換最多用三次,用四次等價(jià)于沒(méi)用過(guò),用五次等價(jià)于用一次
45 這里的cou[i]記錄了第i號(hào)變換已經(jīng)使用的次數(shù)
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 一個(gè)鐘最多有四種狀態(tài):3 6 9 12(0)
61 可以用 01 10 11 00 這樣的兩位二進(jìn)制數(shù)表示
62 一個(gè)這樣的鐘
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 連變換操作也用對(duì)應(yīng)的方法表示了,變換信息存儲(chǔ)在key[]數(shù)組中
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 // 測(cè)試一下transf()函數(shù)的正確性
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
|