題意：
一個(gè)5*6的開關(guān)矩陣，撥動(dòng)每個(gè)開關(guān)，都會(huì)使得它本身以及前后左右四個(gè)開關(guān)反轉(zhuǎn)。現(xiàn)在給出所有開關(guān)的初始狀態(tài)，問使得所有開關(guān)處于關(guān)狀態(tài)，需要撥動(dòng)的開關(guān)。
解法：
首先看到這題就應(yīng)該想到方程組。或者說，是一個(gè)模2方程組。
但是，這個(gè)會(huì)給我們帶來求解的麻煩。求解方程組有經(jīng)典的高斯消元法，但是出現(xiàn)模運(yùn)算，確實(shí)讓人頭疼。這里，我們想到了異或運(yùn)算，聯(lián)系高斯消元的本質(zhì)，是用一個(gè)方程來代換另外一個(gè)方程，十進(jìn)制模二運(yùn)算中的加、減運(yùn)算與二進(jìn)制中的異或運(yùn)算正好對(duì)應(yīng)！然后下面的事情就簡(jiǎn)單多了
有一個(gè)小技巧，使用位運(yùn)算能夠大大簡(jiǎn)化編程復(fù)雜度。
可以將原來矩陣的每一行壓縮成一個(gè)32位整數(shù)，這樣每次消元的過程中選擇列主元的過程可以用排序輕松解決~，然后消去的過程和回代的過程也就非常好實(shí)現(xiàn)了。用這種方法，這題的代碼量可以控制在60行以內(nèi)。
忽然想起了老隊(duì)長(zhǎng)說過的話:100行以內(nèi)的程序才是正解，做了這么多題，越來越發(fā)現(xiàn)這句話是多么的經(jīng)典。話說現(xiàn)在郭老大在馬化騰那應(yīng)該算個(gè)紅人了~
還有件很囧的事，使用STL里的greater仿函數(shù)竟然要包括一個(gè)叫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 }