数据加载中……

USACO 1.4.2 The Clocks

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



posted on 2009-07-14 23:08 Chen Jiecao 阅读(936) 评论(1)  编辑 收藏 引用 所属分类: USACO

评论

# re: USACO 1.4.2 The Clocks  回复  更多评论   

具体key[9]和“57521883”的产生原理没太看懂,求解释!
2012-10-08 20:55 | freeboy1015

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理