开关问题

Problem's Link:

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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define LL long long#define ULL unsigned long longusing 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

View Code