|
|
中间漏了一个题目,极度恶心的 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
|