Problem Description

有N個相同的開關，每個開關都與某些開關有著聯系，每當你打開或者關閉某個開關的時候，其他的與此開關相關聯的開關也會相應地發生變化，即這些相聯系的開關的狀態如果原來為開就變為關，如果為關就變為開。你的目標是經過若干次開關操作后使得最后N個開關達到一個特定的狀態。對于任意一個開關，最多只能進行一次開關操作。你的任務是，計算有多少種可以達到指定狀態的方法。（不計開關操作的順序）

Input

輸入第一行有一個數K，表示以下有K組測試數據。?
每組測試數據的格式如下：?
第一行 一個數N（0 < N < 29）?
第二行 N個0或者1的數，表示開始時N個開關狀態。?
第三行 N個0或者1的數，表示操作結束后N個開關的狀態。?
接下來 每行兩個數I J，表示如果操作第 I 個開關，第J個開關的狀態也會變化。每組數據以 0 0 結束。?

Output

如果有可行方法，輸出總數，否則輸出“Oh,it's impossible~!!” 不包括引號

Sample Input

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

Sample Output

4
Oh,it's impossible~!!

思路：

根據題目可知是一個高斯消元求異或方程組的題，要求總共的方案數，那么也是要先求出自由元的個數 freeNum，由于每個自由元有 1、0 兩種狀態，那么最后結果就是?1<<freeNum

n 個燈泡，構造 n 個方程，根據給出的開始狀態與結束狀態可知，如果一個燈開始狀態與結束狀態不同，那么這個燈肯定是被按過，反之則沒有被按過，那么每個方程的解 a[i][n] 就是每個燈開始狀態與結束狀態的異或

接著看左邊的系數矩陣部分，對于每個開關來說，每次按開關，開關自身會發生變換，那么 a[i][i]=1，即第 i 個開關受第 i 個開關影響，然后再看給出兩個關聯的開關 t1、t2，由于關聯的兩個開關相互影響，按下 t1 之后 t2 隨之改變，那么就有 a[t2][t1]=1，即第 t2 個開關受第 t1 個開關影響

最后進行高斯消元，尋找自由元的個數然后計算 1<<freeNum 即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define E 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD=6; const int N=1000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std;int a[N][N];//增廣矩陣 int x[N];//解集 int freeX[N];//自由變元 int Gauss(int equ,int var){//返回自由變元個數/*初始化*/for(int i=0;i<=var;i++){x[i]=0;freeX[i]=0;}/*轉換為階梯陣*/int col=0;//當前處理的列int num=0;//自由變元的序號int k;//當前處理的行for(k=0;k<equ&&col<var;k++,col++){//枚舉當前處理的行int maxRow=k;//當前列絕對值最大的行for(int i=k+1;i<equ;i++){//尋找當前列絕對值最大的行if(abs(a[i][col])>abs(a[maxRow][col]))maxRow=i;}if(maxRow!=k){//與第k行交換for(int j=k;j<var+1;j++)swap(a[k][j],a[maxRow][j]);}if(a[k][col]==0){//col列第k行以下全是0，處理當前行的下一列freeX[num++]=col;//記錄自由變元k--;continue;}for(int i=k+1;i<equ;i++){if(a[i][col]!=0){for(int j=col;j<var+1;j++){//對于下面出現該列中有1的行，需要把1消掉a[i][j]^=a[k][j];}}}}/*求解*///無解：化簡的增廣陣中存在(0,0,...,a)這樣的行，且a!=0for(int i=k;i<equ;i++)if(a[i][col]!=0)return -1;return var-k;//自由變元有var-k個 } int start[N];//開始狀態 int endd[N];//結束狀態 int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0;i<n;i++)//開始狀態scanf("%d",&start[i]);for(int i=0;i<n;i++)//最終狀態scanf("%d",&endd[i]);memset(a,0,sizeof(a));for(int i=0;i<n;i++)//每個方程的解a[i][n]=start[i]^endd[i];for(int i=0;i<n;i++)//第i個開關受第i個開關影響a[i][i]=1;int t1,t2;while(scanf("%d%d",&t1,&t2)!=EOF&&(t1+t2)){//a[t1-1][t2-1]=1;a[t2-1][t1-1]=1;}int freeNum=Gauss(n,n);if(freeNum==-1)printf("Oh,it's impossible~!!\n");elseprintf("%d\n",1<<freeNum);}return 0; }

?

總結

以上是生活随笔為你收集整理的开关问题（POJ-1830）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。