开关问题
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=;
int con[p][p];
int N;
int beg[p],fin[p];
int function()
{
int i,j,k,t,row,col,temp,count=;
for(row=col=; row<=N&&col<=N; row++,col++)
{
if(con[row][col]==)
{
for(i=row+; i<=N; i++)
{
if(con[i][col]!=)
{
for(j=; j<=N+; j++)
{
swap(con[row][j],con[i][j]);
}
break;
}
}
}
if(con[row][col]==)
{
row--;
continue;
}
for(k=; k<=N; k++)
{
if(con[k][col]!=&&k!=row)
{
temp=-(con[k][col]/con[row][col]);
for(t=col; t<=N+; t++)
{
con[k][t]=(temp*con[row][t])+con[k][t];
}
}
}
}
for(k=row; k<N+; k++)
if(con[k][N+]!=) { return ; }
if(row==N+) { return ; }
else
{
return <<(N-row+);
}
}
int main()
{
int T,i,j,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(i=; i<=N; i++)
{
scanf("%d",&beg[i]);
}
for(i=; i<=N; i++)
{
scanf("%d",&fin[i]);
}
scanf("%d%d",&x,&y);
memset(con,,sizeof(con));
while(x!=&&y!=)
{
con[y][x]=;
scanf("%d%d",&x,&y);
}
for(i=; i<=N; i++)
{
con[i][i]=;
}
for(i=; i<=N; i++)
{
if(beg[i]==fin[i])
{
con[i][N+]=;
}
else
{
con[i][N+]=;
}
}
int pp = function();
if(pp)
{
printf("%d\n",pp);
}
else
{
printf("Oh,it's impossible~!!\n");
}
}
}