POJ1830 开关问题（异或方程组）

你的名字 2024-04-17 05:49 56阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。

你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。

对于任意一个开关，最多只能进行一次开关操作。

你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）  
输入格式

输入第一行有一个数K，表示以下有K组测试数据。

每组测试数据的格式如下：

第一行 一个数N（0 < N < 29）。

第二行 N个0或者1的数，表示开始时N个开关状态。

第三行 N个0或者1的数，表示操作结束后N个开关的状态。

接下来 每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。

每组数据以 0 0 结束。  
输出格式

如果有可行方法，输出总数，否则输出“Oh,it’s impossible~!!” 。  
输入样例：

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

输出样例：

4  
Oh,it’s impossible~!!

分析：  
涨姿势的一道题。同时，认真耐心，不惧怕的去看题，看题解，至关重要。不要害怕。  
日后必当更加勉励。

参考博客：https://blog.csdn.net/immiao/article/details/17342143  
这篇博客的思路还是很不错的。建议看下。  
下面我说下我对这个题的理解：  
题目给出的条件：  
1，每个开关至多一次操作。  
2，操作i开关会改变j开关的状态。

**开关至多操作一次**，那么我是否可以用一个数组x。来表示开关的操作情况呢。  
即 x\[i\] == 1 则表示第i号开关我是按了一次的。x\[i\] == 0 则表示第i号开关没有按。

**操作i开关会改变j开关的状态**,那么我是否可以用一个二维数组a来把这个改变情况保存下来呢。a\[i\]\[j\] == 1 则表示操作j号开关，会改变i号开关。a\[i\]\[j\] == 0 则表示不会改变。特殊的，我们需要令a\[i\]\[i\] == 1（一开始忘了，导致样例都没过）。

我们在把开关的初始状态的放入start数组，最终状态放入end数组。  
我们令开关开时状态为1.关是状态为0.  
我们清楚的知道，每次按一下i号开关，所产生的影响无非就是对i号及其相关的开关产生影响。影响情况应为1变0.0变1.这不就是异或的性质了木。  
1^1 == 0  
1 ^0 == 1.  
上面两个式子中的第一个1表示a数组里面的1.第二个数字表示开关的状态，结果值为开关状态。

那么我们可以得到下面方程组：  
start\[i\] ^ a\[i\]\[1\] \* x\[1\] ^ a\[i\]\[2\] \* x\[2\] ~~ x\[i\]\[n\] \* x\[n\] == end\[i\]。  
转化得：  
a\[i\]\[1\] \* x\[1\] ^ a\[i\]\[2\] \* x\[2\] ~~ x\[i\]\[n\] \* x\[n\] == end\[i\] ^ start\[i\] 。  
简单分析一下第一个式子。就是第i号开关的开始状态异或所有能改变第i号开关的操作，当然，像a\[i\]\[j\]==1了，那么x\[j\] == 1.这个改变才能成立。所以a\[i\]\[j\] \* x\[j\]。  
下面code使用了位运算来压缩

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int T,N;
    int a[32];
    
    int main(){
        scanf("%d",&T);
        while(T --){
            scanf("%d",&N);
            for(int i = 1; i <= N; i ++)
                scanf("%d",&a[i]);
            for(int i = 1; i <= N; i ++){
                int x; scanf("%d",&x);
                a[i] ^= x; a[i] |= (1 << i);
            }
            while(1){
                int i,j; scanf("%d%d",&i,&j);
                if(i == 0 && j == 0) break;
                a[j] |= (1 << i);
            }
            int ans = 1;
            for(int i = 1; i <= N; i ++){
                for(int j = i + 1; j <= N; j ++){
                    if(a[i] < a[j])
                        swap(a[i],a[j]);
                }
                if(a[i] == 1){
                    ans = 0; break;
                }
                if(a[i] == 0){
                    ans = 1 << (N - i + 1); break;
                }
                for(int j = N; j >= 1; j --){
                    if((a[i] >> j) & 1){
                        for(int k = 1; k <= N; k ++){
                            if(i == k || (((a[k] >> j) & 1) == 0)) continue;
                            else {
                                a[k] ^= a[i];
                            }
                        }
                        break;
                    }
                }
            }
            if(ans == 0){
                printf("Oh,it's impossible~!!\n");
            } else {
                printf("%d\n",ans);
            }
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/