pku 1222 EXTENDED LIGHTS OUT 高斯消元

题意:
一个5*6的开关矩阵,拨动每个开关,都会使得它本身以及前后左右四个开关反转。现在给出所有开关的初始状态,问使得所有开关处于关状态,需要拨动的开关。

解法:
首先看到这题就应该想到方程组。或者说,是一个模2方程组。
但是,这个会给我们带来求解的麻烦。求解方程组有经典的高斯消元法,但是出现模运算,确实让人头疼。这里,我们想到了异或运算,联系高斯消元的本质,是用一个方程来代换另外一个方程,十进制模二运算中的加、减运算与二进制中的异或运算正好对应!然后下面的事情就简单多了

有一个小技巧,使用位运算能够大大简化编程复杂度。
可以将原来矩阵的每一行压缩成一个32位整数,这样每次消元的过程中选择列主元的过程可以用排序轻松解决~,然后消去的过程和回代的过程也就非常好实现了。用这种方法,这题的代码量可以控制在60行以内。
忽然想起了老队长说过的话:100行以内的程序才是正解,做了这么多题,越来越发现这句话是多么的经典。话说现在郭老大在马化腾那应该算个红人了~

还有件很囧的事,使用STL里的greater仿函数竟然要包括一个叫functional的头文件,甚是诡异。。

代码:
 1 # include <cstdio>
 2 # include <algorithm>
 3 # include <functional>
 4 # include <cstring>
 5 using namespace std;
 6 inline void setbit(int &num,int bit)
 7 {
 8     num|=1<<(30-bit);
 9 }
10 inline bool getbit(int &num,int bit)
11 {
12     if(num&(1<<(30-bit))) return true;
13     else return false;
14 }
15 int main()
16 {
17     int test;
18     scanf("%d",&test);
19     for(int t=1;t<=test;t++)
20     {
21         int e[30];
22         memset(e,0,sizeof(e));
23         for(int i=0;i<30;i++)
24         {
25             int tmp;
26             scanf("%d",&tmp);
27             setbit(e[i],i);
28             if(i%6!=0) setbit(e[i],i-1);
29             if(i%6!=5) setbit(e[i],i+1);
30             if(i/6!=0) setbit(e[i],i-6);
31             if(i/6!=4) setbit(e[i],i+6);
32             if(tmp) setbit(e[i],30);
33         }
34         for(int i=0;i<30;i++)//消元
35         {
36             sort(e+i,e+30,greater<int>());
37             if(getbit(e[i],i))
38                 for(int j=i+1;j<30;j++)
39                     if(getbit(e[j],i))
40                         e[j]^=e[i];
41             
42         }
43         for(int i=29;i>=0;i--)//回代
44             if(getbit(e[i],i))
45               for(int j=i-1;j>=0;j--)
46                   if(getbit(e[j],i))
47                       e[j]^=e[i];
48         printf("PUZZLE #%d\n",t);
49         for(int i=0;i<30;i++)
50         {
51            if(e[i])
52              printf("%d",getbit(e[i],30));
53            else printf("0");
54            if(i%6==5) printf("\n");
55            else printf(" ");
56         }
57     }
58     return 0;
59 }



posted on 2011-01-16 01:35 yzhw 阅读(315) 评论(0)  编辑 收藏 引用 所属分类: combination math


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


<2011年1月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜