微信公众号的h5网站开发,什么是功能型网站,工作室建设,网站开发培训 从0开关问题Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 7771 Accepted: 3058 Description 有N个相同的开关#xff0c;每个开关都与某些开关有着联系#xff0c;每当你打开或者关闭某个开关的时候#xff0c;其他的与此开关相关联的开关也会相应地发生变化每个开关都与某些开关有着联系每当你打开或者关闭某个开关的时候其他的与此开关相关联的开关也会相应地发生变化即这些相联系的开关的状态如果原来为开就变为关如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关最多只能进行一次开关操作。你的任务是计算有多少种可以达到指定状态的方法。不计开关操作的顺序Input
输入第一行有一个数K表示以下有K组测试数据。 每组测试数据的格式如下 第一行 一个数N0 N 29 第二行 N个0或者1的数表示开始时N个开关状态。 第三行 N个0或者1的数表示操作结束后N个开关的状态。 接下来 每行两个数I J表示如果操作第 I 个开关第J个开关的状态也会变化。每组数据以 0 0 结束。 Output
如果有可行方法输出总数否则输出“Oh,its 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 0Sample Output
4
Oh,its impossible~!!Hint
第一组数据的说明 一共以下四种方法 操作开关1 操作开关2 操作开关3 操作开关1、2、3 不记顺序 Source LIANGLIANGPOJDescription 有N个相同的开关每个开关都与某些开关有着联系每当你打开或者关闭某个开关的时候其他的与此开关相关联的开关也会相应地发生变化即这些相联系的开关的状态如果原来为开就变为关如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关最多只能进行一次开关操作。你的任务是计算有多少种可以达到指定状态的方法。不计开关操作的顺序 Input 输入第一行有一个数K表示以下有K组测试数据。 每组测试数据的格式如下 第一行 一个数N0 N 29 第二行 N个0或者1的数表示开始时N个开关状态。 第三行 N个0或者1的数表示操作结束后N个开关的状态。 接下来 每行两个数I J表示如果操作第 I 个开关第J个开关的状态也会变化。每组数据以 0 0 结束。 Output 如果有可行方法输出总数否则输出“Oh,its 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 0Sample Output 4
Oh,its impossible~!!Hint 第一组数据的说明 一共以下四种方法 操作开关1 操作开关2 操作开关3 操作开关1、2、3 不记顺序 Source LIANGLIANGPOJ 注意题目中i和j说反了 每个灯可以控制自己和其他的一些灯xi代表第i个灯是否操作所以xi的值只会是0或1。 对每一个灯的来说肯能会收几个灯的控制如果第i个灯被第k个灯控制那么xk的系数为1否则为0,。结果如果变化为1不变化为0所以得到一个异或方程组。 求解这个异或方程组进行高斯消元 异或方程组的高斯消元的方式和不同的高斯消元大部分相同但是不是用减而是判断要消的那行如果是1进行异或否则不动。 通过高斯消元可以判断出方程是否有解和解的个数。 如本题中求出矩阵的自由元数num1个。所以这num1个值的取值对结果是没有影响的又因为xi只能取0或1所以方法数位2^num1 #include cstdio
#include cstring
#include algorithm
using namespace std ;
int Map[30][30] , a[30] ;
void swap1(int p,int q,int n)
{int j , temp ;temp a[p] ; a[p] a[q] ; a[q] temp ;for(j 1 ; j n ; j){temp Map[p][j] ; Map[p][j] Map[q][j] ; Map[q][j] temp ;}return ;
}
int solve(int n)
{int i , j , k , t 1 , num1 0 ;for(i 1 ; i n t n ; i){for(j i ; j n ; j)if( Map[j][t] )break ;if(j n1){t ;i-- ;num1;continue ;}if( i ! j )swap1(i,j,n) ;for(j i1 ; j n ; j){if( Map[j][t] 0 ) continue ;for(k t ; k n ; k)Map[j][k] Map[i][k] ^ Map[j][k] ;a[j] a[i] ^ a[j] ;}t ;}for( ; i n ; i)if( a[i] 1 )return -1 ;return num1 ;
}
int main()
{int t , n , i , j , x ;scanf(%d, t) ;while( t-- ){memset(Map,0,sizeof(Map)) ;scanf(%d, n) ;for(i 1 ; i n ; i){scanf(%d, a[i]) ;Map[i][i] 1 ;}for(i 1 ; i n ; i){scanf(%d, x) ;a[i] a[i]^x ;}int u , v ;while( scanf(%d %d, v, u) ){if( u 0 v 0 ) break ;Map[u][v] 1 ;}x solve(n) ;if( x -1 )printf(Oh,its impossible~!!\n) ;elseprintf(%d\n, 1x) ;}return 0;
}异或方程组的高斯消元模板 //有equ个方程var个变元。增广矩阵行数为equ,列数为var1,分别为0到varint equ,var;int a[MAXN][MAXN]; //增广矩阵int x[MAXN]; //解集int free_x[MAXN];//用来存储自由变元多解枚举自由变元可以使用int free_num;//自由变元的个数//返回值为-1表示无解为0是唯一解否则返回自由变元个数int Gauss(){int max_r,col,k;free_num 0;for(k 0, col 0 ; k equ col var ; k, col){max_r k;for(int i k1;i equ;i){if(abs(a[i][col]) abs(a[max_r][col]))max_r i;}if(a[max_r][col] 0){k--;free_x[free_num] col;//这个是自由变元continue;}if(max_r ! k){for(int j col; j var1; j)swap(a[k][j],a[max_r][j]);}for(int i k1;i equ;i){if(a[i][col] ! 0){for(int j col;j var1;j)a[i][j] ^ a[k][j];}}}for(int i k;i equ;i)//进入此循环的条件本身矩阵行大于列 或者 因为出现自由变元后使得非自由变元数比行数小if(a[i][col] ! 0)//若等号右边是1则无解因为等号左边已经消为0return -1;//无解if(k var) return var-k;//自由变元个数//唯一解回代for(int i var-1; i 0;i--){x[i] a[i][var];for(int j i1;j var;j)x[i] ^ (a[i][j] x[j]);}return 0;} 异或方程组的高斯消元模板
