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