数学 --- 高斯消元 POJ 1830
开关问题
Problem's Link: http://poj.org/problem?id=1830
Mean:
略
analyse:
增广矩阵：con[i][j]：若操作j，i的状态改变则con[i][j]=1,否则con[i][j]=0。
最后的增广矩阵应该是N*（N+1），最后一列：对比开光的始末状态，若相同则为0，若不同则为1；
最后的解共有三种：
1.无解，既出现了一行中前面N个数为0，第N+1的值非0；
2.没有第1种情况出现，存在X行数值全为0，则解的个数为2^X;
3,没有1,2 两种情况出现，唯一解，输出1。
Time complexity: O(n)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-06-17-22.36 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; const int p=30; int con[p][p]; int N; int beg[p],fin[p]; int function() { int i,j,k,t,row,col,temp,count=0; for(row=col=1; row<=N&&col<=N; row++,col++) { if(con[row][col]==0) { for(i=row+1; i<=N; i++) { if(con[i][col]!=0) { for(j=1; j<=N+1; j++) { swap(con[row][j],con[i][j]); } break; } } } if(con[row][col]==0) { row--; continue; } for(k=1; k<=N; k++) { if(con[k][col]!=0&&k!=row) { temp=-(con[k][col]/con[row][col]); for(t=col; t<=N+1; t++) { con[k][t]=(temp*con[row][t])+con[k][t]; } } } } for(k=row; k<N+1; k++) if(con[k][N+1]!=0) { return 0; } if(row==N+1) { return 1; } else { return 1<<(N-row+1); } } int main() { int T,i,j,x,y; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i=1; i<=N; i++) { scanf("%d",&beg[i]); } for(i=1; i<=N; i++) { scanf("%d",&fin[i]); } scanf("%d%d",&x,&y); memset(con,0,sizeof(con)); while(x!=0&&y!=0) { con[y][x]=1; scanf("%d%d",&x,&y); } for(i=1; i<=N; i++) { con[i][i]=1; } for(i=1; i<=N; i++) { if(beg[i]==fin[i]) { con[i][N+1]=0; } else { con[i][N+1]=1; } } int pp = function(); if(pp) { printf("%d\n",pp); } else { printf("Oh,it's impossible~!!\n"); } } }